Here is my solution, which takes advantage of the discrete time constraint. It is basically the Chinese Remainder Theorem applied to each axis :
defp part2(input) do
hailstones = parse_input(input)
x = hailstones |> Snap.map(&Vec3.x/1) |> axis_congruence()
y = hailstones |> Snap.map(&Vec3.y/1) |> axis_congruence()
z = hailstones |> Snap.map(&Vec3.z/1) |> axis_congruence()
x + y + z
end
defp axis_congruence(axis_hailstones) do
-@velocity_boundary..@velocity_boundary
|> Stream.flat_map(fn rock_velocity ->
axis_hailstones
|> Enum.reject(&(Snap.velocity(&1) == rock_velocity))
|> Enum.map(&(&1 |> Snap.position() |> Cong.new(Snap.velocity(&1) - rock_velocity)))
|> Enum.reduce([], fn congruence, coprimes ->
if Enum.all?(coprimes, &(&1 |> Cong.m() |> Integer.gcd(Cong.m(congruence)) == 1)) do
[congruence | coprimes]
else
coprimes
end
end)
|> :crt.chinese_remainder()
|> case do
:undefined ->
[]
rock_position
when rock_position < -@position_boundary or rock_position > @position_boundary ->
[]
rock_position ->
if Enum.all?(
axis_hailstones,
&will_collide?(&1, Snap.new(rock_position, rock_velocity))
) do
[rock_position]
else
[]
end
end
end)
|> Enum.at(0)
end
defp will_collide?(hailstone, rock) do
maybe_null_delta_position = Snap.position(hailstone) - Snap.position(rock)
maybe_null_delta_velocity = Snap.velocity(rock) - Snap.velocity(hailstone)
case {maybe_null_delta_position, maybe_null_delta_velocity} do
{0, 0} ->
true
{_, 0} ->
false
{delta_position, delta_velocity} ->
time = delta_position / delta_velocity
time > 0 and time == round(time)
end
end
I allowed myself to use an Erlang implementation of the CRT to save me some time during Christmas days, but its Elixir translation should not be a problem.
Vec3, Cong and Snap are basic helper modules used to manipulate {x, y, z}, {modulo, remainder} and {position, velocity} tuples and make the code more readable.
It uses ranges of velocities and positions that I consider plausible for this exercise (essentially by looking at input magnitudes).
The tricky part (at least in my input) is that the rock can have the same position and/or velocity that some hailstones. It has to be considered to choose the inputs used for the CRT and to build the scenarios which will lead to a future collision or not.
I’m not so sure that it will solve the problem for any input, but it did the job for me !
