Part 1: Brute force all 2^n button combinations (XOR toggle)
Part 2: Bifurcate algorithm - enumerate parity-matching combos,
halve remaining targets, and recurse with memoization
Algorithm credit: Reddit user tenthmascot
https://www.reddit.com/r/adventofcode/comments/1pk87hl/
The key insight is that Part 1 (parity/XOR) helps solve Part 2:
1. Find all button combos that achieve correct target parity
2. Press those once (Phase 1), making all remaining values even
3. Halve and recurse - O(log(max_target)) depth with caching
Part 1: Find largest rectangle with any two red tiles as corners
Part 2: Rectangle must be entirely within the polygon formed by
red tiles connected by green edges + interior fill
Used coordinate compression + expanded grid flood fill + 2D prefix
sum for O(n²) rectangle validation on huge coordinate ranges.
Turns out two simple heuristics solve the whole problem in 4ms:
1. Does the area fit? No → invalid
2. Are there enough 3x3 spaces for all presents? Yes → valid
But hey, at least we learned how to use Dancing Links for
a problem that didn't need it. The dlx crate thanks us for
the download stats.
Day 10: Indicator light configuration with bitmask brute-force
Day 11: Graph path counting with memoized DFS
- Part 1: Count all paths from 'you' to 'out'
- Part 2: Count paths from 'svr' to 'out' visiting both 'dac' and 'fft'
Russell Champoux
RussellChamp