Obligatory wrap up post!
clews.id.au/posts/advent...

#AdventOfCode

Today's Advent of Code: change one word (toggle → increment) and your elegant O(n³) solution becomes NP-hard.

Four failed approaches later, I finally learned this could be solved with Integer Linear Programming.

More details:
clews.id.au/til/integer-...

#AdventOfCode #Rust

Final results:
- Flood fill: 60+ sec (didn't finish)
- Coordinate compression: Buggy
- Geo crate: 4.4s, 31 dependencies
- Custom geometry: 2.6s, ZERO dependencies! 🎉

The custom solution was 1.7x FASTER than the library!

Challenge accepted! Implemented custom geometry code:
- Ray casting for point-in-polygon
- Edge-rectangle intersection tests
- Rectilinear polygon containment check

~130 lines of careful geometry code. Worth it?

Breakthrough moment: "What if I just use a geometry library?"

Added Rust's geo crate, rewrote Part 2 to use Polygon.contains().

Result! Correct answer in 4.4 seconds!

But... 31 transitive dependencies for one function? 🤔

Next attempt: coordinate compression. Compress the sparse grid down to just the relevant coordinates.

Implemented it... incorrectly. The mapping bugs were gnarly. 😤

The problem? 495 red tiles with coordinates in the 90K+ range = 3+ million cells to flood fill. BFS optimisation didn't help.

Time to pivot!

Part two was a journey in frustration!

Started with what seemed obvious: flood fill to find all green tiles, then check each rectangle. Simple, right?

Wrong. 60+ seconds and still running... 😅

If you reinvented Kruskal, you’ve already internalised the idea behind it. That’s a win!