File size: 9,147 Bytes
c23eced 2e5b81a c23eced 2e5b81a c23eced 2e5b81a | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 | """Task 255 solver — 265/265 pass (ALL examples correct).
Algorithm:
1. Find largest empty rect → erode non-boundary sides → core
2. PHASE 1: RIGHT/LEFT extensions (single pass, dynamic eligibility from core)
3. PHASE 2: Sub-rect post-processing for runs with wide gaps (static eligibility, gap >= 4)
4. PHASE 3: DOWN/UP extensions (height>=3 guard + adjacent no-fg col extension)
5. PHASE 4: Second RIGHT/LEFT pass (width>=3 guard, cascades from UP/DOWN vertical arms)
6. Mask to background (inp==0) only
Key insights that solved all 4 previously-failing cases:
- [116],[218]: Sub-rect in static-eligible rows extends >= 4 beyond main rect → use eroded sub-rect boundary
- [155],[173]: height>=3 guard on DOWN/UP prevents short RIGHT/LEFT arms from cascading perpendicular
- [130]: Adjacent no-fg cols extend the UP/DOWN eligible run; second RIGHT/LEFT pass handles cascade from vertical arm
Validated: 3/3 train + 1/1 test + 261/261 arc-gen = 265/265 PASS
"""
import numpy as np
import json
def find_largest_empty_rect(inp):
h, w = inp.shape
heights = np.zeros(w, dtype=int)
best_area, best = 0, (0, 0, 0, 0)
for r in range(h):
for c in range(w):
heights[c] = heights[c] + 1 if inp[r, c] == 0 else 0
stack = []
for c in range(w + 1):
cur_h = heights[c] if c < w else 0
start = c
while stack and stack[-1][1] > cur_h:
idx, sh = stack.pop()
area = sh * (c - idx)
if area > best_area:
best_area = area
best = (r - sh + 1, idx, sh, c - idx)
start = idx
if not stack or cur_h > stack[-1][1]:
stack.append((start, cur_h))
return best
def erode_range(start, end, grid_max):
s, e = start, end
if s > 0: s += 1
if e < grid_max: e -= 1
return s, e
def find_contiguous_runs(indices):
if not indices: return []
runs, start, prev = [], indices[0], indices[0]
for i in indices[1:]:
if i == prev + 1: prev = i
else: runs.append((start, prev)); start = prev = i
runs.append((start, prev))
return runs
def apply_rule(inp):
h, w = inp.shape
tr, lc, rh, rw = find_largest_empty_rect(inp)
main_r1, main_r2 = tr, tr + rh - 1
main_c1, main_c2 = lc, lc + rw - 1
core_r1, core_r2 = erode_range(main_r1, main_r2, h - 1)
core_c1, core_c2 = erode_range(main_c1, main_c2, w - 1)
result = np.zeros((h, w), dtype=bool)
result[core_r1:core_r2+1, core_c1:core_c2+1] = True
# PHASE 1: RIGHT/LEFT (dynamic eligibility, single pass)
right_elig = []
for r in range(h):
rc = np.where(result[r])[0]
if len(rc) == 0: continue
fg = np.where(inp[r] != 0)[0]
if len(fg) == 0 or fg[-1] < rc[0]:
right_elig.append(r)
for rs, re in find_contiguous_runs(sorted(right_elig)):
es, ee = erode_range(rs, re, h - 1)
if es <= ee:
for r in range(es, ee + 1):
rc = np.where(result[r])[0]
if len(rc) > 0: result[r, rc[-1]+1:] = True
left_elig = []
for r in range(h):
rc = np.where(result[r])[0]
if len(rc) == 0: continue
fg = np.where(inp[r] != 0)[0]
if len(fg) == 0 or fg[0] > rc[-1]:
left_elig.append(r)
for rs, re in find_contiguous_runs(sorted(left_elig)):
es, ee = erode_range(rs, re, h - 1)
if es <= ee:
for r in range(es, ee + 1):
rc = np.where(result[r])[0]
if len(rc) > 0: result[r, :rc[0]] = True
# PHASE 2: Sub-rect post-processing (static eligibility, threshold >= 4)
static_right = []
for r in range(h):
fg = np.where(inp[r] != 0)[0]
if len(fg) == 0 or fg[-1] < core_c1:
static_right.append(r)
for rs, re in find_contiguous_runs(sorted(static_right)):
sub = inp[rs:re+1, :]
sub_tr, sub_lc, sub_rh, sub_rw = find_largest_empty_rect(sub)
if main_c1 - sub_lc >= 4:
e_r1, e_r2 = erode_range(rs + sub_tr, rs + sub_tr + sub_rh - 1, h - 1)
e_c1, _ = erode_range(sub_lc, sub_lc + sub_rw - 1, w - 1)
if e_r1 <= e_r2:
for r in range(e_r1, e_r2 + 1):
result[r, e_c1:] = True
static_left = []
for r in range(h):
fg = np.where(inp[r] != 0)[0]
if len(fg) == 0 or fg[0] > core_c2:
static_left.append(r)
for rs, re in find_contiguous_runs(sorted(static_left)):
sub = inp[rs:re+1, :]
sub_tr, sub_lc, sub_rh, sub_rw = find_largest_empty_rect(sub)
sub_c2 = sub_lc + sub_rw - 1
if sub_c2 - main_c2 >= 4:
e_r1, e_r2 = erode_range(rs + sub_tr, rs + sub_tr + sub_rh - 1, h - 1)
_, e_c2 = erode_range(sub_lc, sub_c2, w - 1)
if e_r1 <= e_r2:
for r in range(e_r1, e_r2 + 1):
result[r, :e_c2+1] = True
# PHASE 3: DOWN/UP (dynamic, height>=3 guard + adjacent no-fg col extension)
down_elig = set()
for c in range(w):
rr = np.where(result[:, c])[0]
if len(rr) == 0: continue
if (rr[-1] - rr[0] + 1) < 3: continue
fg = np.where(inp[:, c] != 0)[0]
if len(fg) == 0 or fg[-1] < rr[0]:
down_elig.add(c)
extended = set(down_elig)
for c in sorted(down_elig):
for adj in [c-1, c+1]:
if 0 <= adj < w and adj not in extended:
fg_adj = np.where(inp[:, adj] != 0)[0]
if len(fg_adj) == 0:
extended.add(adj)
for cs, ce in find_contiguous_runs(sorted(extended)):
es, ee = erode_range(cs, ce, w - 1)
if es <= ee:
for c in range(es, ee + 1):
rr = np.where(result[:, c])[0]
if len(rr) > 0:
result[rr[-1]+1:, c] = True
else:
result[core_r2+1:, c] = True
up_elig = set()
for c in range(w):
rr = np.where(result[:, c])[0]
if len(rr) == 0: continue
if (rr[-1] - rr[0] + 1) < 3: continue
fg = np.where(inp[:, c] != 0)[0]
if len(fg) == 0 or fg[0] > rr[-1]:
up_elig.add(c)
extended_up = set(up_elig)
for c in sorted(up_elig):
for adj in [c-1, c+1]:
if 0 <= adj < w and adj not in extended_up:
fg_adj = np.where(inp[:, adj] != 0)[0]
if len(fg_adj) == 0:
extended_up.add(adj)
for cs, ce in find_contiguous_runs(sorted(extended_up)):
es, ee = erode_range(cs, ce, w - 1)
if es <= ee:
for c in range(es, ee + 1):
rr = np.where(result[:, c])[0]
if len(rr) > 0:
result[:rr[0], c] = True
else:
result[:core_r1, c] = True
# PHASE 4: Second RIGHT/LEFT pass (width>=3 guard, after UP/DOWN)
right_elig2 = []
for r in range(h):
rc = np.where(result[r])[0]
if len(rc) == 0: continue
if (rc[-1] - rc[0] + 1) < 3: continue
fg = np.where(inp[r] != 0)[0]
if len(fg) == 0 or fg[-1] < rc[0]:
right_elig2.append(r)
for rs, re in find_contiguous_runs(sorted(right_elig2)):
es, ee = erode_range(rs, re, h - 1)
if es <= ee:
for r in range(es, ee + 1):
rc = np.where(result[r])[0]
if len(rc) > 0: result[r, rc[-1]+1:] = True
left_elig2 = []
for r in range(h):
rc = np.where(result[r])[0]
if len(rc) == 0: continue
if (rc[-1] - rc[0] + 1) < 3: continue
fg = np.where(inp[r] != 0)[0]
if len(fg) == 0 or fg[0] > rc[-1]:
left_elig2.append(r)
for rs, re in find_contiguous_runs(sorted(left_elig2)):
es, ee = erode_range(rs, re, h - 1)
if es <= ee:
for r in range(es, ee + 1):
rc = np.where(result[r])[0]
if len(rc) > 0: result[r, :rc[0]] = True
return result & (inp == 0)
def verify_task255(task_data_path='task-data/task255.json'):
with open(task_data_path) as f:
data = json.load(f)
total_pass, total_fail, failures = 0, 0, []
for split in ['train', 'test', 'arc-gen']:
for idx, ex in enumerate(data[split]):
inp_arr = np.array(ex['input'], dtype=int)
exp = np.array(ex['output'], dtype=int)
mask = apply_rule(inp_arr)
pred = inp_arr.copy(); pred[mask] = 3
if np.array_equal(pred, exp):
total_pass += 1
else:
total_fail += 1
m = ((exp == 3) & (pred != 3)).sum()
e = ((pred == 3) & (exp != 3)).sum()
failures.append({'split': split, 'idx': idx, 'missing': int(m), 'extra': int(e)})
print(f"Results: {total_pass} pass, {total_fail} fail")
for f in failures[:15]:
print(f" {f['split']}[{f['idx']}]: M={f['missing']}, E={f['extra']}")
return total_pass, total_fail, failures
if __name__ == '__main__':
verify_task255()
|