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 because that’s the worst-case size of the frontier.
So, the worst-case space complexity of DFS is .
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. Perhaps it’s a matter of better preprocessing.