A bit lighter day, though it did not feel easier at first. In fact part1 was clearly identified as two parts:
- first make the magic blocks fall; includes making 3D collisions work and "editing" or "compressing" the input. It has some examples, which could be used to make test cases.
- then identify which blocks, when removed, do *not* generate any more "compression" or falling blocks. This second half of part 1 could reuse the first half, but I chose not to, thinking it would help with part 2: the complexity seemed approachable, but I could imagine other problems where it would not scale. So I built two maps of which blocks support which and the opposite one (which is supported by which), and then used that to solve the problem. Once the sample passed, so did the input.

For part 2, I was right, and the two reverse maps were needed to explore the set of possibilities, with a recursive solutions with a set of fallen blocks.

My solution has many inefficiencies, and clocks at around 2s in release mode, but that will have to do for today 🙂

#AdventOfCode

This one went smoothly. I did the simple recursive depth-first exploration for part 1: I figured a full exploration would be doable since the slopes are heavily reducing the search space.

It succeeded in the first try with no test.

Then part 2 relaxed a bit the conditions, making the search space much bigger. As usual, I went for a bruteforce-first "just-in-case", and then kept looking.
The problem looked like it would need dynamic programing. I was debugging such an approach while the bruteforce returned something. Tried it, and it worked !

I continue debugging the DP approach, and even found the optimal result for the given example. But I now knew the real answer, and it just did not work on input.
In reality, this is a Longest Path in Cyclic Graph problem, one that is NP-hard. It's possible to reduce a bit the search space with edge transitive reduction (remove cells that are only adjacent to two cells), but I opted to simply get a bigger stack (and then, this is only needed in debug mode, not release mode).

My only regret is that I used a set of coordinates for the seen nodes instead of two-dimensional boolean array (which I usually reach for), wasting ~15min in my bruteforce approach. Final solution takes about 4min, with no edge reduction. I need a faster computer 🙂 (usually one doesn't for AoC 😞)

I ranked 698 for part 1 and 185 for part 2! Looks like I broke two records on a single day !

#AdventOfCode

I could not resist, so for day 23, I wrote an edge-reduction (+trivial dead-end elimination) solution, and it takes ~300ms in release mode.

I still have no regrets because it took me longer to write than the time to write and run my first naive bruteforce solution.

On the plus side: I generated a graphviz of the reduced input which helped understand why it was needed:

#AdventOfCode

I solved part 1 in an average time (for the later days); the real problem was part 2. I did not know how to approach the solution for a long time; so this was definitely the hardest problem this year.

After failing to solve part 2 in Wolfram Alpha (reaching the limit of characters), I ended up writing a bruteforce solution which found the solution from the example pretty quickly. But as I had guessed, it did not work for the much bigger input. I did not let it run for more than 1 hour.

So the next day, I caved and started to learn how to use z3 with the rust bindings crate. It took some wrestling (no examples, buggy build on fedora fixed in git but with no new crate), but I managed to do it, and it finds a solution in a few seconds.
I now know it can be solved in ~constant time, but I was too tired to re-write (again) the equations to solve them, or to learn about and implement Gaussian Elimination.

#AdventOfCode #AdventOfMath #RustLang

As I saw the problem today, I was reminded of how useful was visualization on day 20.

So I immediately tried to learn about the dot language (that was fast), and whipped up some awk to convert the input. The three connection edges were quickly apparent, so I removed them manually, made the other edges bi-directional and counted the nodes on each part of the graph.

I know there is a simple graph-theory solution with flows, but that will be enough for me for this year's AoC !

#AdventOfCode

It's the second year in a row that I'm able to complete AoC. And I'll be honest: this was though. The break-neck pace of doing one full solve per day requires that one either has a lot of free time, or has previously spent a lot of free time getting better in order to solve the puzzles faster. I do it because it's fun, and it still was; but I'm aware that it's walking over the not-fun line as well.

I was able to do it, but it was not cost-free. I think I might go for a lighter pace (or skip) next year.

On a positive note, I still learned a lot this year, and that's one of my personal goals 🙂

#AdventOfCode