You’re not supposed to put your actual answers in public posts, but I did because I worked so hard for that answer. And I’m still working hard trying to figure out the answer.
In today’s problem, you’re in a server room and you’re trying to find the number of possible data paths from a particular server (labeled “you” by a friendly elf) to the output. The elf explains helpfully that the servers are connected by one way connections with no loops.
Oh, so this is a Directed Acyclic Graph (DAG). I wonder if that will turn out to be important later on?
Well, I know how to write a breadth first search — did it yesterday — but how about a depth first search? And I know about memoization. And you know what? It worked, it was fine, I got the Part 1 answer easily.
While at work, I couldn’t help peeking at the Part 2. Instead of starting at the “you” server, we’d be starting at the “svr” server, and instead of going to “out” directly, we were only interested in paths that also went through the “fft” (Fast Fourier Transform?) and “dac” (Digital / Analog Converter?) servers. Clearly we add the number of paths from svr -> fft -> dac -> out to the number of paths from svr -> dac -> fft -> out, and we’d be done.
WRONG. OUT OF MEMORY. AGAIN.
I thought I was clever. I said, “Fine! I’ll write it in Java just to be different, turn in that answer, and claim partial success.”
But. Out of memory. The reason comes down to my memoization. Since the DAG could arrive at a particular node via many paths, I couldn’t just keep a count at the node, I had to keep a count keyed to the entire path to reach that node. And that was a lot. It was sheer luck that the Part 1 path was relatively simple.
I did some more research and found out about Kahn’s algorithm. This method is used when tasks depend upon previous tasks being done; you want to ensure the tasks are done in the correct order. It reorders the nodes so that a node never has a dependency on a previous node, then does a Breadth-first search, not a Depth-first search, calculating each level along the way, such that there’s only one path to a node by the time you get to that node. There is no memoization, no caching, just the topological sorting and the edge counts that, summed, provide the answer.
Python has a built-in library that just does this, but I didn’t want to have to run a Python solver in the background like I did for yesterday’s, so I found some code and adapted it for Picotron.
And it worked, no fuss, no bother, super fast. I’ll have to read through it a few times to understand why it works, but Advent of Code exists, at least in part, to get people familiar with these sorts of algorithms.
Sometimes I feel I should have a master’s in graph theory to participate… Probably wouldn’t hurt.
Leave a Reply