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:
https://github.com/bjorng/advent-of-code-2023/blob/main/day24/lib/day24.ex
Popular in Challenges
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Deploy Phoenix to your own VPS with PaaS ease: push-to-deploy, zero downtime, auto SSL, managed Postgres. 14-day free trial at potions.io
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #advent-of-code
- #elixirconf-us
- #distillery
- #processes
- #forms
- #api
- #metaprogramming
- #security
- #performance
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.
Error tracking for Elixir devs who love to ship. Start your free account.
Practical resources that improve the lives of professional developers.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"