# 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 - FIIn 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:

- Initialise a frontier QueueSet.
- 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. - Add all the neighbours of the current node to the frontier set, marking where they came from.
- 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.
- 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.