"""Task 076 Solver — Centroid + 2-marker disambiguation for template rotation (266/266 PASS). Rule: 1. Input has 3-4 objects, each = bar (5 cells of color 4, 8-connected) + 2-marker (4-adj to bar) 2. Template has additional decorations (colors 1, 3) reachable via BFS from bar 3. Apply template decorations to incomplete objects using the correct rotation/reflection Key insights: - Use 8-connectivity for bar detection (bars can have diagonal connections) - Use BFS from bar cells to find ALL decoration cells (not just directly 4-adjacent) - Round centroid-relative coordinates to 0.1 to avoid float precision issues - Use 2-marker position to disambiguate among symmetric transforms ONNX: NOT VIABLE — requires connected component detection + BFS. """ import numpy as np import json from scipy.ndimage import label, generate_binary_structure def get_objects(inp): """Find all bar objects using 8-connectivity on color 4. Use BFS from bar cells to find all decoration cells (1, 2, 3) connected to bar.""" H, W = inp.shape struct8 = generate_binary_structure(2, 2) mask4 = (inp == 4).astype(int) labeled, n = label(mask4, structure=struct8) # Collect all bar cell sets all_bar_cells = set() bar_groups = [] for cid in range(1, n + 1): cells = list(zip(*np.where(labeled == cid))) bar_groups.append(cells) all_bar_cells.update(cells) objects = [] for cells in bar_groups: bar_set = set(cells) # BFS from bar cells to find decorations (colors 1, 2, 3) # Follow 4-connectivity through non-zero, non-bar cells adj = {1: set(), 2: set(), 3: set()} visited = set(all_bar_cells) # Don't cross into other bars queue = list(cells) # Start from bar cells while queue: next_queue = [] for r, c in queue: for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = r + dr, c + dc if 0 <= nr < H and 0 <= nc < W and (nr, nc) not in visited: v = inp[nr, nc] if v in (1, 2, 3): visited.add((nr, nc)) adj[v].add((nr, nc)) next_queue.append((nr, nc)) queue = next_queue is_template = len(adj[1]) > 0 or len(adj[3]) > 0 objects.append({ 'cells': cells, 'adj1': adj[1], 'adj2': adj[2], 'adj3': adj[3], 'is_template': is_template }) return objects def normalize_shape(cells): """Get centroid and centroid-relative sorted coordinates (rounded to avoid float issues).""" cells_arr = np.array(cells, dtype=float) centroid = cells_arr.mean(axis=0) rel = cells_arr - centroid # Round to 1 decimal to avoid float precision issues rel_rounded = np.round(rel, 1) rel_list = sorted([tuple(r) for r in rel_rounded.tolist()]) return centroid, rel_list TFS = [ lambda r, c: (r, c), lambda r, c: (c, -r), lambda r, c: (-r, -c), lambda r, c: (-c, r), lambda r, c: (r, -c), lambda r, c: (-r, c), lambda r, c: (c, r), lambda r, c: (-c, -r), ] def apply_tf(points, idx): """Apply transform idx to list of (r,c) points.""" return [TFS[idx](r, c) for r, c in points] def round_point(p): """Round a point to 1 decimal.""" return (round(p[0], 1), round(p[1], 1)) def find_tf_with_marker(t_shape, t_marker_rel, i_shape, i_marker_rel): """Find transform that maps template bar shape to incomplete shape AND maps template 2-marker relative position to incomplete 2-marker relative position.""" i_marker_rounded = round_point(i_marker_rel) t_marker_rounded = round_point(t_marker_rel) candidates = [] for idx in range(8): transformed_shape = sorted([round_point(p) for p in apply_tf(t_shape, idx)]) if transformed_shape == i_shape: t_marker_transformed = round_point(TFS[idx](t_marker_rounded[0], t_marker_rounded[1])) if t_marker_transformed == i_marker_rounded: return idx candidates.append(idx) if candidates: return candidates[0] return None def solve_076(inp_grid): inp = np.array(inp_grid) H, W = inp.shape out = inp.copy() objects = get_objects(inp) template = None incompletes = [] for obj in objects: if obj['is_template']: template = obj elif len(obj['adj2']) > 0: incompletes.append(obj) if template is None: return out.tolist() t_centroid, t_shape = normalize_shape(template['cells']) if template['adj2']: t_marker = list(template['adj2'])[0] t_marker_rel = (t_marker[0] - t_centroid[0], t_marker[1] - t_centroid[1]) else: t_marker_rel = (0.0, 0.0) t_deco1_rel = [(r - t_centroid[0], c - t_centroid[1]) for r, c in template['adj1']] t_deco3_rel = [(r - t_centroid[0], c - t_centroid[1]) for r, c in template['adj3']] for inc in incompletes: i_centroid, i_shape = normalize_shape(inc['cells']) if inc['adj2']: i_marker = list(inc['adj2'])[0] i_marker_rel = (i_marker[0] - i_centroid[0], i_marker[1] - i_centroid[1]) else: i_marker_rel = (0.0, 0.0) tf_idx = find_tf_with_marker(t_shape, t_marker_rel, i_shape, i_marker_rel) if tf_idx is None: continue new_deco1 = apply_tf(t_deco1_rel, tf_idx) new_deco3 = apply_tf(t_deco3_rel, tf_idx) for dr, dc in new_deco1: nr, nc = int(round(i_centroid[0] + dr)), int(round(i_centroid[1] + dc)) if 0 <= nr < H and 0 <= nc < W and out[nr, nc] == 0: out[nr, nc] = 1 for dr, dc in new_deco3: nr, nc = int(round(i_centroid[0] + dr)), int(round(i_centroid[1] + dc)) if 0 <= nr < H and 0 <= nc < W and out[nr, nc] == 0: out[nr, nc] = 3 return out.tolist() if __name__ == "__main__": import sys task_data = 'task-data' if not __import__('os').path.exists(task_data): task_data = '../task-data' with open(f"{task_data}/task076.json") as f: data = json.load(f) all_ex = data["train"] + data["test"] + data.get("arc-gen", []) right = sum(1 for ex in all_ex if solve_076(ex["input"]) == ex["output"]) print(f"task076: {right}/{len(all_ex)} PASS")