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)
|> Task.async_stream(fn ps ->
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?