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() |> |> solve1()

  def get_input() do
    # "testinput24"
    |>!() |> String.trim() |> String.split("\n")

  def parse(l) do
    for e <- (l |> String.split(" @ ")) do
      e |> String.split(", ")
      |> s -> String.to_integer(s) end)
      |> List.to_tuple()

  def line_intersection_2d([{x0,y0,_},{u0,v0,_}],[{x1,y1,_},{u1,v1,_}]) do
    if u0 * v1 - u1 * v0 == 0 do {:parallel, nil}
      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 } }

  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
  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
      |> check_bbox_2d()
    |> Enum.filter(fn t -> t end) |> Enum.count()
end |> IO.inspect(charlists: :as_lists)
1 Like

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 |> |> axis_congruence()
    y = hailstones |> |> axis_congruence()
    z = hailstones |> |> axis_congruence()

    x + y + z

  defp axis_congruence(axis_hailstones) do
    |> Stream.flat_map(fn rock_velocity ->
      |> Enum.reject(&(Snap.velocity(&1) == rock_velocity))
      |> |> Snap.position() |> - rock_velocity)))
      |> Enum.reduce([], fn congruence, coprimes ->
        if Enum.all?(coprimes, &(&1 |> Cong.m() |> Integer.gcd(Cong.m(congruence)) == 1)) do
          [congruence | coprimes]
      |> :crt.chinese_remainder()
      |> case do
        :undefined ->

        when rock_position < -@position_boundary or rock_position > @position_boundary ->

        rock_position ->
          if Enum.all?(
               &will_collide?(&1,, rock_velocity))
             ) do

  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} ->

      {_, 0} ->

      {delta_position, delta_velocity} ->
        time = delta_position / delta_velocity
        time > 0 and time == round(time)

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 !


I gave up on trying to solve part 2 by myself and looked for hints on reddit. Here is my solution:

1 Like

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