Advent of Code 2019, Day 6

Today was fun; it involved trees and searching. To paraphrase the problem, given a tree of orbits, count the total number of orbits and find the number of orbital manuevers needed to get to Satan.

I've written a bunch of trees before and I kind of wanted to play around implementing some data structures, so I implemented a graph and a queue set. It does mean there's a lot of code today... 190 lines (339 with test code).

Part 1

The first data structure I wrote was the graph.

type Graph struct {
        nodes   map[string]bool
        edges   map[string]map[string]bool
        reverse map[string]map[string]bool
}

The reverse field is used to map parent relationships. In the case of the orbits here, edges will only have one connection (because it's a tree) while reverse maps the child connections. The reverse field was added in part 2 when I realised I had things backwards. It was faster to just add in reverse, but if I was going back to clean things up, I'd consider doing things differently. Notably, though, the relationship in this is a little inverted because in order to count orbits, I want to be to follow a node up to the root of the whole system. The root node ('COM') should be counted, either.

func NewGraph() *Graph {
        return &Graph{
                nodes:   map[string]bool{},
                edges:   map[string]map[string]bool{},
                reverse: map[string]map[string]bool{},
        }
}

func (g *Graph) LinksFrom(node string) (edges []string) {
        for e := range g.edges[node] {
                edges = append(edges, e)
        }
        return
}

func (g *Graph) Add(node string) {
        g.nodes[node] = true
}

The naming here is based on the terminology in the problem statement - 'obj' orbits 'com' (the center of mass); I kept it here because it helped me to think in terms of the problem statement.

func (g *Graph) Link(obj, com string) {
        if g.edges[obj] == nil {
                g.edges[obj] = map[string]bool{}
        }

        g.edges[obj][com] = true

        if g.reverse[com] == nil {
                g.reverse[com] = map[string]bool{}
        }
        g.reverse[com][obj] = true
}
CountFor tries to count the number of orbits for a node; really,
it's counting the number of edges. It does this by checking to see if the node has any edges; the root node, for example, shouldn't have any edges. Then it recursively calls itself for each node that it's connected to. The total of all of these is returned.
func (g *Graph) CountFor(node string) int {
        if !g.nodes[node] {
                return 0
        }

        if g.edges[node] == nil {
                return 0
        }

        count := 0
        for node := range g.edges[node] {
                count++
                count += g.CountFor(node)
        }

        return count
}

Count applies CountFor to each node that has an edge. This is necessary because even shared edges count. That is,

Visually, the above map of orbits looks like this:

G - H J - K - L
/ /
COM - B - C - D - E - F
I

In this visual representation, when two objects are connected by a line, the one on the right directly orbits the one on the left.

Here, we can count the total number of orbits as follows:

  • D directly orbits C and indirectly orbits B and COM, a total of 3 orbits.
  • L directly orbits K and indirectly orbits J, E, D, C, B, and COM, a total of 7 orbits.
  • COM orbits nothing.
  • The total number of direct and indirect orbits in this example is 42.

I'm sure there's a better way.

func (g *Graph) Count() int {
        count := 0
        for node := range g.edges {
                count += g.CountFor(node)
        }
        return count
}

func (g *Graph) AddOrbit(entry string) {
        odata := strings.SplitN(entry, ")", 2)
        com := odata[0]
        obj := odata[1]
        g.Add(com)
        g.Add(obj)
        g.Link(obj, com)
}

func (g *Graph) LoadMap(entries []string) {
        for _, entry := range entries {
                g.AddOrbit(entry)
        }
}

This is enough to get me to an answer for part 1:

func loadMap() {
        file, err := os.Open("navmap.txt")
        die.If(err)
        defer file.Close()

        scanner := bufio.NewScanner(file)
        for scanner.Scan() {
                universalOrbitMap = append(universalOrbitMap, strings.TrimSpace(scanner.Text()))
        }

        return
}

func part1() {
        g := NewGraph()
        g.LoadMap(universalOrbitMap)
        if len(universalOrbitMap) != expectedMapSize {
                panic(fmt.Sprintf("universal map should be %d but is %d!",
                        expectedMapSize, len(universalOrbitMap)))
        }
        fmt.Println(g.Count())
}

Yeah, you could just maintain counters for everything, but now I have a graph, which turned out to be useful for part 2.

I ran into some trouble for a minute where my tests passed but the answer wasn't right. I decided to try reversing the order of the inputs in the test code, and what do you know - the code broke. That let me zero in on where I was running into trouble.

Part 2

Part two requires that we find a path between two nodes. Since breadth-first search will always find the shortest path length (which is what the problem calls for) between any two nodes in a graph, it makes the most sense to use it. It's also pretty straightforward.

While writing the BFS over my graph, I wanted to keep a set of seen nodes and a set of frontier nodes. At first, I used a separate map and slice, but then I decided to try writing a combined data structure. I called it a QueueSet but it's sort of an uninspired name. The idea was that I could use a QueueSet to keep a frontier that only enqueued nodes it had seen before.

// A QueueSet is a queue with fast lookups. It maintains both a hash
// table and an array for the objects in the set. The QueueSet keeps
// history; items are never removed from the set.
//
// The motivation was that I want to be able to basically range over
// an ordered dictionary while adding and removing elements as needed.
// That is, you can do something like
//
// for !qs.Empty() {
//     // add or remove from qs
// }
type QueueSet struct {
        m map[string]bool
        s []string
}

func NewSet(initial string) *QueueSet {
        return &QueueSet{
                m: map[string]bool{initial: true},
        }
}

func (s *QueueSet) Has(v string) bool {
        return s.m[v]
}

func (s *QueueSet) Empty() bool {
        return len(s.s) == 0
}

func (s *QueueSet) Pop() string {
        v := s.s[0]
        s.s = s.s[1:]
        return v
}

func (s *QueueSet) Add(x string) {
        if !s.m[x] {
                s.m[x] = true
                s.s = append(s.s, x)
        }
}

func (s *QueueSet) AddList(xs []string) {
        for _, x := range xs {
                s.Add(x)
        }
}

It feels straightforward to me (famous last words!) - a queue with a set bolted on. I could see a use case for this where history isn't kept, but for a BFS frontier, this is what's useful. I added an initial string to NewSet because I knew in this problem I'd want to initialise it with the starting node.

I also knew I'd need to be able to get the neighbours of a node, which extends in both directions. However, at this point, the edges field only tracked one-way edges. I added a reverse field to the graph structure, and a method Neighbours to return a list of all the neighbourly nodes.

func (g *Graph) Neighbours(node string) []string {
        neighbours := make([]string, 0, len(g.edges[node])+1)
        for k := range g.edges[node] {
                neighbours = append(neighbours, k)
        }

        for direct := range g.reverse[node] {
                neighbours = append(neighbours, direct)
        }

        return neighbours
}

The BFS is implemented more or less as:

  1. Initialise a frontier QueueSet.
  2. Set up a map that can keep track of where we came from: every time we add a node to the frontier, we add a mapping from that node to the current node. This was actually the biggest stumbling block for me; I'd forgotten how to trace a path with a BFS - looking through my old notes reminded me about the cameFrom structure.
  3. Add all the neighbours of the current node to the frontier set, marking where they came from.
  4. As long as the frontier set has nodes or we find the node we're looking for, keep going through the process of popping a node off the frontier and adding its neighbours to the frontier.
  5. Finally, use the cameFrom structure to build the path back - starting with the end node, find which node it came from. Then, find out which node that one came from, repeat until we're at the start. Then reverse this list and call it a day.
func (g *Graph) Search(from, to string) []string {
        frontier := NewSet(from)
        cameFrom := map[string]string{}

        start := from

        for _, neighbour := range g.Neighbours(from) {
                cameFrom[neighbour] = from
                frontier.Add(neighbour)
        }

        for !frontier.Empty() {
                node := frontier.Pop()
                if node == to {
                        break
                }

                for _, neighbour := range g.Neighbours(node) {
                        if !frontier.Has(neighbour) {
                                cameFrom[neighbour] = node
                                frontier.Add(neighbour)
                        }
                }
                from = node
        }

        paths := []string{}
        for to != start {
                paths = append(paths, to)
                to = cameFrom[to]
        }
        paths = append(paths, to)
        for i := 0; i < len(paths)/2; i++ {
                j := len(paths) - i - 1
                paths[i], paths[j] = paths[j], paths[i]
        }

        return paths
}

Finally, the problem says we need to count the number of orbital transfers, which turns out to be our path minus the first and last nodes ('YOU' and 'SAN'); we want to traverse between the parents of these nodes. My solutions takes advantage of the fact that because my graph is actually a tree, each node has exactly one edge: the body it orbits.

func part2() {
        g := NewGraph()
        g.LoadMap(universalOrbitMap)
        if len(universalOrbitMap) != expectedMapSize {
                panic(fmt.Sprintf("universal map should be %d but is %d!",
                        expectedMapSize, len(universalOrbitMap)))
        }

        paths := g.Search(g.LinksFrom("YOU")[0], g.LinksFrom("SAN")[0])
        fmt.Println(len(paths))
}

For completeness, here's my instrumentation output:

day06p0: complete in 173us, total allocated 157 kB,
current heap allocation 157 kB
day06p1: complete in 42313us, total allocated 1201 kB,
current heap allocation 1201 kB
day06p2: complete in 2939us, total allocated 2620 kB,
current heap allocation 2620 kB

My BFS is fairly efficient but my edge counter is not. This code isn't really good, but it was fun to explore the data structures.


Tags: ,