2024 Day 21: Keyboard Conundrum

Advent of Code
1

It doesn’t surprise me that competitors earned the fewest stars. This problem is downright ornery.1

  • There’s a hidden twist that <^, when possible is always a better choice than ^<. The examples reveal that one if you dig through the details long enough, but the twist doubles down because it’s not the only pair where that happens.
  • The multiple levels of indirection make it pretty confusing.
  • There’s a reason the puzzle master doesn’t list any solutions for Part 2: combinatorial explosion. :fearful: :scream: :scream_cat: :exploding_head: Fortunately, each string of arrow-pad commands consists of multiple independent substrings separated by As, so rather than expand the entire string count the substrings and adjust the numbers as you pass through the levels of robots.

This problem defeated me, and after several hours (where it turned out I had been on the right track!) I surrendered to the dark side of reading articles on how others solved it: this one for Part 1 and this one for Part 2.

1 downright ornery: I don’t mean that as a criticism; it’s a great problem!

1 Like
2

Indeed!

It’s the thoughest puzzle this year, in my perception.
I have left it for later (that turned out to be a few hours ago) with the hope (back then) that it was the peak of difficulty (it worked).

I also dark-sided, and adapted @jcmoyer’s solution to the restrictive context of HAC: no containers (esp. vectors), no unconstrained types, no “for X of T”, and so on. So it was a sort of an alternative challenge…

Differences from @jcmoyer’s implementation:

  • Breadth First Search (BFS) algo for getting paths in keypads is
    replaced by a systematic search, “Manhattan-style” (there is no obstacle except one gap).

  • Memoization (cache-ing) is done via an array instead of a hash map.

3

I thought of BFS’ing this one, but every time I started to think about it, it looked too complicated to tear myself from the approach I was using.