exists
Advent of Code 2023 - Day 24
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)
Most Liked
antoine-duchenet
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 !
bjorng
I gave up on trying to solve part 2 by myself and looked for hints on reddit. Here is my solution:
Popular in Challenges
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Build Elixir applications with speed and confidence.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
The deployment platform built for Elixir: PaaS ease, VPS control.
Courses that'll move you from confusion to "Aha, now I get it!"