I'm not sure if Advent of Code is the cause of, or the salve for my nagging urge to code. But, I've decided to give it a try this year. I am not a competition coder, so you'll never see my name on the leaderboard. But, it's Day 12, and I've had fun solving each problem so far. I think some of the tasks are getting interesting, so I'm going to try out a blog series about my solutions.
A quick aside before I get started with the first post. The code you'll see here is of quick-script quality (plus the tiny amount of cleanup I couldn't bare to leave undone before blogging). The goal of each Advent of Code project is to answer a question about a known input. There are no restrictions or bonuses for runtime, memory use, lines of code, etc. There are no unexpected third-party behaviors, no undocumented pieces of the spec (so far). If you can figure out the answer using paper and pencil, you get a star. I have some issues with this related to the marketing of the contest, but the truth is that this aligns with a lot of the code I've been writing this year, and I think a lot of the code people actually produce, even though we sometimes only "count" stuff that makes it into a shipped product. We live in a data-driven society (even when there are glaring examples of people ignoring or misinterpretting it), and building the skills to consume and analyze data to get information to answer your questions, is worthwhile.
Also, it's basically a crossword-sized puzzle that's just fun to sit with for a few minutes each day.
As I write this, it's Day 12. Working through today's puzzle played a big role in my decision to write about these puzzles. So, I'm going to start here, and see whether I can catch up with posts about Days 1-11, or if I'll even be able to stay on-pace with Days 13-25. I promise not to post about Day N until at least late in Day N my time (US Central), how about that?
Okay, on to the solutions. When I read the description of the first part of Day 12, my initial thought was, "Ah, we've finally gotten to a problem that requires some specific knowledge about graph theory or path plotting," which is stuff that I'm not well versed in. (You all know that's academic speak for, "I don't know," right?) As I wondered what it would take to brute-force a solution, I realized my initial thought was wrong. The solution to this puzzle is depth-first traversal!
I didn't think of depth-first traversal to start with, because I usually think of it in the context of depth-first search on a tree, or at least a directed acyclic graph, where the algorithm hopes to find a specific leaf. DFS on an undirected graph usually brings with it the extra complication of needing to track where you've been to avoid going around in circles forever. But it turns out this requirement is built into the puzzle anyway - certain nodes ("small caves") are only allowed to be visited once.
I'm writing in a functional language, so my depth-first traversal will take a recursive form. Each step will be given the name of the current cave, and a representation of the cave network. The key detail will be that the network passed to each recursion will have removed from it, caves that we are not allowed to return to. So the size of the network will be weakly decreasing. In theory, that's not enough to ensure that we don't end up in a loop, and that we do actually finish. But fortunately we're not dealing with arbitrary input, and the puzzle input has been constructed such that I found no such cases.
Here is my implementation for Part 1:
count_paths(<<"end">>, _) ->
1;
count_paths(Cave, Network) ->
case lists:keytake(Cave, 1, Network) of
false ->
0;
{value, {Cave, Links}, Rest} ->
RealRest = case Cave of
<<C, _/binary>> when C >= $A, C =< $Z ->
[{Cave, Links}|Rest];
_ ->
Rest
end,
lists:sum([ count_paths(L, RealRest) || L <- Links ])
end.My functional language of choice at the moment is Erlang. I'm not going to justify it any further than this: I know the language pretty well, and it has a REPL that allows me to experiment while debugging. Follow me through the explanation, and I think you'll find your initial aversion diminished.
The cave network map is modeled as a list of pairs (tuples) of caves and their links. The count_paths/2 function takes this Network list, and the name of a Cave to start from. To get the answer to the Day's problem, I parse the file into this network-list format, and call this function with "start" as the first cave name.
The base case of the function is when the submarine is at the "end" cave. If that's the case, we've found 1 path to the "end".
The recursion otherwise beings with the removal of the current Cave from the Network. If the Cave has already been visited, it won't be in the Network, as described earlier. If it is false that the Cave is in the remaining Network, then the number of paths to "end" from here is 0, and we can return that without further processing. If the cave has a value in the Network, we first check to see if the cave is one that allows multiple visits (starts with a captial A through Z character). If it is, we add the cave back to the Rest of the network. Finally, we recurse to each of the Links in the cave's link list, passing the, possibly smaller, RealRest of the network. Each of those calls will return the number of paths to "end" from that cave, so we can sum those together to get the number of paths to "end" from this Cave.
Network = [{<<"start">>,[<<"b">>,<<"A">>]},
{<<"A">>,[<<"end">>,<<"b">>,<<"c">>,<<"start">>]},
{<<"b">>,[<<"end">>,<<"d">>,<<"A">>,<<"start">>]},
{<<"c">>,[<<"A">>]},
{<<"d">>,[<<"b">>]},
{<<"end">>,[<<"b">>,<<"A">>]}].
10 = puzzle12:count_paths(<<"start">>, Network).Hooray, that's the example answer! No spoilers - example answers only in these posts! Enjoy the magic of seeing your own execution print the correct answer. :)
Great, so on to Part 2. I tweeted a couple of days ago about taking a while to read and understand the problem. I didn't take long enough my first few times reading this section, and subsequently got wrong answers for far too long. The twist is that we get to visit one small cave twice. Most of my erroneous implementations visited all small caves twice. Ah, well.
count_paths(<<"end">>, _, _) ->
1;
count_paths(Cave, Network, Visited) ->
case lists:keytake(Cave, 1, Network) of
false ->
0;
{value, {Cave, Links}, Rest} ->
{RealRest, NewVisited} =
case Cave of
<<C, _/binary>> when C >= $A, C =< $Z ->
{[{Cave, Links}|Rest], Visited};
<<"start">> ->
{Rest, Visited};
_ ->
case Visited of
complete ->
{Rest, complete};
_ ->
case lists:member(Cave, Visited) of
true ->
{lists:foldl(
fun(V, Acc) ->
lists:keydelete(V, 1, Acc)
end,
Rest,
Visited),
complete};
false ->
{[{Cave, Links}|Rest],
[Cave|Visited]}
end
end
end,
lists:sum([ count_paths(L, RealRest, NewVisited)
|| L <- Links ])
end.I've doubled the number of lines of code for one purpose: remembering which small caves have been Visited in a variable, instead of just implicitly in the call stack. Because we needed only the count of paths, and not a listing of each of them, there wasn't much need to keep them around earlier. Even now, I'm only going to keep the small caves we've visited in this list. Once we revisit a cave that is a member of that list, we can go through the Rest of the network, and delete the small caves we have already Visited, so we don't visit them again. Until that point, we put even small caves back in the RealRest of the network, so we can revisit one of them, just like we do with big caves.
I've made just one small optization: after removing Visited small caves from the Rest of the network, I change Visited from a list into an the atom complete. This makes it easier to tell in deeper recursions that we don't need to re-add small caves to the network, or check if we've visited them, because we've already visited one small cave twice. I see now that I could have pivoted to calling the earlier version of count_paths at this point instead.
36 = puzzle12:count_paths(<<"start">>, Network, []).Hooray! We've found all the paths to the exit, and claimed both puzzle stars. I've left the file parsing out of this explanation. If you're curious about it, or you'd like to tinker with the code for other reasons, I've started a github repo with my complete code to each puzzle.
Did you also write code to find the solution in Erlang? Have questions or suggestions about my Erlang code? Ping me on Github (beerriot). Good luck with your own solutions!
Categories: Development AdventOfCode
Post Copyright © 2021 Bryan Fink