玩果盒游戏

Question

玩果盒游戏

Intro

水果盒是一个由10x17个数字网格组成的游戏，每个网格在1到9之间，目标是在一个两分钟的时间窗口中尽可能多地清除数字。为了清除数字，选择一个与网格对齐的矩形，如果其中的数字之和为10，则将其从字段中清除。在游戏开始时，网格是随机填充的，唯一的要求是字段中所有数字的总和为10的倍数。

这是一个示例开始字段，有几个，但不是全部，有效的可能清除显示。

这是一个游戏中途的场地，由于先前的数字被从球场上删除，新的可能的清除被打开。注意，例如，如果左下角的6-3-1矩形被清除，它将打开清除当前被阻塞的两对9-1对的可能性。

也许让自己熟悉这个游戏的最简单的方法是玩几轮游戏，这可以在这里完成：果盒

挑战

如果您现在还没有猜到，那么现在的挑战是编写一个程序，尽可能地优化上面的游戏，其中最优意味着清除最多的数字。

输入

输入将是数字的起始网格。它可以以任何合理的形式表示，这意味着你可以把它作为一个字符串，一个由10个17长整数组成的数组，一个由170个整数组成的2D数组，或任何其他类似的形式。用你最好的判断什么是合理的意思，但本着挑战的精神，它应该是开始的数字网格的一些表示。请在您的答案中具体说明输入应如何传递。

输出

输出应该是最终达到的分数(数字清除)，以及实现这个分数的移动列表。同样，这个输出的确切形式取决于您，但是应该是这样的，在给定的移动列表中，您可以从相同的开始配置中明确地重放游戏，从而最终得到给定的最终分数。例如，可以按顺序输出每个矩形的左上角和右下角坐标。

除此之外，正常的输入/输出规则，以及禁止的漏洞适用。如果您不确定任何规格，请留下评论，我会澄清。

评分

在一个特定的棋盘上的分数是根据在比赛过程中清除了多少个数字来决定的。例如，如果游戏结束时剩下14个数字，不管它们的值如何，最后的分数将是170-14 = 156。

由于每个开始板将有一个不同的最佳分数，所有的答案将运行在相同的10个董事会的评价，我将保持隐藏。在这篇文章的底部，我将根据他们在这10个董事会中的平均表现，保持当前最高职位的领导地位。答案将在第一次提交后的一个月后被接受。

编辑:如果算法不是确定性的，那么10个板中的每个板都将使用-5的平均值.

其他规则

• 由于最初的游戏给你2分钟，提交必须在2分钟内运行在我的机器(一个4核心，2017年MacBook Pro与16 of内存)。对于典型的变化，我们将给出少量的回旋余地。
• 你必须使用一种语言，这是免费使用，可以在网上找到。(这不应取消任何常用语言的资格)

主板

一个月过去了，领导板现在关闭了。恭喜你赢得了胜利！

1. 丁莱多珀：147.2点
2. undefined：129.0点
3. 路易斯·门多：126.0点
4. Ajax1234：119.6点
5. 理查德·诺依曼：118.0点

示例板

这里有三个有效的例子板。每个棋盘还包括天真地清除长方形的得分，直到没有保留为止，作为可能得分的下限。

Board 1: Optimal Score >= 104
---------------------------------
7 8 3 8 4 4 3 1 4 5 3 2 7 7 4 6 7
6 4 3 3 3 7 1 5 1 9 2 3 4 5 5 4 6
9 7 5 5 4 2 2 9 1 9 1 1 1 7 2 2 4
3 3 7 5 5 8 9 3 6 8 5 3 5 3 2 8 7
7 3 5 8 7 8 6 3 5 6 8 9 9 9 8 5 3
5 8 3 9 9 7 6 7 3 6 9 1 6 8 3 2 5
4 9 5 7 7 5 7 8 4 4 4 2 9 8 7 3 5
8 2 1 7 9 1 7 9 6 5 4 1 3 7 6 9 6
2 3 5 6 5 6 3 9 6 6 3 6 9 7 8 8 1
1 8 5 2 2 3 1 9 3 3 3 3 7 8 7 4 8



Board 2: Optimal Score >= 113
---------------------------------
5 4 3 6 7 2 3 5 1 2 8 6 2 3 8 1 7
3 8 7 5 4 6 6 1 6 5 7 5 4 3 8 8 1
7 9 9 3 1 7 1 8 9 1 8 4 9 8 7 1 7
5 4 6 3 1 3 1 5 4 7 4 1 5 8 1 1 5
3 3 4 3 8 7 6 5 8 6 3 2 8 4 6 6 6
7 2 2 8 9 9 7 7 7 7 3 9 1 2 7 2 4
4 1 1 5 7 7 9 2 3 6 9 2 7 5 7 7 1
9 6 7 1 7 9 8 7 3 2 8 9 8 6 1 6 8
1 3 9 6 4 5 5 3 4 9 4 1 9 2 6 9 1
6 9 6 3 1 5 8 2 3 5 4 2 6 4 5 3 5


Board 3: Optimal Score >= 116
---------------------------------
9 2 2 7 6 6 1 7 1 9 7 6 9 3 8 8 3
2 2 4 8 6 9 8 4 8 3 8 1 1 2 7 4 9
8 5 1 8 9 5 5 1 7 7 5 1 3 4 6 5 1
5 2 9 2 2 1 7 5 4 5 9 5 6 4 2 9 7
4 9 6 3 6 2 3 9 2 1 2 8 8 7 9 4 7
1 9 7 2 2 2 6 2 1 2 5 6 2 5 6 7 8
8 8 4 4 9 5 7 2 3 8 2 4 8 1 4 7 3
9 4 7 2 3 7 2 8 4 6 9 8 3 8 5 2 9
4 8 1 3 9 1 6 6 6 7 2 1 4 5 2 6 2
3 7 3 8 1 2 1 8 1 8 3 3 2 3 2 7 4

Answer 1

C++ (gcc)

执行蛮力搜索。它的策略是贪婪地选择产生最少点数的矩形。尽管有违直觉，但这一策略似乎是有效的。为了使搜索有更多的变化，分支的大小也被限制在4。记忆是用来防止相同的板状态再次发生的(由于以不同的顺序应用相同的操作)。对于矩形和的计算，采用双指针方法从时间复杂度中去除一个线性因子。

它输出一个长度链-4元组(r0,c0,r1,c1)，其中r0,c0和r1,c1是左上角和右下角行列坐标。

用g++ -std=c++17 -O2编译。

#include <chrono>
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>

constexpr int ROWS = 10, COLS = 17;

// Program auto-exits by default after two minutes
constexpr int TIMEOUT = 120;

using Grid = std::array<std::array<int, COLS + 1>, ROWS + 1>;

struct Move { int cleared = 256, r0, c0, r1, c1; };

struct Sol {
    int score = 0;
    std::vector<Move> moves;
    Grid grid;
};

__gnu_pbds::gp_hash_table<long long, __gnu_pbds::null_type> cache;
std::vector<Move> moves;

const auto start = std::chrono::system_clock::now();

long long get_hash(Grid &grid) {
    long long hsh = 0;
    for (int r = 1; r <= ROWS; r++)
        for (int c = 1; c <= COLS; c++)
            hsh = hsh * 33 + grid[r][c] + 1;
    return hsh;
}

void print_solution(Sol &sol) {
    std::cout << sol.score << ": ";
    bool begin = true;
    for (auto &[_, r0, c0, r1, c1] : sol.moves) {
        if (!begin) std::cout << " -> ";
        begin = false;
        std::cout << "(" << r0 << ',' << c0 << ',' << r1 << ',' << c1 << ")";
    }
    std::cout << "\n";
}

void search(Grid grid, Sol &sol, int score = 0) {
    const auto now = std::chrono::system_clock::now();
    if (std::chrono::duration<double>(now - start).count() > TIMEOUT) {
        std::cout << TIMEOUT << " seconds elapsed. Exiting...\n";
        print_solution(sol);
        exit(EXIT_SUCCESS);
    }

    const long long hsh = get_hash(grid);
    if (cache.find(hsh) != cache.end())
        return;
    cache.insert(hsh);

    if (score > sol.score)
        sol = {score, moves, grid};

    Grid csum;
    for (int c = 1; c <= COLS; c++) csum[0][c] = 0;
    for (int r = 1; r <= ROWS; r++)
        for (int c = 1; c <= COLS; c++)
            csum[r][c] = csum[r - 1][c] + grid[r][c];

    Move mv0, mv1, mv2, mv3;
    for (int r0 = 1; r0 <= ROWS; r0++) {
        const auto &p0 = csum[r0 - 1];
        for (int r1 = r0; r1 <= ROWS; r1++) {
            const auto &p1 = csum[r1];

            int sum = 0;
            for (int c0 = 1, c1 = 0; c0 <= COLS; c0++) {
                while (c1 < COLS && sum < 10)
                    ++c1, sum += p1[c1] - p0[c1];

                if (sum == 10) {
                    int cleared = 0;
                    for (int r = r0; r <= r1; r++)
                        for (int c = c0; c <= c1; c++)
                            cleared += grid[r][c] != 0;

                    if (cleared < mv0.cleared)
                        mv3 = mv2, mv2 = mv1, mv1 = mv0, mv0 = {cleared, r0, c0, r1, c1};
                    else if (cleared < mv1.cleared)
                        mv3 = mv2, mv2 = mv1, mv1 = {cleared, r0, c0, r1, c1};
                    else if (cleared < mv2.cleared)
                        mv3 = mv2, mv2 = {cleared, r0, c0, r1, c1};
                    else if (cleared < mv3.cleared)
                        mv3 = {cleared, r0, c0, r1, c1};
                }
                sum -= p1[c0] - p0[c0];
            }
        }
    }

    for (const auto &m : {mv0, mv1, mv2, mv3}) {
        const auto &[cleared, r0, c0, r1, c1] = m;
        if (cleared == 256) break;

        auto ngrid = grid;
        for (int r = r0; r <= r1; r++)
            for (int c = c0; c <= c1; c++)
                ngrid[r][c] = 0;

        moves.push_back(m);
        search(ngrid, sol, score + cleared);
        moves.pop_back();
    }
}

int main() {
    // comment out this line to input via STDIN
    freopen("input.txt", "r", stdin);

    Grid grid;
    for (int r = 1; r <= ROWS; r++)
        for (int c = 1; c <= COLS; c++)
            std::cin >> grid[r][c];

    Sol sol;
    search(grid, sol);

    auto end = std::chrono::system_clock::now();
    print_solution(sol);
    std::cout << "Time elapsed: " << std::chrono::duration<double>(end - start).count() << "s\n";

    return 0;
}

在网上试试！

Answer 2

Python3,659字节：

from time import*
r,l=range,len
s=lambda v:[(t,x,y)for x in r(l(v))for y in r(x+1,l(v)+1)if(t:=sum(v[x:y]))<=10 and any(v[x:y])]
def f(b,p=[]):
 u=[]
 for x in r(l(b)):
  for q,w,e in s(b[x]):
   if q==10:u+=[(x,x+1,w,e)]
   elif n:=next((y for y in r(l(b)+1)if y>x and sum(sum(m[w:e])for m in b[x:y])==10),0):u+=[(x,n,w,e)]
 for g in sorted(u,key=lambda x:(x[1]-x[0])*(x[3]-x[2])):
  yield from f(b[:g[0]]+[d[:g[2]]+([0]*(g[3]-g[2]))+d[g[3]:] for d in b[g[0]:g[1]]]+b[g[1]:],p+[g])
 if not u:
  yield sum(sum(not i for i in j)for j in b),p
def e(b,s=120):
 t,r,w=time(),[],f(b)
 while time()-t<s and(n:=next(w,0)):r.append(n)
 return max(r,key=lambda x:x[0])

在网上试试！ (有50秒的最长时限)

输入

该解决方案包含一个列表，其中包含代表董事会的整数(即，最后一个示例中的[[9, 2, 2, 7, 6, 6, 1, 7, 1, 9, 7, 6, 9, 3, 8, 8, 3], ..., [3, 7, 3, 8, 1, 2, 1, 8, 1, 8, 3, 3, 2, 3, 2, 7, 4]] )。在TIO链接中，我在脚注中包含了一个Python函数，用于将板的字符串表示转换为所需的列表列表(请参见to_board)。

输入被传递给函数e，以及一个可选的时间限制，设置为这个挑战的最大值(两分钟)。在运行了最长时间之后，或者直到所有可能的板子都被生产出来，最优的结果才会被返回。

输出

e返回一个包含得分(第一个元素)的元组，以及生成分数的路径。路径包含每个移动(等于10的输入区域)，表示为元组。前两个元素构成垂直范围，后两个元素构成水平范围。例如，move (0, 1, 8, 10)从输入板的第一行选择1和9 ( 0到1的行，非包含的，索引8到10，非包含的)。

Note

时间限制的使用完全是为了产生尽可能高的分数。在没有时间限制的情况下，生成器的第一次100迭代的最大分数仍然会导致超过最佳截止值的值。

Answer 3

八度.纯随机方法

这应用移动随机，直到没有进一步的移动是可能的。然后尝试一个新的移动序列，直到达到一个时间限制。移动的最佳顺序是选择输出。

伪码：

1. 生成所有可能的矩形大小。
2. 随机排列均匀分布的矩形尺寸列表。将s设置为0。
3. 提高s。如果s超过了可能的矩形大小的数量(不可能进一步移动)：计算分数并转到步骤6。否则:继续正常。
4. 执行s-th大小的2D卷积。这将计算该大小的滑动矩形中的所有和。
5. 如果有等于10的和:随机选择一个均匀分布的。将板中的相应条目设置为0，存储移动，然后转到步骤2。否则:转到步骤3。
6. 如果目前的分数比目前最好的要好:更新最佳得分和移动列表。
7. 如果时间允许的话:进入步骤2(尝试一个新的移动序列)。其他:输出最佳得分和移动列表。

代码是一个函数，它以板和时间限制作为输入，并生成作为输出的得分和移动顺序(第三，可选输出给出尝试次数)。

板被定义为一个八度矩阵。移动顺序是四列矩阵，

[ up1 down1 left1 right1
  up2 down2 left2 right2
   ··· ]

up1 to down1是基于1的包含范围，在矩阵坐标中定义第一个矩形的垂直跨度；类似地，left1和right1定义它的水平跨度。up2等指第二步，以此类推。

function [score, moves, num_tries] = fruit_box(board_input, time_limit)

tic % start timer

target_sum = 10;

sizes_rect = {[], []};
[sizes_rect{:}] = ndgrid(1:size(board_input, 1), 1:size(board_input, 2));
sizes_rect = reshape(cat(3, sizes_rect{:}), [], 2).'; % each column defines a rectangle size
sizes_rect = sizes_rect(:, 2:end); % remove first column: [1; 1], which never gives a valid move

score = 0;
moves = [];
num_tries = 0;
while toc < time_limit
    num_tries = num_tries + 1;
    board_try = board_input; % initiallize board for current try
    moves_try = []; % initiallize moves for current try
    done = false;
    while ~done
        done = true;
        for size_rect = sizes_rect(:,randperm(end))
            sums = conv2(board_try, ones(size_rect.'), 'valid');
            [up, left] = find(sums==target_sum);
            if up % at least one move is possible
                ind = randi(numel(up));
                moves_try(end+1, :) = [up(ind) up(ind)+size_rect(1)-1 left(ind) left(ind)+size_rect(2)-1]; % store move
                board_try(moves_try(end,1):moves_try(end,2), moves_try(end,3):moves_try(end,4)) = 0; % set to zero
                done = false; % further moves may be possible in current try
                break
            end
        end
    end
    score_try = nnz(board_try==0); % the score is the number of zeros
    if score_try > score % update solution if better
        score = score_try;
        moves = moves_try;
    end
end

在网上试试！ (55秒限)。