Andrew Fontaine

Mostly code

Advent of Code 2019: Day 6

08 Dec 2019
Code Snippet for Advent of Code 2019: Day 6

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 =
      |> x -> x |> String.split(")") |> List.last() end)
      |> x -> build_tree(list, x) end)

    %{p: p, children: c}

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 |>, t + 1)) |> Enum.sum() |> Kernel.+(t)

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)

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)

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

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


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