After looking up the formula for calculating an intersection of two lines on wikipedia, part 1 was straightforward. I really do not know how would I go about solving part 2 in a programming language like elixir… I am hoping someone here would have a better idea than what I’ve done:
I did part 2 basically by a direct calculation: the observation is that already any three of the given lines determine the starting position and the direction of the rock throw (assuming of course that a global solution exists!). So I took three lines, worked out three equations with three variables (non-linear though) that determine what’s happening, asked wolfram alpha to find a solution, and calculated the starting point.
code for part 1
defmodule Main do
def run() do
get_input() |> Enum.map(&parse/1) |> solve1()
end
def get_input() do
# "testinput24"
"input24"
|> File.read!() |> String.trim() |> String.split("\n")
end
def parse(l) do
for e <- (l |> String.split(" @ ")) do
e |> String.split(", ")
|> Enum.map(&String.trim/1)
|> Enum.map(fn s -> String.to_integer(s) end)
|> List.to_tuple()
end
end
def line_intersection_2d([{x0,y0,_},{u0,v0,_}],[{x1,y1,_},{u1,v1,_}]) do
if u0 * v1 - u1 * v0 == 0 do {:parallel, nil}
else
t = ((x1-x0)*v1 - (y1-y0)*u1) / (u0*v1-v0*u1)
s = ((x1-x0)*v0 - (y1-y0)*u0) / (u0*v1-v0*u1)
cond do
t < 0 or s < 0 -> {:past, nil}
true -> {:fine, { x0 + t*u0, y0 + t*v0 } }
end
end
end
def check_bbox_2d({:fine, {x,y}}) do
# {test_l,test_u} = {7,27}
{test_l,test_u} = {200000000000000,400000000000000}
test_l <= x and x <= test_u and test_l <= y and y <= test_u
end
def check_bbox_2d(_), do: false
def solve1(ls) do
for {l1,i} <- Enum.with_index(ls), {l2,j} <- Enum.with_index(ls), i<j do
line_intersection_2d(l1,l2)
|> check_bbox_2d()
end
|> Enum.filter(fn t -> t end) |> Enum.count()
end
end
:timer.tc(&Main.run/0) |> IO.inspect(charlists: :as_lists)
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 !
Ooh, nice this is very similar to what I came up with, the only significant differences being, that I wrote a CRT implementation that deals with compatible non-coprime congruences (which I shamelessly stole from a CRT implementation on CPAN written in XS), and that I treat the the found starting points in each axis as “candidates” where I also keep track of “at what t did it intersect a particular snowball”.
Then I filter on each axis for only the candidate that has the same intersection orders (at same t) in the other axes, which to me guarantees a correct result.
I did spent waaaaay too much time coming up with the fact that CRT can even be used here and why would that even work, and then actually trying to implement it from scratch
