medal-solvers/TASK255_ANALYSIS.md

Task 255 — Analysis and Partial Solution

Score: 6.64 (94M memory, 851 nodes)

Transformation Rule (257/261 arc-gen pass, 3 train + 1 test pass)

Input: 30×30 grid with background (0) + one foreground color. Output: same grid with color 3 added in a cross-shaped empty region.

Algorithm:

1. Find the largest empty rectangle in the input grid (maximal rectangle of zeros)
2. Erode by 1 pixel on each side that is NOT at the grid boundary
   • This gives the "core" of the cross
3. Extend the cross iteratively in all 4 directions:
   • For each row in the core: if ALL foreground in that row is to the LEFT of the core's left edge → extend that row to the RIGHT (fill to grid edge)
   • Similarly: fg only to the right → extend left
   • For each column in the core: if ALL fg in that column is ABOVE the core's top → extend column downward
   • Similarly: fg only below → extend up
4. Erode each contiguous run of extensions by 1 on non-edge sides
5. Repeat steps 3-4 iteratively (extensions can cascade — new extensions create new eligible rows/columns)
6. Mask: only fill background pixels (color 3 never overwrites foreground)

Verified:

• Train: 3/3 PASS
• Test: 1/1 PASS
• Arc-gen: 257/261 PASS (98.5%)

Remaining 4 Failures:

• arc-gen[116], [155], [173], [218]
• All have Missing>0, Extra=0 (rule under-predicts)
• These are cases where the largest rectangle is in a CORNER and extensions need to cascade in multiple directions simultaneously
• The cascading logic needs to properly recompute eligible rows/columns after each extension direction

Key Insight for Erosion:

• Erosion is ONLY applied on sides that are NOT at the grid boundary (row 0, row 29, col 0, col 29)
• Example: rect rows 0-15 at left edge → no erosion on row 0 side, erode row 15 side

Implementation in ONNX:

The algorithm requires:

1. Largest empty rectangle finding (can be done with prefix sums → MatMul operations)
2. Erosion (simple shift operations)
3. Per-row/per-column checks (reducible to MatMul on row/col vectors)
4. Iterative extension (fixed number of iterations since grid is 30×30)

Expected memory reduction: from 94M to ~1-5M (score improvement: +3-5 pts)

Next Steps:

1. Fix the 4 remaining arc-gen failures (cascading extension bug)
2. Build ONNX model implementing the rule
3. Validate with official neurogolf_utils.py