2023 Day 23: A Long Walk

Advent of Code
1

Took me a while to get around to this one, because Day 21 set me back one day. Day 22 was straightforward (more or less) and while I got Day 23, it took a good long while.

Part 1 is straightforward, I think.

For Part 2, breadth-first search on path points took wayyyyy too long, so I built a graph and performed BFS at forks. That gives me the right answer, but it still takes too long (several minutes! with several million paths queued up!), so I went to look at Reddit commentary and there everyone is basically doing what I’m doing, but using depth-first search instead.

I really have to brush up on the advantages of each, since I don’t quite understand why that approach takes them milliseconds, whereas my approach takes minutes.

Added in later: Found my answer on this page:

So, [BFS] space complexity in the worst-case scenario is oldsymbol{O(b^d)} because that’s the worst-case size of the frontier.
…
So, the worst-case space complexity of DFS is oldsymbol{O(bd)}.

Added in much later: I take that back. A straightforward DFS still takes so long that I interrupted it. Also, I misread/misremembered the Reddit: most other implementations take seconds, with 1 or 2 stating they’re in milliseconds. A brief comparison between what they’re doing and what I’m doing… illuminates nothing. :rage: Perhaps it’s a matter of better preprocessing.

2

I (mis)ued a modified flood-fill (this works only because of the way the labyrinth is constructed), with a duplication of maps when ice is found, and try the icy path. The solution for Part 2 is an addition of a relaxed condition on the ice tiles. Built with GNAT, the program runs in ~5 minutes. With HAC it is +/- forever (but it is expected).

3

I don’t quite get this; can you explain?

4

It is easier to explain with the program itself: https://github.com/zertovitch/hac/blob/2ff05655c96bdfe8b0fd4ca90cc6c3aed0919990/exm/aoc/2023/aoc_2023_23.adb#L96

1 Like