Advent of Code 2023 - Day 24

exists

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)

3 comments

#advent-of-code #2023

1 964 3

2023-12-28 01:15:18 UTC

Showing Posts 1 to 3

Show Best Posts
Show All (oldest first)
Show All (newest first)

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 !

Post #1

bjorng

Erlang Core Team

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

Post #2

ramuuns

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

Post #3

— All posts loaded —