Advent Of Code - Day 12
EDIT: I revisited this problem and completely revised my solution to it: Day 12 Updated
This one is a bit different from our little BFS walk the other day. I didn’t quite remember how DFS works, so I looked at the Wikipedia a bit. Then I remembered that I implemented this previously at some point in a later year.
Disclaimer: I didn’t manage to finish part 2. I’m not sure what the bug is, but I moved on. When I’ll have the inspiration, I’ll figure it out. Unless, someone has an idea what’s going on.
Day 12 - Part 1
There isn’t much to decipher this time. It’s basically a graph traversal. Specifically, finding all path in a graph.
With a tiny addition that large caves can be visited as many times as we like. Which just means that we’ll never put
them into the visited
| seen
map.
But first we’ll have to construct our graph. That one is a bit fiddly. I wasn’t sure if the connections are directed
or that there are on connections as in a -> b
and this doesn’t mean that we’ll update the connection for b
to point
back to a
.
I choose to update both connections.
So once, the boring part is done and we managed to parse our graph we’ll have to do a dfs
. We have to find ALL paths
in this graph. For that we’ll collect the path in a global value and do some recursion with dfs. There is an iterative
approach but I find the recursive one more intuitive.
func dfs(curr *node, path []string, seen map[string]struct{}) {
if isLower(curr.value) {
seen[curr.value] = struct{}{}
}
path = append(path, curr.value)
if curr.value == "end" {
paths = append(paths, path)
} else {
for _, next := range curr.connections {
if _, ok := seen[next.value]; !ok {
dfs(next, path, seen)
}
}
}
delete(seen, curr.value)
}
What’s happening here? We only put it into seen
if it’s lower case. This is where the big cave / small cave thing
comes in. Then, we append the currently visiting node to the path. If we reached 'end'
we are done with that part and
we put our path so far into the all paths gathering global value. Then, we delete the current value and return. If it’s
done at that point, it will just unravel and be done.
If we didn’t reach the path so far, we call dfs on each of the neighbors of our current node. So we identified our base case. Which is to check if we are at the end, and save the path. That’s it, we run this and we have our first star.
Day 12 - Part 2
This is where it gets a bit more complex. We’ll have to now allow for a single cave to be visited twice. I’m doing that by looping over all of the small caves and adding them into a seenTwice map. But for some reason, I’m not getting the right value yet. We’ll get back to that.
Conclusion
The repository for all my solutions for AOC 2021 can be found here.
Thank you for reading!
Gergely.