2024 Day 10: Hoof It

Advent of Code
1

This is the first time I’ve written DFS without having to look it up! :slight_smile:

2 Likes
2

What does DFS mean? I followed a different algorithm, I think: the spreading oil drop. In 10 iterations, you move the edge of the oil spill from each ‘0’ to ‘9’. Because of the way the problem is described, very little admin is needed, For the second problem, you only need to sum the directly preceding neighbours.

3

First, I’ve recycled AoC 2022, Day 12, which uses Dijkstra’s algorithm.
Then, for part 2, I’ve tried to search the different paths by modifying the map after each successful search. But a voice from the clouds told me that I was on the path to overcomplicate things.
So I’ve implemented a depth-first search (DFS) for part 2. Finally I’ve thrown away Dijkstra’s algorithm also for part 1. The hiking procedure now is the same for both parts with a little special treatment for part 1: hac/exm/aoc/2024/aoc_2024_10.adb at 6af8d3c53f3c8e929921045235a4d5b1073f6842 · zertovitch/hac · GitHub

4

Interesting that you guys applied depth-first search. (@tgv follow the link for an explanation of DFS)

For Part 1, I performed breadth-first search. (@tgv I think that’s the similar to the spreading oil drop, but perhaps not quite the same. Depends on whether you pruned oil that came to the same spot more than once.)

For Part 2, I wasted way too much time trying to find a clever combinatorial formula. Maybe there is one (I’ll check Reddit in a moment) but either I lacked sufficient information or I am too dumb to work it out. I did think about applying DFS but it’s been quite a while since I’ve implemented one.

It occurred to me that, since we know the trailheads and their corresponding summits (I had saved that information) it should be straightforward to follow all the paths possible down from the summits. So I used another breadth-first search, going backwards this time, using Manhattan distance to prune points that wander off a legitimate trail. Worked like a charm!

(After a couple of rounds of debugging, that is. I do some really dumb things sometimes…)

1 Like