Play the Fruit Box Game

Question

Play the Fruit Box Game

Intro

Fruit Box is a game consisting of a 10x17 grid of numbers, each between 1 and 9, where the goal is to clear as many numbers as possible in a two-minute time window. In order to clear numbers, one selects a rectangle aligned with the grid, and if the numbers inside of it sum to 10, they are cleared off the field. At the start of the game, the grid is randomly populated, with the only requirement being that the sum of all numbers in the field is a multiple of 10. Several examples are shown below:

This is an example starting field, with several, but not all, valid possible clears shown.

This is a field partway through the game, with new possible clears being opened as a result of previous numbers being taken off the field. Notice that, for example, if the 6-3-1 rectangle in the bottom left were cleared, it would open the possibility to clear two 9-1 pairs horizontally which are currently blocked.

Perhaps the easiest way to familiarize yourself with the game is to play several rounds, which can be done here: Fruit Box

The Challenge

If you haven't guessed by now, the challenge is to write a program which plays the above game as optimally as possible, where optimal means clearing the most numbers.

Input

The input will be the starting grid of numbers. It can be taken in any reasonable representation, meaning you can take it in as a string, an array of 10 17-length integers, a 2D array of 170 integers, or any other similar form. Use your best judgement as to what reasonable means, but in the spirit of the challenge, it should be some representation of the starting grid of numbers. Please specify in your answer exactly how input should be passed.

Output

The output should be the final score achieved (numbers cleared), as well as the list of moves to achieve this score. Again, the exact form of this output is up to you, but it should be such that given the list of moves, one can unambiguously replay the game from the same starting configuration to end up at the given final score. For example, one could output the top left and bottom right coordinate of each rectangle cleared in order.

Beyond the above, the normal input/output rules, as well as forbidden loopholes apply. If you are unsure about any of the specifications, leave a comment and I will clarify.

Scoring

The score on a particular board is given by how many numbers are cleared over the course of the game. For example, if there are 14 numbers left at the end of the game, regardless of their values, the final score will be 170-14 = 156.

Since each starting board will have a different optimal score, all answers will be run on the same set of 10 boards for evaluation, which I will keep hidden. At the bottom of this post, I will maintain a leaderboard of the current top submissions, based on their average performance across these 10 boards. The answer which is at the top of the leaderboard one month after the first submission will be accepted.

Edit: If the algorithm is not deterministic, the average-of-5 will be used for each of the 10 boards.

Other Rules

• Since the original game gives you 2 minutes, the submission must run in under 2 minutes on my machine (a 4 core, 2017 MacBook Pro with 16GB of RAM). A small amount of leeway will be given to account for typical variations.

• You must use a language which is free to use and can be found online. (This should not disqualify any typically-used languages)

Leaderboard

One month has passed, and the leaderboard is now closed. Congratulations to dingledooper for taking the win!

1. dingledooper: 147.2 Points
2. M Virts: 129.0 Points
3. Luis Mendo: 126.0 Points
4. Ajax1234: 119.6 Points
5. Richard Neumann: 118.0 Points

Example Boards

Here are 3 valid example boards. Each board also includes the score achieved by naively clearing rectangles in order until none remain, as a lower bound on the possible score.

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)

Performs a brute force search. Its strategy is to greedily choose rectangles that yield the least amount of points. Although counter-intuitive, this strategy is seemingly effective. To give the search more variation, the branch size is also limited to 4. Memoization is used to prevent the same board state from re-occurring (due to applying the same operations in a different order). As for calculating the rectangle sums, a two-pointer approach is taken to remove a linear factor from the time complexity.

It outputs a chain of length-4 tuples (r0,c0,r1,c1), where r0,c0 and r1,c1 are the top-left and bottom-right row-column coordinates.

Compiled with 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;
}

Try it online!

Answer 2

Python3, 659 bytes:

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])

Try it online! (with a 50 second maximum time limit)

Input

This solution takes in a list of lists with the integers representing the board (i.e [[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]] for the last example). In the TIO link, I have included in the footer a Python function to convert a string representation of the board to the required list of lists (see to_board).

The input is passed to the function e, along with an optional time limit, set to the maximum for this challenge (two minutes). After running for the maximum period of time, or until all possible boards have been produced, the optimal result is returned.

Output

e returns a tuple containing the score (the first element), and the path to produce the score. The path contains each move (the area of the input that sums to 10), which is represented as a tuple. The first two elements form the vertical range, and the last two elements comprise the horizontal range. For example, the move (0, 1, 8, 10) selects the 1 and 9 from the first row of the input board (rows 0 to 1, noninclusive, with indices 8 to 10, noninclusive).

Note

The use of the time limit is solely to produce as high a score as possible. Without a time limit, the maximum score of the first 100 iterations of the generator will still result in a value above the optimal cutoff.

Answer 3

Octave. Purely random approach

This applies moves randomly until no further moves are possible. Then tries a new sequence of moves until a time limit is reached. The best sequence of moves is chosen output.

Pseudo-code:

1. Generate all possible rectangle sizes.
2. Permute the list of rectangle sizes randomly with uniform distribution. Set s to 0.
3. Increase s. If s exceeds the number of possible rectangle sizes (no further moves are possible): compute score and go to step 6. Else: continue normally.
4. Perform 2D convolution with the s-th size. This computes all sums in a sliding rectangle of that size.
5. If there are sums that equal 10: choose one randomly with uniform distribution. Set the corresponding entries in the board to 0, store the move, and go to step 2. Else: go to step 3.
6. If the current score is better than the best so far: update best score and list of moves.
7. If time allows: go to step 2 (to try a new sequence of moves). Else: output best score and list of moves.

The code is a function that takes the board and time limit as inputs, and produces the score and sequence of moves as outputs (a third, optional output gives the number of tries).

The board is defined as an Octave matrix. The sequence of moves is a 4-column matrix,

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

up1 to down1 is the 1-based, inclusive range that defines the vertical span of the first rectangle in matrix coordinates; and similarly left1 and right1 define its horizontal span. up2 etc refer to the second move, and so on.

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

Try it online! (with 55-second limit).

Answer 4

Python, 2013 bytes

Uses numpy and ffts to generate moves by convolution, then starts a depth first search of all possible moves, with a timeout to limit the search (definitely not terminating any time soon without that). Caches move generation and step results based on the input board.

Prefers small moves first to knock out large numbers. I also tried random weights but it doesn't seem to do well consistently.

I'm using a list of rows (lists) as input, should also work with tuples and other iterables.

import time
import random
import numpy as np
import sys
sys.setrecursionlimit(10000)

def go(b):
    timeout=115 # seconds, set to 5 on ATO
    
    r = len(b)
    c = len(b[0])
    
    fftshape = (2*r,2*c)
    shapes = [(i,j) for i in range(1,r) for j in range(1,c) if i*j!=1]
    kernels = [np.ones(s) for s in shapes]
    ffts = np.stack([np.conj(np.fft.fft2(k,fftshape)) for k in kernels],axis=2)

    
    def _getmoves(b):
        ba = np.asarray(b)
        kres = np.real(np.fft.ifft2(((np.fft.fft2(ba,fftshape)[:,:,np.newaxis]*ffts)),axes=(0,1)))
        res = [kres[:,:,i] for i in range(kres.shape[2])]
        ix = [np.argwhere(np.all(np.stack((r>9.5,r<10.5),axis=2),axis=2)) for r in res]
        moves = [((i[0],i[0]+s[0]),(i[1],i[1]+s[1])) for s,ix in zip(shapes,ix) for i in ix if i[0]+s[0] <= ba.shape[0] and i[1]+s[1] <= ba.shape[1] ]
        return moves

    movec = {}
    def getmoves(b):
        if b not in movec:
            movec[b] = _getmoves(b)
    #         print("miss")

        return movec[b]   

    def _step(b):
        nonlocal timeout
        nonlocal start_time
        moves = getmoves(b)
        ba = np.asarray(b)
        if moves and not time.time() - start_time  > timeout:
            rl=[]
            best=(0,)
            for m in sorted(moves,key=lambda m:(m[0][1]-m[0][0])*(m[1][1]-m[1][0])):
                bac = ba.copy()
                bac[m[0][0]:m[0][1],m[1][0]:m[1][1]]=0;
                score,bar,ml=step((*map(tuple,bac.tolist()),));
                if score > best[0]:
                    best = (score,bar,[m]+ml)
            return best    
        else:
            score = (ba.shape[0]*ba.shape[1])-(ba>0).sum()
            return score,ba,[]

    stepc = {}
    def step(b):
        if b not in stepc:
            stepc[b] = _step(b)
        return stepc[b]
    
    start_time = time.time()
    score,baf,movelist = step((*map(tuple,b),))
    print(f"Score: {score}")
    print(movelist)
    print(baf)
    return score,movelist,baf

Attempt This Online!

Answer 5

C++

#include <algorithm>
using std::sort;

#include <functional>
using std::reference_wrapper;

#include <initializer_list>
using std::initializer_list;

#include <iostream>
using std::cout;
using std::ostream;

#include <numeric>
using std::accumulate;

#include <vector>
using std::vector;

struct Cell {
    unsigned short number;

    explicit Cell(unsigned short number)
        : number(number)
    {
    }

    friend unsigned short operator+(unsigned short lhs, Cell const & cell)
    {
        return lhs + cell.number;
    }

    friend ostream & operator<<(ostream & out, Cell const & cell)
    {
        out << cell.number;
        return out;
    }
};

struct Point {
    size_t x, y;

    Point(size_t x, size_t y)
        : x(x), y(y)
    {
    }

    friend ostream & operator<<(ostream & out, Point const & point)
    {
        out << point.x << "x" << point.y;
        return out;
    }
};

struct Frame {
    Point start, end;

    Frame(Point start, Point end)
        : start(start), end(end)
    {
    }

    friend ostream & operator<<(ostream & out, Frame const & step)
    {
        out << step.start << " -> " << step.end;
        return out;
    }
};

struct Result {
    vector<Frame> steps;
    unsigned short score;

    Result(vector<Frame> const & steps, unsigned short score)
        : steps(steps), score(score)
    {
    }

    friend ostream & operator<<(ostream & out, Result const & result)
    {
        for (auto const & step : result.steps)
            out << step << "\n";

        out << "Score: " << result.score;
        return out;
    }
};

auto sum(vector<reference_wrapper<Cell>> const & selection)
{
    return accumulate(selection.begin(), selection.end(), 0);
}

auto getWeight(vector<reference_wrapper<Cell>> const & selection)
{
    unsigned int weight = 0;

    for (Cell const & cell : selection)
        weight += cell.number << cell.number;

    return weight / selection.size();
}

class Grid {
private:
    vector<vector<Cell>> cells;
    unsigned short targetValue;
public:
    Grid(initializer_list<initializer_list<unsigned short>> list, unsigned short targetValue)
        : targetValue(targetValue)
    {
        for (auto const & inner : list) {
            vector<Cell> row;

            for (auto const &  number : inner)
                row.emplace_back(number);

            cells.push_back(row);
        }
    }
    Grid(initializer_list<initializer_list<unsigned short>> list)
        : Grid(list, 10)
    {
    }

    [[nodiscard]] auto size() const
    {
        return cells.size() * cells.at(0).size();
    }

    [[nodiscard]] auto startPoints() const
    {
        vector<Point> points;

        for (auto y = 0; y < cells.size(); y++)
            for (auto x = 0; x < cells.at(y).size(); x++)
                points.emplace_back(x, y);

        return points;
    }

    [[nodiscard]] auto endPoints(Point const & startPoint) const
    {
        vector<Point> points;

        for (auto y = startPoint.y; y < cells.size(); y++)
            for (auto x = startPoint.x; x < cells.at(y).size(); x++)
                points.emplace_back(x, y);

        return points;
    }

    [[nodiscard]] auto getFrames() const
    {
        vector<Frame> frames;

        for (auto const & start : startPoints())
            for (auto const & end : endPoints(start))
                frames.emplace_back(start, end);

        return frames;
    }

    auto getCells(Frame const & step)
    {
        vector<reference_wrapper<Cell>> selection;

        for (unsigned short y = step.start.y; y <= step.end.y; y++)
            for (unsigned short x = step.start.x; x <= step.end.x; x++)
                selection.emplace_back(cells.at(y).at(x));

        return selection;
    }

    [[nodiscard]] auto filterFrames(vector<Frame> const & frames)
    {
        vector<Frame> result;

        for (auto const & frame : frames)
            if (sum(getCells(frame)) == targetValue)
                result.push_back(frame);

        return result;
    }

    [[nodiscard]] unsigned short numbersLeft() const
    {
        unsigned short counter = 0;

        for (auto const & row : cells)
            for (auto const & cell : row)
                if (cell.number != 0)
                    counter++;

        return counter;
    }

    void sortFrames(vector<Frame> & frames)
    {
        sort(frames.begin(), frames.end(), [this] (Frame const & lhs, Frame const & rhs) {
            return getWeight(getCells(lhs)) > getWeight(getCells(rhs));
        });
    }

    bool reduceCells(vector<reference_wrapper<Cell>> const & selection)
    {
        if (sum(selection) == targetValue) {
            for (Cell & cell : selection)
                cell.number = 0;

            return true;
        }

        return false;
    }

    auto reduce(Frame const & frame)
    {
        return reduceCells(getCells(frame));
    }

    friend ostream & operator<<(ostream & out, Grid const & grid)
    {
        for (auto const & row : grid.cells) {
            for (auto const & cell : row)
                out << cell << " ";

            out << " \n";
        }

        return out;
    }
};

auto resolve(Grid & grid)
{
    vector<Frame> log, steps;

    while (true) {
        auto frames = grid.getFrames();
        auto candidates = grid.filterFrames(frames);

        if (candidates.empty())
            break;

        grid.sortFrames(candidates);
        auto candidate = candidates.at(0);

        if (grid.reduce(candidate))
            log.push_back(candidate);
    }

    return Result(log, grid.size() - grid.numbersLeft());
}

int main() {
    Grid grid1 = {
        {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}
    };
    Grid grid2 ={
        {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}
    };
    Grid grid3 = {
        {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}
    };
    vector<reference_wrapper<Grid>> grids = {grid1, grid2, grid3};
    unsigned short gridNumber = 0;

    for (auto & grid : grids) {
        cout << "Grid #" << ++gridNumber << "\n";
        auto result = resolve(grid);
        cout << result << "\n";
        cout << grid << "\n";
    }
}

Try it online

The algorithm weighs the selections based on their amount of high numbers and size.

Answer 6

Rust

Uses breadth-first beam search, with a heuristic evaluation based on greedily eliminating as many entries as possible while ignoring newly-created boxes. Solves each board in parallel. You can reduce beam_size in solve if you need to in order to meet the time budget (I know it should really be a command-line flag).

src/main.rs

use fnv::FnvHashMap;
use rayon::prelude::*;

type Fruit = [[i16; 17]; 10];
type Rect = [u8; 4];
type ClearedMask = [u8; 22];

fn check_entry(mask: &ClearedMask, i: usize, j: usize) -> bool {
    let k = 17 * i + j;
    return (mask[k / 8] & (1 << (k % 8))) == 0
}

fn remove_entry(mask: &mut ClearedMask, i: usize, j: usize) {
    let k = 17 * i + j;
    mask[k / 8] |= 1 << (k % 8);
}

fn find_rects(output_rects: &mut Vec<(Rect, u8)>, mask: &ClearedMask, fruit: &Fruit, cum_sums: &mut [[i16; 18]; 11]) {
    for i in 0..11 {
        cum_sums[i][0] = 0;
    }
    for j in 0..18 {
        cum_sums[0][j] = 0;
    }
    for i in 0..10 {
        for j in 0..17 {
            cum_sums[i + 1][j + 1] = if check_entry(mask, i, j) {fruit[i][j]} else {0};
        }
    }
    for i in 0..10 {
        for j in 0..17 {
            cum_sums[i + 1][j + 1] += cum_sums[i][j + 1];
        }
    }
    let mut table = [0u16; 1530];
    for i0 in 0..10 {
        for i1 in i0..10 {
            let mut s = 0i16;
            let k = ((i0 << 4) | i1) as u16;
            for j1 in 0..17 {
                table[s as usize] = (k << 8) | (j1 as u16);
                unsafe {
                    s += cum_sums.get_unchecked(i1 + 1).get_unchecked(j1 + 1) -
                         cum_sums.get_unchecked(i0).get_unchecked(j1 + 1);
                }
                if s < 10 {
                    continue;
                }
                let j0 = unsafe {
                    *table.get_unchecked((s - 10) as usize) as usize
                };
                if (j0 >> 8) as u16 != k {
                    continue;
                }
                let j0 = j0 & 255;
                let r = [i0 as u8, j0 as u8, i1 as u8, j1 as u8];
                let mut a = 0;
                for i2 in i0..=i1 {
                    for j2 in j0..=j1 {
                        if check_entry(mask, i2, j2) {
                            a += 1;
                        }
                    }
                }
                output_rects.push((r, a))
            }
        }
    }
}

fn heuristic(rects: &Vec<(Rect, u8)>) -> u16 {
    let mut collision_info = Vec::with_capacity(rects.len());
    for _ in 0..rects.len() {
        collision_info.push((0u128, 0u16));
    }
    let mut s = 0;
    for idx0 in 0..rects.len() {
        let [_, j00, i10, j10] = rects[idx0].0;
        for idx1 in (idx0 + 1)..rects.len() {
            let [i01, j01, _, j11] = rects[idx1].0;
            if i01 > i10 {
                break;
            }
            if (j00 <= j11) & (j10 >= j01) {
                collision_info[idx0].0 |= 1 << idx1;
                collision_info[idx1].0 |= 1 << idx0;
                collision_info[idx0].1 += 1;
                collision_info[idx1].1 += 1;
            }
        }
    }
    let mut used = 0u128;
    let mut sort_idx: Vec<(u32, usize)> = (0..rects.len()).map(|i| (((collision_info[i].1 as u32) << 8) | (255 - rects[i].1) as u32, i)).collect();
    sort_idx.sort();
    for &(_, i) in sort_idx.iter() {
        if used & (1 << i) != 0 {
            continue;
        }
        used |= collision_info[i].0;
        s += rects[i].1 as u16;
    }
    return s;
}

fn solve(fruit: &Fruit) -> (Vec<Rect>, u16) {
    let mut cum_sums = [[0i16; 18]; 11];
    let mut output_rects = Vec::new();
    let mut heuristic_rects = Vec::new();
    let mut queue = Vec::new();
    let mut next_queue = Vec::new();
    let mut parent_map: FnvHashMap<ClearedMask, (ClearedMask, Rect)> = FnvHashMap::default();
    let rng = 18;
    queue.push((0, 0, rng, [0u8; 22]));
    let mut max_cleared = 0;
    let beam_size = 6500;
    let mut best_mask = [0u8; 22];
    while !queue.is_empty() {
        for (_, cleared, _, mask) in queue.iter() {
            find_rects(&mut output_rects, &mask, &fruit, &mut cum_sums);
            for (r, a) in output_rects.iter() {
                let mut mask1 = mask.clone();
                for i in r[0]..=r[2] {
                    for j in r[1]..=r[3] {
                        remove_entry(&mut mask1, i as usize, j as usize);
                    }
                }
                if parent_map.contains_key(&mask1) {
                    continue;
                }
                parent_map.insert(mask1, (*mask, *r));
                let cleared1 = cleared + (*a as u16);
                find_rects(&mut heuristic_rects, &mask1, &fruit, &mut cum_sums);
                let h = heuristic(&heuristic_rects);
                heuristic_rects.clear();
                next_queue.push((cleared1 + h, cleared1, rng, mask1));
                if cleared1 > max_cleared {
                    max_cleared = cleared1;
                    best_mask = mask1;
                }
            }
            output_rects.clear();
        }
        std::mem::swap(&mut queue, &mut next_queue);
        if queue.len() > beam_size {
            queue.sort_by(|p, q| q.cmp(p));
            queue.truncate(beam_size);
        }
        next_queue.clear();
    }
    let mut moves = Vec::new();
    let mut mask = best_mask;
    while let Some((parent_mask, r)) = parent_map.get(&mask) {
        moves.push(*r);
        mask = *parent_mask;
    }
    return (moves, max_cleared)
}

fn main() {
    let fruit0 = [
        [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],
    ];
    let fruit1 = [
        [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],
    ];
    let fruit2 = [
        [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],
    ];
    let boards = [&fruit0, &fruit1, &fruit2];
    let results: Vec<(Vec<Rect>, u16)> = boards.into_par_iter().map(solve).collect();
    for (board_index, (fruit, (moves, score))) in boards.iter().zip(results.iter()).enumerate() {
        println!("Board {:?}: {:?} fruit cleared!\n\n", board_index, score);
        let mut mask1 = [0; 22];
        for r in moves.iter().rev() {
            for i in r[0]..=r[2] {
                for j in r[1]..=r[3] {
                    remove_entry(&mut mask1, i as usize, j as usize);
                }
            }
            println!("({:?}, {:?}), ({:?}, {:?})\n\n", r[0], r[1], r[2], r[3]);
            for i in 0..10 {
                for j in 0..17 {
                    let s = if check_entry(&mask1, i, j) {fruit[i][j]} else {0};
                    print!("{:?} ", s);
                }
                println!("");
            }
        }
    }
    println!("");
    for (board_index, (_, score)) in results.iter().enumerate() {
        println!("Board {:?}: {:?} fruit cleared!\n", board_index, score);
    }
}

Cargo.toml

[package]
name = "fruitbox"
version = "0.1.0"
edition = "2018"

[dependencies]
rayon = "1.5.1"
fnv = "1.0.3"