Fruit Box

apple.py

import random

# create game
seed = 42
n_row = 10
n_col = 17
applesum = 10  # sum(apples)=10
applenum = 10  # 1...9

def generate_game(rng=None):
    """generates game matrix randomly
    matrix size: n_row x n_col
    valstats[i] == j means the count of i is j.
    rejection sampling: sum of the numbers in the matrix is divisible by applesum
    returns matrix, valstats
    """
    
    if rng is None:
        rng = random

    condition = False
    while not condition:
        matrix = [[0]*n_col for _ in range(n_row)]
        valstats = [0]*applenum
    
        for i in range(n_row):
            for j in range(n_col):
                c = rng.randrange(1,applenum)
                matrix[i][j] = c
                valstats[c] += 1
        condition = sum([i*e for i,e in enumerate(valstats)]) % applesum == 0

    return matrix, valstats


def act(x1,x2,y1,y2,matrix):  # [x1,x2], [y1,y2]
    """remove apple in matrix[x1:x2+1][y1:y2+1]
    return the list of removed apples (x, y, value)"""
    # check validity
    sums = 0
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            sums += matrix[i][j]
    if sums != applesum:
        return 0
    # update
    removals = []
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            c = matrix[i][j]
            if c!=0:
                matrix[i][j]=0
                removals += [(i,j,c)]
    return removals


def unact(removals, matrix):
    """restore apple in matrix
    (x,y,c) <-> matrix[x][y] = c"""
    # check validity
    for i,j,c in removals:
        if matrix[i][j] != 0:
            return 1
    # update
    for i,j,c in removals:
        matrix[i][j] = c
    return 0


# agents
def search0(matrix, *, rng=None):
    """search rectangle in priority of row coord, column coord, small row, small column
    search with branch cutting
    input matrix (n_row x n_col)
    input rng (unused, deterministic)
    output (x1, x2, y1, y2) both inclusive, or None if rectangle not found
    """
    for x in range(n_row):
        for y in range(n_col):
            for dx in range(n_row):
                csum = 0  # area sum
                cx = x+dx  # set row range
                if cx >= n_row:  # boundary check 
                    break
                for dy in range(n_col):
                    cy = y+dy  # set column range
                    if cy >= n_col:  # boundary check
                        break
                    for i in range(x, cx+1):  # add column area
                        csum += matrix[i][cy]
                    if dy==0 and csum==0:  # duplicate check by boundary
                        break
                    if csum >= applesum:  # cutoff searching
                        if csum == applesum:  # match
                            return x, cx, y, cy
    return None


def search_base(matrix, *, rng=None, key=None, future_actions=False):
    """search rectangle in priority of (count elem, count sumsquare, max_actions, random tiebreak),
    remove duplicates
    search with branch cutting
    input matrix (n_row x n_col)
    output (x1, x2, y1, y2) both inclusive, or None if rectangle not found
    """
    def search_cands(matrix):
        cands = []
        for x in range(n_row):
            for y in range(n_col):
                for dx in range(n_row):
                    csum = 0  # area sum
                    nelems = [0]*applenum  # area num
                    cx = x+dx  # set row range
                    if cx >= n_row:  # boundary check 
                        break
                    for dy in range(n_col):
                        cy = y+dy  # set column range
                        if cy >= n_col:  # boundary check
                            break
                        for i in range(x, cx+1):  # add column area
                            csum += matrix[i][cy]
                            nelems[matrix[i][cy]] += 1
                        if dy==0 and csum==0:  # duplicate check by boundary
                            break
                        if csum >= applesum:  # cutoff searching
                            if csum == applesum:  # match
                                # duplicate check, only rows
                                row1=0
                                row2=0
                                for j in range(y, cy+1):
                                    row1 += matrix[x][j]
                                    row2 += matrix[cx][j]
                                if row1!=0!=row2:  # add element if not duplicate
                                    factor = (sum(nelems[1:]), -sum([i*i*e for i,e in enumerate(nelems)]), (dx+1)*(dy+1))
                                    cands += [(x, cx, y, cy, factor)]
                            break
        return cands
    
    if rng is None:
        rng = random
    cands = search_cands(matrix)
    if cands:
        # _, _, _, _, max_factor = min(cands, key=lambda p: p[4])
        top_cands = []
        for cand in cands:
            x, cx, y, cy, factor = cand
            # reeval
            if future_actions:
                ops = act(x, cx, y, cy, matrix)
                next_cands = search_cands(matrix)
                unact(ops, matrix)
                new_factor = (*factor, -len(next_cands), rng.random())
            else:
                new_factor = (*factor, rng.random())
            if key is not None:
                new_factor = key(new_factor)
            top_cands += [(x, cx, y, cy, new_factor)]
        x,cx,y,cy,factor = min(top_cands, key=lambda p: p[4])
        return x, cx, y, cy
    return None


def run_test(algo, matrix, n_trial=None, *, rng=None, kwargs=None):
    if n_trial is None:
        n_trial = 1
    if n_trial != 1:
        print(f'random trial {n_trial}')
    if rng is None:
        rng = random
    if kwargs is None:
        kwargs = {}
    count_best = 0
    depth_at_best = 0
    mat_at_best = None
    count_list = []
    depth_list = []
    
    sa_i = algo
    for i in range(n_trial):
        mat_i = [e[:] for e in matrix]
        
        # create new rng for each trial.
        rng2 = random.Random(rng.random())
        count = 0
        depth = 0
        while True:
            coords = sa_i(mat_i,rng=rng2,**kwargs)
            if coords is None:
                break
            ops = act(*coords, mat_i)
            assert len(ops)!=0
            count += len(ops)
            depth += 1
        
        count_list += [count]
        depth_list += [depth]
        if (count, -depth) > (count_best, -depth_at_best):
            count_best = count
            depth_at_best = depth
            mat_at_best = mat_i
    if n_trial > 1:
        print('avg score', sum(count_list)/n_trial, 'min_score', min(count_list))
        print('best score', count_best, 'depth at best', depth_at_best)
    else:
        print('score', count_best, 'depth', depth_at_best)

    for row in mat_at_best:
        print(*row)

    return count_list, depth_at_best


if __name__=="__main__":
    # run
    n_boards = 10
    n_trial = 20
    
    algos = [
    # deterministic algos:
    # select first
    ("greed", search0, 1, {}),
    # random algos:
    # random
    # elem, random
    # sumsquare, random
    # area, random
    # max actions, random
    ("rand ", search_base, n_trial, {"key":(lambda x:x[3])}),
    ("elem ", search_base, n_trial, {"key":(lambda x:(x[0],x[3]))}),
    ("sumsq", search_base, n_trial, {"key":(lambda x:(x[1],x[3]))}),
    ("area ", search_base, n_trial, {"key":(lambda x:(x[2],x[3]))}),
    ("futur", search_base, n_trial, {"future_actions":True, "key":(lambda x:(x[3],x[4]))}),
    ("mixed", search_base, n_trial, {"future_actions":True, "key":(lambda x:(x[3],x[1],x[0],x[2],x[4]))})
    ]
    
    # create rng for board and test
    board_rng = random.Random(seed)
    test_rng = random.Random(seed)
    
    stat_li = [[] for _ in range(len(algos))]
    for j in range(n_boards):
        matrix, valstats = generate_game(board_rng)
        print(f"board {j+1}")
        for row in matrix:
            print(*row)
        
        print('stats ', *valstats[1:], 'total', sum([i*e for i,e in enumerate(valstats)]))
        
        test_seed = test_rng.random()  # use same rng seed
        for i, e in enumerate(algos):
            algo_name, algo_i, n_trial, kwargs = e
            mat_i = [e[:] for e in matrix]
            print(f'algorithm {i+1}: {algo_name}')
            # initialize same new rng for each algo
            rng2 = random.Random(test_seed)
            cnt_li, _ = run_test(algo_i, mat_i, n_trial=n_trial, rng=rng2, kwargs=kwargs)
            best, worst, avg = max(cnt_li), min(cnt_li), sum(cnt_li)/len(cnt_li)
            stat_li[i] += [(best, worst, avg)]
    
    idnames = ["best       ", "worst      ", "avg        "]
    print("## Algo ", *idnames, sep="\t")
    for i in range(len(algos)):
        values = []
        sds = []
        for k in range(len(idnames)):
            values += [sum(stat_li[i][j][k] for j in range(n_boards))/n_boards]
        for k in range(len(idnames)):
            sds += [(sum(stat_li[i][j][k]**2 for j in range(n_boards))/n_boards - values[k]**2)**0.5]
        print(f"{i+1:02d} {algos[i][0]}", *[f"{v:.1f}({sd:.1f})" for v,sd in zip(values,sds)], sep="\t")

apple_brute.py

import random

# create game
seed = 42
n_row = 10
n_col = 17
applesum = 10  # sum(apples)=10
applenum = 10  # 1...9


def generate_game(rng=None):
    """generates game matrix randomly
    matrix size: n_row x n_col
    valstats[i] == j means the count of i is j.
    rejection sampling: sum of the numbers in the matrix is divisible by applesum
    returns matrix, valstats
    """
    
    if rng is None:
        rng = random

    condition = False
    while not condition:
        matrix = [[0]*n_col for _ in range(n_row)]
        valstats = [0]*applenum
    
        for i in range(n_row):
            for j in range(n_col):
                c = rng.randrange(1,applenum)
                matrix[i][j] = c
                valstats[c] += 1
        condition = sum([i*e for i,e in enumerate(valstats)]) % applesum == 0

    return matrix, valstats


def act(x1,x2,y1,y2,matrix):  # [x1,x2], [y1,y2]
    """remove apple in matrix[x1:x2+1][y1:y2+1]
    return the list of removed apples (x, y, value)"""
    # check validity
    sums = 0
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            sums += matrix[i][j]
    if sums != applesum:
        return 0
    # update
    removals = []
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            c = matrix[i][j]
            if c!=0:
                matrix[i][j]=0
                removals += [(i,j,c)]
    return removals


def unact(removals, matrix):
    """restore apple in matrix
    (x,y,c) <-> matrix[x][y] = c"""
    # check validity
    for i,j,c in removals:
        if matrix[i][j] != 0:
            return 1
    # update
    for i,j,c in removals:
        matrix[i][j] = c
    return 0



def search_cands(matrix):
    cands = []
    for x in range(n_row):
        for y in range(n_col):
            for dx in range(n_row):
                csum = 0  # area sum
                nelems = [0]*applenum  # area num
                cx = x+dx  # set row range
                if cx >= n_row:  # boundary check 
                    break
                for dy in range(n_col):
                    cy = y+dy  # set column range
                    if cy >= n_col:  # boundary check
                        break
                    for i in range(x, cx+1):  # add column area
                        csum += matrix[i][cy]
                    if dy==0 and csum==0:  # duplicate check by boundary
                        break
                    if csum >= applesum:  # cutoff searching
                        if csum == applesum:  # match
                            # duplicate check, only rows
                            row1=0
                            row2=0
                            for j in range(y, cy+1):
                                row1 += matrix[x][j]
                                row2 += matrix[cx][j]
                            if row1!=0!=row2:  # add element if not duplicate
                                cands += [(x, cx, y, cy)]
                        break
    return cands


def run_dfs(matrix):
    def dfs(count, depth):
        nonlocal codebook,matrix,encode,visit,count_best,depth_at_best, mat_at_best

        # print(len(visit), depth, count, count_best)
        cands = search_cands(matrix)
        if len(cands)==0:
            if count > count_best:
                count_best = count
                depth_at_best = depth
                mat_at_best = [e[:] for e in matrix]
                print(len(visit), count_best)
            return
        for cand in cands:
            ops = act(*cand, matrix)
            assert len(ops)!=0
            for i,j,v in ops:
                encode ^= codebook[i][j][v]
            if encode not in visit:
                visit.add(encode)
                dfs(count + len(ops), depth + 1)
            unact(ops, matrix)
            for i,j,v in ops:
                encode ^= codebook[i][j][v]
    
    codebook = [[ [0] + [random.randrange(2**64) for _ in range(9)] 
                  for _ in range(n_col)] for _ in range(n_row)]
    
    mat_i = [e[:] for e in matrix]
    encode = 0
    for i in range(n_row):
        for j in range(n_col):
            v=mat_i[i][j]
            encode ^= codebook[i][j][v]

    visit = {encode}
    count_best = 0
    depth_at_best = 0
    mat_at_best = None
    dfs(0, 0)
    print('score', count_best, 'depth', depth_at_best)


if __name__=="__main__":
    # create rng for board and test
    board_rng = random.Random(seed)
    
    matrix, valstats = generate_game(board_rng)
    print(f"board")
    for row in matrix:
        print(*row)
    
    print('stats ', *valstats[1:], 'total', sum([i*e for i,e in enumerate(valstats)]))
    
    # bruteforce
    run_dfs(matrix)