Advent of Code 2019

The story of my slow descent into madness

View on GitHub
6 December 2019

Day 6: Universal Orbit Map

by Simon Berger

Links:

“About time we start with the graph theory problems”, I thought to myself while reading through the puzzle’s description. But when I started working on my solution I quickly realised that I had forgotten quite a lot about graph theory. After a while it came back to me, but it did take a lot longer than I’m comfortable admitting.

I consciously made the decision not to use a dedicated graph library yet, but I’m sure I’ll get the chance to use the lovely petgraph again this year.

Anyway, I still haven’t really found what I actually want to write about. I would like to explain what my process was but today went as smooth as somehow possible so I don’t even have any mishaps to talk about. I could go over how my solution works but I feel that wouldn’t really be interesting, but maybe I’m wrong, so let’s try it.

How I did the thing

We know that the relationship between “orbiter” (satellite) and “orbitee” (parent body) is many to one (i.e. a body can have multiple satellites, but a satellite only orbits one parent body). The input we’re given is a mapping from body to satellite though, so the first thing we need to do is reverse this relationship. We can build a unique mapping from satellite → parent body which is way easier to work with. This gives us a graph, or rather, it can be seen as a graph. A directed acyclic graph (DAG) in fact. In this graph vertices are the objects and edges describe the “is orbiting” relationship. If there is an edge (keep in mind that we’re talking about directed edges here) from one object to another, said object is orbiting the other one.

Treating this as a graph isn’t strictly necessary, but it allows us to use the incredibly rich “ecosystem” that exists for graphs already, such as many useful algorithms.

Part 1

In part one we’re trying to find the total amount of direct and indirect orbits. Since we treat the “is orbiting” relationship as an edge in our graph, we’re basically summing up the amount of reachable (connected) vertices for each and every vertex.

I’m not 100% sure on this, but I think normally the amount of reachable vertices would include the vertex as well (i.e. a vertex without any edges would still have a count of 1). As per the definition of the puzzle we don’t want to count that though, we only care about vertices other than itself.

To do this efficiently we can generate what I called a “depth map”. That definitely isn’t an appropriate term and I don’t really understand why I chose it, but let’s just roll with it because I can’t be bothered to come up with something else. This structure maps each vertex to the amount of reachable vertices (i.e. the amount of direct and indirect orbits). To solve the puzzle all we have to do is add up the values of this depth map.

But the question is, how do we generate said map? The answer is using a memoized recursive approach. Basically this means that we take each vertex and count the amount of vertices we can reach by repeatedly following the edge (there can only ever be one edge, remember) until we reach a vertex with no outgoing edges (i.e. a sink vertex). This is a bit of an inefficient approach, it has an asymptotic runtime of , where n is the amount of vertices in the graph. Most of the runtime is wasted traversing the same vertices over and over again, which is something we can solve using memoization.

Now, instead of following an edge we first check whether we already know the “depth” of the neighbouring vertex. If we do, we know that this vertex’s depth is just that plus one. If, however, we don’t already know it, we first determine its depth using this same approach. That way, every vertex is only traversed once, which makes the approach .

Part 2

To put it in terms of graph theory, the second part requires us to find the shortest path between two vertices, namely santa and us. For this to work, we must now treat the graph as undirected. This means that if there is an edge between two vertices, one can go over the edge in both directions.

Don’t worry, we don’t have to change the data structure we’re using, we can use an approach that nicely builds on the first part.

We know that both santa and us must have a path to the sink vertex. Finding these paths is basically what we did in the first part. All we have to change is that instead of counting each vertex, we add it to a list (in reverse order so we get the path starting from the sink). We can now use the fact that the last vertex both paths have in common (“LCV”) has to be part of the path between santa and us. To get the length of this path we can add up the lengths of the two paths (santa → LCV) and (LCV → us).

I’m not going to explain why that is true, but if you look at the graph illustration from the puzzle’s description you should be able to see that it is.

Here’s an illustration focusing on the important vertices:

                           US
                          /
            -         - -
          /         /
   SINK - - - LCV - - - -
                \
                  - SANTA

To find the last common vertex, we iterate over both paths at the same time and compare the vertices until they are no longer equal. It’s important to determine the index of the LCV in the path.

Now that we know the LCV and its index in the path, we can easily determine the length of the paths (LCV → santa) and (LCV → us) by subtracting the length of the path (sink → LCV) from the length of their paths to the sink. The length of (sink → LCV) is just .

Don’t forget to add one, otherwise you might run into a fencepost error.

One last thing is to subtract 2 from the result. This is because we’re interested in the amount of transfers required to orbit the object santa is orbiting, so the two endpoints (santa and us) are excluded from the length.

Conclusion

I went over how to solve today’s puzzles pretty extensively I think and it took up a lot of my time. I can’t really tell whether it was worth it. I think for the coming days I will only really talk about the how when I find that I have something to say about it.

As for today, I don’t really think that my solutions were particularly interesting. The second part, maybe, because I could see some people solving it differently.

Anyway, I’m content for today, ‘till tomorrow, then!

tags: graph theory
Overview
Previous day Next day