Skip to content

Instantly share code, notes, and snippets.

@jgs03177

jgs03177/analysis1.py

Last active July 6, 2025 00:23
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jgs03177/ac76dc9c6ddde3f0aa1c47e9c714af1d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jgs03177/ac76dc9c6ddde3f0aa1c47e9c714af1d to your computer and use it in GitHub Desktop.
Download ZIP
Fruit Box
Raw
analysis1.py
# analysis
# board, trial
# 2000, 25
algos = ["rand ", "elem ", "sumsq", "area "]
stats = []
for i in range(len(algos)):
filename = f"{algos[i]}_raw.csv"
with open(filename, "r") as f:
# f.readline() # avg_best,avg_worst,avg_mean
board=[]
for l in f:
val = list(map(float, l.strip().split(',')))
board += [(val)]
stats += [board]
stat_li = []
for i in range(len(algos)):
tmp1 = []
for j in range(len(stats[i])):
cnt_li = stats[i][j]
best, worst, avg = max(cnt_li), min(cnt_li), sum(cnt_li)/len(cnt_li)
tmp1 += [(best,worst,avg)]
stat_li += [tmp1]
# print(stats)
n_algs = len(stats)
n_boards = len(stats[0])
n_trials = len(stats[0][0])
print("Experiment @", f"{n_algs} algorithms, {n_boards} boards, {n_trials} trials")
print("============================")
idnames = ["avg best ", "avg worst ", "avg mean "]
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]}", *[f"{v:.1f}({sd:.1f})" for v,sd in zip(values,sds)], sep="\t")
print("## Algo ", "max best", "min worst", sep="\t")
for i in range(len(algos)):
values = []
sds = []
values += [max(stat_li[i][j][0] for j in range(n_boards))]
values += [min(stat_li[i][j][1] for j in range(n_boards))]
print(f"{i+1:02d} {algos[i]}", *[f"{v:.1f}" for v in values], sep="\t")
import numpy as np
import scipy
stat_np = np.array(stat_li)
idnames = ["avg best ", "avg worst ", "avg mean "]
print("============================")
print("Avg score difference (paired t-test, pvalue)")
print("## Algo ", *idnames, sep="\t")
for i in range(len(algos)):
for i2 in range(i+1, len(algos)):
values = []
tests = []
for k in range(len(idnames)):
values += [np.mean(stat_np[i,:,k]-stat_np[i2,:,k])]
for k in range(len(idnames)):
test = scipy.stats.ttest_rel(stat_np[i,:,k], stat_np[i2,:,k])
tests += [test]
print(f"{algos[i]} vs {algos[i2]}", *[f"{v:+.1f}({test.pvalue:.6e})" for v,test in zip(values,tests)], sep="\t")
import matplotlib.pyplot as plt
plt.rcParams["figure.figsize"] = (10,8)
def set_axis_style(ax, labels):
ax.set_xticks(np.arange(1, len(labels) + 1), labels=labels)
ax.set_xlim(0.25, len(labels) + 0.75)
ax.set_xlabel('Algorithm name')
stat_raw_np = np.array(stats)
plt.violinplot([stat_np[i,:,0] for i in range(n_algs)], side="low", showmeans=True)
plt.violinplot([stat_np[i,:,2] for i in range(n_algs)], side="high", showmeans=True)
plt.title("Best/Mean")
plt.ylabel("Score")
plt.ylim(50,180)
ax = plt.gca()
set_axis_style(ax, algos)
plt.savefig('fig1', bbox_inches='tight')
plt.show()
Raw
analysis2.py
# analysis
# board, trial
# 200, 200
algos = ["rand ", "elem ", "sumsq", "area "]
stats = []
for i in range(len(algos)):
filename = f"{algos[i]}_raw2.csv"
with open(filename, "r") as f:
# f.readline() # avg_best,avg_worst,avg_mean
board=[]
for l in f:
val = list(map(float, l.strip().split(',')))
board += [(val)]
stats += [board]
n_algs = len(stats)
n_boards = len(stats[0])
n_trials = len(stats[0][0])
stat_li = []
for i in range(len(algos)):
tmp1 = []
for j in range(len(stats[i])):
best=0
worst=999
sums=0
sumsq=0
tmp2 = []
for k in range(len(stats[i][j])):
v = stats[i][j][k]
best, worst, sums, sumsq = max(best, v), min(worst, v), sums+v, sumsq+v*v
mean=sums/(k+1)
variance=(sumsq/(k+1)-mean*mean)**.5
tmp2 += [(best,worst,mean,variance)]
tmp1 += [tmp2]
stat_li += [tmp1]
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams["figure.figsize"] = (10,8)
stat_np = np.array(stat_li)
best_np = stat_np[:,:,:,0]
mean_best_np = np.mean(best_np, axis=1)
#worst_np = stat_np[:,:,:,1]
#avg_np = stat_np[:,:,:,2]
#stdev_np = stat_np[:,:,:,3]
for i in range(n_algs):
plt.plot(range(1,n_trials+1), mean_best_np[i], label=algos[i])
plt.title("Best")
plt.legend()
plt.xlabel("Trials")
plt.ylabel("Score")
plt.savefig('fig2', bbox_inches='tight')
plt.show()
Raw
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")
Raw
apple_benchmark.py
import random
# create game
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 nullfn(*args, **kwargs):
return
def run_test(algo, matrix, n_trial=None, verbose=True, *, rng=None, kwargs=None):
if not verbose:
print=nullfn
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
from tqdm import trange
if __name__=="__main__":
# run
seed = 1
n_boards = 2000
n_trial = 25
algos = [
# random algos:
# random
# elem, random
# sumsquare, random
# area, 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]))}),
]
# create rng for board and test
board_rng = random.Random(seed)
test_rng = random.Random(seed)
verbose = False
tmpprint = print
if not verbose:
print = nullfn
stat_li = [[] for _ in range(len(algos))]
output_li = [[] for _ in range(len(algos))]
for j in trange(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, verbose=verbose, 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)]
output_li[i] += [cnt_li]
if best==170:
tmpprint(f'algorithm {i+1}: {algo_name} all cleared at board {j}')
print = tmpprint
idnames = ["avg best ", "avg worst ", "avg mean "]
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")
idnames = ["avg best ", "avg worst ", "avg mean "]
print("## Algo ", *idnames, sep="\t")
for i in range(len(algos)):
for i2 in range(i+1, len(algos)):
values = []
sds = []
for k in range(len(idnames)):
values += [sum(stat_li[i][j][k]-stat_li[i2][j][k] for j in range(n_boards))/n_boards]
for k in range(len(idnames)):
sds += [(sum((stat_li[i][j][k]-stat_li[i2][j][k])**2 for j in range(n_boards))/n_boards - values[k]**2)**0.5]
print(f"{algos[i][0]} vs {algos[i2][0]}", *[f"{v:+.1f}({sd:.1f})" for v,sd in zip(values,sds)], sep="\t")
print("## Algo ", "max best", "min worst", sep="\t")
for i in range(len(algos)):
values = []
sds = []
values += [max(stat_li[i][j][0] for j in range(n_boards))]
values += [min(stat_li[i][j][1] for j in range(n_boards))]
print(f"{i+1:02d} {algos[i][0]}", *[f"{v:.1f}" for v in values], sep="\t")
for i in range(len(algos)):
filename = f"{algos[i][0]}_raw.csv"
with open(filename, "x") as f:
for j in range(n_boards):
print(*output_li[i][j], sep=',', file=f)
Raw
apple_brute.py
import random
import time
# 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 t0,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(f"Max found {count_best} ({len(visit)}@{time.perf_counter()-t0:.6f})")
return
for cand in cands:
ops = act(*cand, matrix)
assert len(ops)!=0
for i,j,v in ops:
encode ^= codebook[i][j]
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]
codebook = [[random.randrange(2**64) for _ in range(n_col)] for _ in range(n_row)]
mat_i = [e[:] for e in matrix]
encode = 0
t0 = time.perf_counter()
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment