AoC 2024: Day 21

Main thread for Day 21 of the 2024 advent of code. Feel free to discuss the challenge and ask questions. If particular discussions become large, we can break them off into new threads.

Some Rules:

  1. Please try to keep spoilers within spoiler tags. This is done by typing [spoiler]text to be blurred[\spoiler]. If you have longer sections you can also use the [details=“Title”] tags.
  2. Have Fun

Day 21 Challenge

Templates:

Resources:

Previous days discussions

Day 1: AoC 2024: Day 1
Day 2: AoC 2024: Day 2
Day 3: AoC 2024: Day 3
Day 4: AoC 2024: Day 4
Day 5: AoC 2024: Day 5
Day 6: AoC 2024: Day 6
Day 7: AoC 2024: Day 7
Day 8: AoC 2024: Day 8
Day 9: AoC 2024: Day 9
Day 10: AoC 2024: Day 10
Day 11: AoC 2024: Day 11
Day 12: AoC 2024: Day 12
Day 13: AoC 2024: Day 13
Day 14: AoC 2023: Day 14
Day 15: AoC 2024: Day 15
Day 16: AoC 2024: Day 16
Day 17: AoC 2024: Day 17
Day 18: AoC 2024: Day 18
Day 19: AoC 2024: Day 19
Day 20: AoC 2024: Day 20

This was a trip, started by attempting a heuristic solution (which would have worked, but more on that later), decided against it since a BFS would be nicer, then part2 forced to upgrade to a dynamic programming solution (since heuristics still seemed not to work). Implemented that, and it basically confirmed that, indeed, heuristics should have worked. Eh.

Source: aoc2024/src/day21.zig at main · p88h/aoc2024 · GitHub
(don’t look at it, its’ horrible).

Video:https://youtu.be/PDDdEBg63PQ
(look at that instead)

Benchmark (with some precomputations kept in code, but works for all inputs):

        parse   part1   part2   total
day 21:  0.4 µs  1.2 µs  1.1 µs  2.9 µs (+-4%) iter=98110