""" Task 101 Solver — 266/266 verified Rule: 1. Template c2 = all c2 connected (through c2) to c1-adjacent c2 2. Template c1 = all c1 cells 3. Markers = remaining c2 cells 4. Marker blocks match template c2 pattern at some scale s: - Each template c2 cell becomes an s×s block in the marker - Connected marker block can contain the ENTIRE scaled template c2 pattern 5. c1 cells are stamped relative to the matched pattern ONNX Status: NOT VIABLE — requires CC detection, dynamic pattern matching, variable grids (14x12, 17x14, 17x21) """ import json import numpy as np from collections import deque def solve_task101(inp_grid): inp = np.array(inp_grid) H, W = inp.shape out = inp.copy() c1_positions = list(map(tuple, np.argwhere(inp == 1))) c2_positions = list(map(tuple, np.argwhere(inp == 2))) if not c1_positions or not c2_positions: return out.tolist() c1_set = set(c1_positions) c2_set = set(c2_positions) # Find template c2: flood-fill from c1-adjacent c2 through c2 seed_c2 = set() for pos in c2_positions: r, c = pos for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: if (r+dr, c+dc) in c1_set: seed_c2.add(pos) break if not seed_c2: return out.tolist() template_c2_set = set(seed_c2) queue = deque(seed_c2) while queue: pos = queue.popleft() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nb = (pos[0]+dr, pos[1]+dc) if nb in c2_set and nb not in template_c2_set: template_c2_set.add(nb) queue.append(nb) template_c2 = sorted(template_c2_set) marker_c2_set = c2_set - template_c2_set if not marker_c2_set or not template_c2: return out.tolist() # Template c2 relative positions tpl_c2_min_r = min(p[0] for p in template_c2) tpl_c2_min_c = min(p[1] for p in template_c2) tpl_c2_rel = [(r - tpl_c2_min_r, c - tpl_c2_min_c) for r, c in template_c2] # Template c2 bbox dimensions tpl_c2_h = max(r for r, c in tpl_c2_rel) + 1 tpl_c2_w = max(c for r, c in tpl_c2_rel) + 1 # Template c1 relative to template c2 TL tpl_c1_rel = [(r - tpl_c2_min_r, c - tpl_c2_min_c) for r, c in c1_positions] def stamp_at(origin_r, origin_c, scale): for (tr, tc) in tpl_c1_rel: for sr in range(scale): for sc in range(scale): r = origin_r + tr * scale + sr c = origin_c + tc * scale + sc if 0 <= r < H and 0 <= c < W and out[r, c] == 0: out[r, c] = 1 def check_block_matches_pattern(block_cells, block_min_r, block_min_c, block_h, block_w, scale): expected = set() for (tr, tc) in tpl_c2_rel: for sr in range(scale): for sc in range(scale): expected.add((block_min_r + tr * scale + sr, block_min_c + tc * scale + sc)) return expected == block_cells # Group marker c2 into connected components visited = set() marker_blocks = [] for pos in sorted(marker_c2_set): if pos in visited: continue component = set() q = deque([pos]) visited.add(pos) while q: p = q.popleft() component.add(p) for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nb = (p[0]+dr, p[1]+dc) if nb in marker_c2_set and nb not in visited: visited.add(nb) q.append(nb) rows_b = [p[0] for p in component] cols_b = [p[1] for p in component] min_r = min(rows_b) min_c = min(cols_b) block_h = max(rows_b) - min_r + 1 block_w = max(cols_b) - min_c + 1 marker_blocks.append((min_r, min_c, block_h, block_w, component)) n_anchors = len(template_c2) processed = set() for idx, (min_r, min_c, bh, bw, cells) in enumerate(marker_blocks): if idx in processed: continue possible_scales = set() if tpl_c2_h > 0 and bh % tpl_c2_h == 0: s = bh // tpl_c2_h if tpl_c2_w == 0 or bw == tpl_c2_w * s: possible_scales.add(s) if tpl_c2_w > 0 and bw % tpl_c2_w == 0: s = bw // tpl_c2_w if tpl_c2_h == 0 or bh == tpl_c2_h * s: possible_scales.add(s) for scale in sorted(possible_scales, reverse=True): if check_block_matches_pattern(cells, min_r, min_c, bh, bw, scale): stamp_at(min_r, min_c, scale) processed.add(idx) break # Second pass: pair unprocessed blocks unprocessed = [(idx, mb) for idx, mb in enumerate(marker_blocks) if idx not in processed] if unprocessed and n_anchors > 1: scale_blocks = {} for idx, (min_r, min_c, bh, bw, cells) in unprocessed: if bh == bw and len(cells) == bh * bw: scale = bh if scale not in scale_blocks: scale_blocks[scale] = [] scale_blocks[scale].append((idx, min_r, min_c)) else: if 1 not in scale_blocks: scale_blocks[1] = [] for cell in cells: scale_blocks[1].append((idx, cell[0], cell[1])) ref_r, ref_c = tpl_c2_rel[0] offsets_from_first = [(r - ref_r, c - ref_c) for r, c in tpl_c2_rel] for scale in sorted(scale_blocks.keys(), reverse=True): bl_list = scale_blocks[scale] bl_positions = set((r, c) for (_, r, c) in bl_list) used_positions = set() for (idx, r, c) in sorted(bl_list, key=lambda x: (x[1], x[2])): if (r, c) in used_positions: continue all_found = True group_positions = [(r, c)] for (dr, dc) in offsets_from_first[1:]: partner = (r + dr * scale, c + dc * scale) if partner not in bl_positions or partner in used_positions: all_found = False break group_positions.append(partner) if all_found: for p in group_positions: used_positions.add(p) origin_r = r - ref_r * scale origin_c = c - ref_c * scale stamp_at(origin_r, origin_c, scale) elif unprocessed and n_anchors == 1: for idx, (min_r, min_c, bh, bw, cells) in unprocessed: scale = min(bh, bw) if bh == bw: stamp_at(min_r, min_c, scale) else: for sr in range(0, bh, scale): for sc in range(0, bw, scale): sub_ok = all((min_r+sr+dr, min_c+sc+dc) in cells for dr in range(scale) for dc in range(scale)) if sub_ok: stamp_at(min_r + sr, min_c + sc, scale) return out.tolist() if __name__ == '__main__': with open('/app/task-data/task101.json') as f: data = json.load(f) all_examples = data['train'] + data['test'] + data.get('arc-gen', []) right, wrong = 0, 0 for i, ex in enumerate(all_examples): if solve_task101(ex['input']) == ex['output']: right += 1 else: wrong += 1 print(f"Results: {right}/{right+wrong} pass ({wrong} fail)")