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.