Mostly code

# Advent of Code 2019: Day 6

08 Dec 2019 Today, I’m pretty much playing Kerbal Space Program and planning some orbital trajectories. As shown in the problem itself, a tree is the perfect way to represent the orbits, so building one shouldn’t be too hard.

``````  defp build_tree([], node), do: node

defp build_tree(list, p) do
connections = Enum.filter(list, &String.starts_with?(&1, p))

list = Enum.filter(list, fn x -> x not in connections end)

c =
connections
|> Enum.map(fn x -> x |> String.split(")") |> List.last() end)
|> Enum.map(fn x -> build_tree(list, x) end)

%{p: p, children: c}
end
``````

`list` here is the list of connections I’m given, in the form of `AAA)BBB`, and `p` is the object that I am finding satellites of. First, I find all the connections by filtering the list for lines that start with the payload, and then for each child I build a tree with that child as the root. Once all the lines are filtered out, the tree is complete.

The goal is to compute how many direct and indirect orbits there are. For an object, the total number of indirect and direct orbits is simply its depth in the tree, so the total number of orbits in the whole tree is the sum of the depth of each node. There is a lovely recursive solution for that.

``````  defp total_orbits(node, t \\ 0)
defp total_orbits(%{children: []}, t), do: t

defp total_orbits(%{children: c}, t) do
c |> Enum.map(&total_orbits(&1, t + 1)) |> Enum.sum() |> Kernel.+(t)
end
``````

Print out the result and that’s one done.

## Puzzle 2

I know where Santa is! Now to calculate the fewest transfers between him and me. If I reduce the tree to the smallest tree that contains both nodes, the depth of each node’s parent will add up to the number of transfers required to reach my destination.

First to minimize the tree. If any of a node’s children contain both the nodes I’m looking for, I search that child’s children and so on. To handle checking if a tree contains a node, I check if its subtree contains the node until there’s only one node left.

``````  defp contains?(%{p: p}, p), do: true
defp contains?(%{children: [], p: _p}, _x), do: false
defp contains?(%{children: c}, x), do: Enum.any?(c, &contains?(&1, x))

defp minimize_tree(%{children: c} = node, a, b) do
case Enum.find(c, fn x -> contains?(x, a) and contains?(x, b) end) do
nil -> node
tree -> minimize_tree(tree, a, b)
end
end
``````

It’s not exactly the most computationally efficient method, as I am descending the depths of the tree a lot, but I was trying to finish this over lunch.

Once the smallest tree is found, I just need to calculate the depth of the node’s parents, which is very close to the above.

``````  defp depth(node, p, t \\ 0)
defp depth(%{children: [], p: p}, p, t), do: t - 1

defp depth(%{children: c}, p, t) do
child = Enum.find(c, &contains?(&1, p))
depth(child, p, t + 1)
end

defp total_moves(tree, a, b) do
node = minimize_tree(tree, a, b)
depth(node, a) + depth(node, b)
end
``````

And with that, the problem is solved! Two received.

## Conclusion

Another day with no tests. I remember these tree algorithms from school, so I was confident in my solution. It is a touch slow, at around 1.5 seconds, which I find interesting. I am a little curious to try and find out what my bottleneck is here, but not enough to sit down and figure it out.

I ❤ feedback. Let me know what you think of this article on Twitter @afontaine_ca