AoC 2024: Day 18

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

Source: aoc2024/src/day18.zig at main · p88h/aoc2024 · GitHub
Video: https://youtu.be/0Gd85UbHVIE

BFS + binary search in main source, iterative BFS (on broken paths only) in visualisation.

Benchmark:

        parse   part1   part2   total
day 18: 22.1 µs 15.7 µs 24.6 µs 62.5 µs (+-1%) iter=19110
1 Like

Binary Search implementation could be cleaner, but it’s late :smiley:

https://zigbin.io/510cbd

Under 0.4ms. I thought doing a binary search would be enough to have good performance, but as p88h shows, I should have done iterative BFS. Anyways, at least I am not using priority queues anymore when a simple queue works. I am lagging behind a bit, I think I’ll take a more breaks and finish during Christmas vacation. Day 17 part 2 humiliated me.

The Zig Pastebin , using array The Zig Pastebin