File size: 2,397 Bytes
7f77137 | 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 | # 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
|