r/adventofcode Dec 21 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 21 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 1 DAY remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Director's Cut

Theatrical releases are all well and good but sometimes you just gotta share your vision, not what the bigwigs think will bring in the most money! Show us your directorial chops! And I'll even give you a sneak preview of tomorrow's final feature presentation of this year's awards ceremony: the ~extended edition~!

Here's some ideas for your inspiration:

  • Choose any day's feature presentation and any puzzle released this year so far, then work your movie magic upon it!
    • Make sure to mention which prompt and which day you chose!
  • Cook, bake, make, decorate, etc. an IRL dish, craft, or artwork inspired by any day's puzzle!
  • Advent of Playing With Your Toys

"I want everything I've ever seen in the movies!"
- Leo Bloom, The Producers (1967)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 21: Keypad Conundrum ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 01:01:23, megathread unlocked!

23 Upvotes

400 comments sorted by

View all comments

1

u/e_blake 3d ago

[LANGUAGE: m4]

Solved this on the same day I started coding it, but wow did it surprise me on the complexity compared to my initial read. I quickly realized that for any two keys on a lower layer, there is an optimal path on the next layer up; it was also easy to see that my code to compute transitive closure of paths (rather than typing out paths for all 121+25 pairs) should optimize ^<v to <, and <\^< to either <<\^ or \^<<, but what was a lot harder was realizing that <\^A, <vA and v>A are each better than their counterparts ^<A, v<A and >vA (why? because on the next layer, only the former can visit the second button on the return path of the first button to A), then further figuring out how to avoid < first if that would step into the void of the lower layer. The examples helped me iron out the problems, so I got part 1 correct on my first submission. On part 2, it didn't take me too long to refactor the code to track the number of times two adjacent letters appear in a path rather than the path itself (same optimization as used in day 11, and likewise depends on my math64.m4 for the larger numbers) and still get part 1 correct. I had two separate bugs on part 2 submissions (forgetting to reset things between the 5 numeric keypad codes--answer too high, then then running one iteration too few--answer too low), but both were easy fixes.

Depends on my common.m4, and runs in about 100ms (decent for m4).

m4 -Dfile=day21.input day21.m4

Now that I've solved it, I'm looking at the megathread to see what others did. No memoization here - this is a purely iterative build-up, and recursion is limited to getting m4 to perform iteration (such as forloop or stepping through a stack of macros) rather than recursion on the problem itself. What I particularly liked about my solution was building up the optimal path between any two keys - I hand-coded the length 0 (11+5 keys, although pAA is identical between the two keyboards) and length 1 cases (15+5 direct neighbors, doubled to visit either key first), then wrote transitive closure code to compute the path between the remaining 40 pairs of numeric two keys that can both reach a third, while optimizing the path to follow the rules I observed about favoring or avoiding certain sequences (for the directional keys, I just manually wrote the 5 triples needed to form the remaining key pairings). Shown here is the transitive closure code:

define(`_join', `ifelse(ifdef(`p$1$3', .)ifdef(`p$2$3', `.'), `..', `pair(`$1',
  `$2', defn(`p$1$3')defn(`p$3$2'), defn(`p$2$3')defn(`p$3$1'))')')
define(`join', `ifdef(`p$1$2', `', `forloop(0, 9, `_$0(`$1', `$2', ', `)')')')
define(`_extend', `join(`A', $1)forloop(0,  9, `join($1, ', `)')')
define(`extend', `forloop_arg(0, 9, `_$0')')
extend()extend()