Mostly code

# Advent of Code 2019: Day 12

13 Dec 2019 I see I am trying not to crash today. I’ve been given some pretty simple instructions on how to handle tracking how gravity applies to the moons, so first I’ll go about implementing that. A moon can be a map that contains its position and its velocity: `%{p: {0, 0, 0}, v: {0, 0, 0}}`

``````  defp apply_velocity(%{p: {x1, y1, z1}, v: {x2, y2, z2} = v}) do
%{p: {x1 + x2, y1 + y2, z1 + z2}, v: v}
end

defp set_velocity(%{p: p1, v: v1}, %{p: p2}) do
%{p: p1, v: apply_gravity(v1, gravity_diff(p1, p2))}
end

defp apply_gravity({x1, y1, z1}, {x2, y2, z2}) do
{x1 + x2, y1 + y2, z1 + z2}
end

defp gravity_diff({x1, y1, z1}, {x2, y2, z2}) do
{gravity_diff(x1, x2), gravity_diff(y1, y2), gravity_diff(z1, z2)}
end

defp gravity_diff(p1, p2) when p1 > p2, do: -1
defp gravity_diff(p1, p2) when p1 == p2, do: 0
defp gravity_diff(p1, p2) when p1 < p2, do: 1
``````

`apply_gravity/2` takes the positions of 2 moons, and computes how gravity affects the velocity of the first moon. `gravity_diff/2` takes two positions and calculates how gravity affects the first moon by returning a differential, such as `{-1, 1, 0}`. `set_velocity/2` uses the above two functions to apply gravity to the first moon, as computed above, and `apply_velocity/1` alters the given moon’s position by its velocity. All that’s left is to chunk the moons through it for 1000 steps and calculate the final energy output.

``````  def p1(), do: s1(input_stream(), 1000)

def s1(stream, x) do
moons = Enum.map(stream, &parse/1)

Range.new(1, x)
|> Enum.reduce(moons, fn _, moons -> run_step(moons) end)
|> Enum.map(fn %{p: {x1, y1, z1}, v: {xv, yv, zv}} ->
(abs(x1) + abs(y1) + abs(z1)) * (abs(xv) + abs(yv) + abs(zv))
end)
|> Enum.sum()
end

defp run_step(moons) do
moons
|> Enum.map(fn moon ->
Enum.reduce(moons -- [moon], moon, fn m1, m2 ->
set_velocity(m2, m1)
end)
end)
|> Enum.map(&apply_velocity/1)
end
`````` one done.

## Puzzle 2

Oh jeez… Time to discuss time complexity. The puzzle clearly states that I probably can’t just straight run the simulation for that long, which is too bad, because now I need to research what I can do instead. Well, for starters, the dimensions are independent of each other, so I could theoretically compute all the moon’s `x`, `y`, and `z` position cycles separately, which gives 3 cycles, the `x` cycle, the `y` cycle, and the `z` cycle. After that, I just need to find the number of cycles it takes for those sub-cycles to line up.

Again, too big of a number to just continually add numbers to until I figure it out. As with all my greatest works, the next step is to Google the problem.

Googling says something about the least-common multiple (LCM), which rings a bell. What does Wikipedia say? “It is the smallest positive integer that is divisible by each of them.” BOOM that is exactly what I’m looking for!

Let’s say I have 2 cycles, 2 and 5. The least common multiple here is 10. It’s also very clearly the first number where the cycles line up!

OK, so I have my cycles, all that’s left is to compute the LCM for the three of them. The easiest formula involves the greatest common divisor (GCD). Fortunately for us, there is `Integer.gcd/2`. Oh, it only takes 2 numbers… back to the Wikipedia page! Wikipedia suggests that ```lcm(a, lcm(b, c)) == lcm(lcm(a, b), c)```, so I can compute the LCM of one pair and use it to compute the LCM of the pair and another and so on until I’m done. All that’s left is to compute! I am adjusting the format of data to be three lists of tuples, one per axis, where the first element of the tuple is the position and the second element is the velocity, which means I need some different functions for computing movements.

``````  def p2(), do: s2(input_stream())

def s2(stream) do
moons = Enum.map(stream, &parse/1)

moons
|> Enum.map(fn %{p: {x, y, z}, v: {xv, yv, zv}} -> [{x, xv}, {y, yv}, {z, zv}] end)
|> Enum.reduce([[], [], []], fn [x, y, z], [xs, ys, zs] ->
[[x | xs], [y | ys], [z | zs]]
end)
1
|> Stream.iterate(&(&1 + 1))
|> Enum.reduce_while(ps, fn c, moons ->
moons = run_step(moons)

if moons == ps do
{:halt, c}
else
{:cont, moons}
end
end)
end)
|> Stream.map(fn {:ok, x} -> x end)
|> Enum.reduce(1, fn x, y -> div(x * y, Integer.gcd(x, y)) end)
end

defp apply_velocity({p, v}), do: {p + v, v}

defp set_velocity({p1, v1}, {p2, _v2}) do
{p1, apply_gravity(v1, gravity_diff(p1, p2))}
end

defp apply_gravity(p, v), do: p + v
``````

For speed, I can use `Task.async_stream/3` to compute the cycles in parallel, and then funnel them into a final `Enum.reduce/3` to compute the least common multiple! The result is: huh, a very, very, humungous number. No wonder I had to put all this work into a math-y solution.

## Conclusion

To be honest, I don’t really like these puzzles where there’s a “trick” to them. If I didn’t Google or knew about least-common multiples, I’d be stuck staring at this puzzle for a very long time. I could’ve maybe pencilled out the idea of a solution, but would’ve needed to look up some formulae on how to compute the thing. Which is to say, it’s not so much about building a solution but finding one. Anyway, maybe day 13 will be more my style?