AoC 2024: Day 20

Challenge
1

Main thread for Day 20 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 20 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

2

Cheating race conditions just sounds like a nightmare, to be completely honest. The puzzle was nice though! Key insight for part 2 was to use Taxicab Geometry to identify potential shortcut endpoints.

https://zigbin.io/5aeacd

3

Had some fun optimizing today. Not sure how to tell Zig that a pointer I have (*self, basically) does not actually change and the fields I am accessing do not need constant fetching from memory. Loading fields into local consts seems to work, but is this the only way?

Anyways.

Source: aoc2024/src/day20.zig at main · p88h/aoc2024 · GitHub
Video: https://www.youtube.com/watch?v=P7IfyW58aOQ

Benchmark:

        parse   part1   part2   total
day 20: 19.1 µs  0.1 ms  0.8 ms  1.0 ms (+-6%) iter=1000
4

18ms: a bit slow because I did not think about only checking the path points at the correct manhattan distance. My solution is clearly n2. Next time I’ll think more.

https://zigbin.io/0862d0