Advent of Code 2024 - Day 14

I said I was on a break, but I took a sneak peak and it looked fun so…

Part 1 completes in half a millisecond with a single pass of the robots. Integer.mod/2 to the rescue.

I was expecting part 2 to to be “and now 1 billion seconds??” but that took me by surprise. Not enough time to figure it out but I’m guessing looking for the centre y axis being full of robots will find it.

Part 1 solution:

def part1({robots, size_x, size_y}) do
  mid_x = div(size_x, 2)
  mid_y = div(size_y, 2)

  robots
  |> Enum.reduce({0, 0, 0, 0}, fn [px, py, vx, vy], {a, b, c, d} ->
    x = Integer.mod(px + vx * 100, size_x)
    y = Integer.mod(py + vy * 100, size_y)

    case {x, y} do
      {x, y} when x < mid_x and y < mid_y -> {a + 1, b, c, d}
      {x, y} when x < mid_x and y > mid_y -> {a, b + 1, c, d}
      {x, y} when x > mid_x and y < mid_y -> {a, b, c + 1, d}
      {x, y} when x > mid_x and y > mid_y -> {a, b, c, d + 1}
      {x, y} when x == mid_x or y == mid_y -> {a, b, c, d}
    end
  end)
  |> Tuple.product()
end

This was a fun day.

I initially solved part 2 by printing out a map with the robots after each second. I then did some creative grepping to find the Christmas tree. Knowing what the Christmas tree looks like, I could create a unique pattern to use when searching for the Christmas tree programmatically.

The combined running time for both parts is 2.3 seconds.

3 Likes

Yeah I feel like a lot of people did things short ways (look for all unique positions? Which works somehow?) and I did lots of trial and error browsing output grids to find the tree, and then work backwards to write code to find the tree. If I knew what the tree looked like from the get-go, it would have been a lot simpler!

(that’s what it looks like)

My code: advent_of_code/lib/y2024/day14.ex at main · sevenseacat/advent_of_code · GitHub

Name                     ips        average  deviation         median         99th %
day 14, part 1        516.12        1.94 ms     ±8.66%        1.85 ms        2.30 ms
day 14, part 2          1.41      707.27 ms     ±0.37%      707.76 ms      710.36 ms
1 Like

Can you give an order of magnintude for the seconds?

My part 1 is correct, and I see some kind of horizontal or verical patterns when I print the map but nothing that resembles an actual tree.

Edit alright found it

I printed the grids when any of the grid column had 5 adjacent tiles. It’s less than 10 000 seconds

Yesss work with those patterns, that’s how I did it. Look for the tick numbers (number of seconds elapsed) that cause those patterns. FInd the patterns of the tick numbers. Extrapolate upwards. (It’s not a massive number)

1 Like

With my input, the tree was found within the first 10000 seconds.

1 Like

Thank you guys. I found it by searching contiguous cells and it worked :). I’m not sure if I want to implement the pattern search because you need to know the tree shape already.

Edit: Alright, did it anyway, looking for the tip of the tree is 400ms

 Enum.reduce_while(1..10000, nil, fn sec, _ ->
      positions = Enum.map(robots, &simulate(&1, room_dimensions, sec))
      map = Map.new(positions, &{&1, true})

      if Enum.all?([{43, 57}, {42, 58}, {43, 58}, {44, 58}], &Map.has_key?(map, &1)) do
        {:halt, sec}
      else
        {:cont, nil}
      end
    end)
  end

Also it was very slow because of my modulo function:

  defp mod(0, _), do: 0
  defp mod(n, m) when n < 0, do: mod(m + n, m)
  defp mod(n, m), do: rem(n, m)

Looking at the implementation I can see why :smiley: But today I learnt Integer.mod/2 exists!

Edit2: since the slow thing was the modulo, the map is actually slower. this is around 140ms:

    Enum.reduce_while(1..10000, nil, fn sec, _ ->
      positions = Enum.map(robots, &simulate(&1, room_dimensions, sec))

      if Enum.all?([{43, 57}, {42, 58}, {43, 58}, {44, 58}], & &1 in positions) do
        {:halt, sec}
      else
        {:cont, nil}
      end
    end)

Edit this will not work for any input if not everyone has the tree in the same position. I don’t know if it is the case.

3 Likes

I got the answer to part 2. In my case, I dumped the grid and noticed:

  • The output after 27 seconds looked suspicious
  • It repeated again after 101 seconds

So I just checked every 101 second jump before finding the tree (actually I went past it due to spamming the return key and had to scroll up to get the index :laughing:). Thankfully it wasn’t too far in. I can’t find the motivation to write the code to search for the tree though :crazy_face:

1 Like

With all the fuss about people using AI this year, and the interesting nature of part 2, I thought I’d feed today’s problem into ChatGPT and see what it came up with.

It solved part 1 instantly, and more efficiently than I solved it (no need to loop 100 times to figure out where things are after 100 seconds, multiply the velocity by 100 and calculate once).

It failed on part 2 - it had the interesting idea to look for a bounding box of the robots that was less than a given size, to represent the robots converging together to make a shape, but that doesn’t work because not all of the robots are involved in making the shape. I’m not super skilled at prompting but nothing I’m telling it seems to budge it from that algorithm (despite including some density-calculation functionality), so of course it blows right past the correct answer and loops infinitely.

Super interesting though!

This was the answer to a previous year though, which it has surely been trained on.

That makes sense! And is probably why it doesn’t behave the same way this year :smiley:

Though the code might still work, if the density function was altered a bit…

edit: Yep, removing the bounding box calculation and using just a density calculation works perfectly. This is the code it generated:

It takes just over a second to run on my machine and gives the same answer for my real input, as my code does.

My solution. I solved Part 2 manually by printing each second’s grid, too. For part 1 I was also inspired by the solutions already posted in this thread.

I did solve part 1 with simple modulo operations like most of us.

Concerning part 2, I did render the “animation” (at x4 speed) in my console.
2 patterns appeared for the first time in the first 100 frames and then reappeared regularly respectively every 101 and 103 frames.
With the guess that the Christmas tree appears when both patterns are applied to the same frame, the chinese remainder theorem gave me the solution.

2 Likes

Oh my, I am not proud of my Part 2. My is_a_christmas_tree?/1 function is the absolute worst. It took 272 seconds to get to the answer.

But, lots of decorating to do today, moving on.

paste

I had an annoying bug with my home made mod function that meant part1 took longer than it should. Nice to learn about Integer.mod. Do you think it would be good to add a note about the existance of Integer.mod to the documentation for rem()?

For part 2 I tried various huristics until I decided to reuse the regions finding function from day 12. That worked fine but was lucky as they could have easily drawn a tree without touching. I was very close to realising I could have looked for seconds where they are in unique positons (although again that is just a heuristic I guess).

1 Like

Finding minimal variance of positions worked for me in part 2. For each second in range 0..(101 * 103) I’ve calculated variance of robots’ positions:

  defp variance(positions) do
    {xs, ys} = Enum.unzip(positions)
    xl = length(xs)
    yl = length(ys)
    xmean = Enum.sum(xs) / xl
    ymean = Enum.sum(ys) / yl
    xvar = Enum.sum(Enum.map(xs, fn x -> (x - xmean) ** 2 end)) / xl
    yvar = Enum.sum(Enum.map(ys, fn y -> (y - ymean) ** 2 end)) / yl
    (xvar + yvar) / 2
  end

The second with minimal variance was the solution.

5 Likes

Went for a semi, brute force method here. Generated .txt files of the first 200 options, spotted that there was a sequence of when the robots seemed to come together, so then decided to try searching for a block of xxxx in the txt representation of the grid, and I was lucky!

Should really tidy it up to not be converting to a string every time for speed, but it works and I’m short on time today!

defmodule Aoc2024.Solutions.Y24.Day14 do
  alias AoC.Input

  def parse(input, _part) do
    Input.read!(input)
    |> String.split("\n", trim: true)
    |> Enum.map(fn robot ->
      [rob, speed] = String.split(robot, " ", trim: true)
      {get_x_y(rob), get_x_y(speed)}
    end)
  end

  def get_x_y(loc) do
    [x, y] = String.split(loc, ",", trim: true)
    x = String.split(x, "=", trim: true) |> List.last() |> String.to_integer()
    y = String.to_integer(y)
    {x, y}
  end

  def part_one(problem) do
    grid_x = 100
    grid_y = 102
    middle_x = 50
    middle_y = 51

    {a, b, c, d} =
      problem
      |> perform_moves({grid_x, grid_y}, 100, 0)
      # |> Enum.map(&perform_moves(&1, {grid_x, grid_y}, 100, 0))
      |> Enum.reduce({0, 0, 0, 0}, fn robot, acc ->
        acc = find_quadrant(robot, acc, {middle_x, middle_y})
        acc
      end)

    a * b * c * d
  end

  def part_two(problem) do
    grid_x = 100
    grid_y = 102

    problem
    |> perform_moves_pt_2({grid_x, grid_y}, 8000, 0)
  end

  def find_quadrant(
        {{loc_x, loc_y}, _},
        {quad_1, quad_2, quad_3, quad_4} = acc,
        {middle_x, middle_y}
      ) do
    cond do
      loc_x < middle_x && loc_y < middle_y ->
        {quad_1 + 1, quad_2, quad_3, quad_4}

      loc_x > middle_x && loc_y < middle_y ->
        {quad_1, quad_2 + 1, quad_3, quad_4}

      loc_x < middle_x && loc_y > middle_y ->
        {quad_1, quad_2, quad_3 + 1, quad_4}

      loc_x > middle_x && loc_y > middle_y ->
        {quad_1, quad_2, quad_3, quad_4 + 1}

      true ->
        acc
    end
  end

  def perform_moves(robots, {_grid_x, _grid_y}, count, acc) when acc == count, do: robots

  def perform_moves(robots, {grid_x, grid_y}, count, acc) do
    robots =
      Enum.map(robots, fn robot ->
        perform_move(robot, {grid_x, grid_y})
      end)

    perform_moves(robots, {grid_x, grid_y}, count, acc + 1)
  end

  def perform_moves_pt_2(robots, {_grid_x, _grid_y}, count, acc) when acc == count, do: robots

  @first_1 59
  @diff_1 103
  @tick_1 Enum.map(1..100, fn n -> @first_1 + (n - 1) * @diff_1 end)
  @first_2 82
  @diff_2 101
  @tick_2 Enum.map(1..100, fn n -> @first_2 + (n - 1) * @diff_2 end)
  @ticks @tick_1 ++ @tick_2

  def perform_moves_pt_2(robots, {grid_x, grid_y}, count, acc) do
    robots =
      Enum.map(robots, fn robot ->
        perform_move(robot, {grid_x, grid_y})
      end)

    if acc in @ticks do
      if check_for_tree(robots) do
        acc
      else
        perform_moves_pt_2(robots, {grid_x, grid_y}, count, acc + 1)
      end
    else
      perform_moves_pt_2(robots, {grid_x, grid_y}, count, acc + 1)
    end
  end

  def check_for_tree(robots) do
    grid = for _ <- 0..102, do: for(_ <- 0..100, do: ".")

    Enum.reduce(robots, grid, fn {{x, y}, _}, acc ->
      List.update_at(acc, y, fn row ->
        List.update_at(row, x, fn _ -> "#" end)
      end)
    end)
    |> Enum.join(" ")
    |> String.contains?("##########")
  end

  def print_coordinates_grid(coordinates, acc) do
    grid = for _ <- 0..102, do: for(_ <- 0..100, do: ".")

    updated_grid =
      Enum.reduce(coordinates, grid, fn {{x, y}, _}, acc ->
        List.update_at(acc, y, fn row ->
          List.update_at(row, x, fn _ -> "#" end)
        end)
      end)

    file =
      Enum.reduce(updated_grid, "", fn row, acc ->
        acc <> Enum.join(row, "") <> "\n"
      end)

    File.write!("output_#{acc}.txt", file)
  end

  def perform_move({{x, y}, {speed_x, speed_y}}, {grid_x, grid_y}) do
    updated_x = calulate_next_position(x, speed_x, grid_x)
    updated_y = calulate_next_position(y, speed_y, grid_y)
    {{updated_x, updated_y}, {speed_x, speed_y}}
  end

  def calulate_next_position(current, speed, grid_size) when current + speed > grid_size do
    current - 1 + speed - grid_size
  end

  def calulate_next_position(current, speed, grid_size) when current + speed < 0 do
    grid_size + 1 + current + speed
  end

  def calulate_next_position(current, speed, _grid_size) do
    current + speed
  end
end

Had to come here to get some idea of what the christmas tree was supposed to look like so I could figure out how to search for it. Once I knew that it was fairly straightforward since I had written function to output a grid layout for debugging for a previous day.

AOC continues to be a great way for me to learn the Elixir standard library. I think I’ve used a new-to-me function every day.

require Grid

defmodule Aoc2024.Day14 do
  @moduledoc false

  def part1(file, size) do
    seconds = 100
    get_input(file)
    |> Enum.map(&move(&1, seconds, size))
    |> Enum.map(&quadrant(&1, size))
    |> Enum.frequencies()
    |> Map.delete(0)
    |> Map.values()
    |> Enum.product()
  end

  def part2(file, size) do
    robots = get_input(file)
    Enum.reduce_while(1..10_000, robots, fn seconds, robots ->
      output = Enum.map(robots, &move(&1, seconds, size))
      |> Enum.frequencies()
      |> Grid.new(size)
      |> Grid.output(" ")
      if Regex.match?(~r/\d{8}/, output) do
        IO.puts("#{seconds} seconds:")
        IO.puts(output)
        {:halt, seconds}
      else
        {:cont, robots}
      end
    end)
  end

  defp get_input(file) do
    File.read!(file)
    |> String.trim()
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      [px, py, vx, vy] =
        Regex.run(~r/p=(?<px>\d+),(?<py>\d+) v=(?<vx>-?\d+),(?<vy>-?\d+)/, line,
          capture: ["px", "py", "vx", "vy"]
        )
        |> Enum.map(&String.to_integer/1)

      {px, py, vx, vy}
    end)
  end

  defp move(_robot = {px, py, vx, vy}, seconds, _size = {sx, sy}) do
    newx = Integer.mod(px + vx * seconds, sx)
    newy = Integer.mod(py + vy * seconds, sy)
    {newx, newy}
  end

  defp quadrant(_robot_position = {px, py}, _size = {sx, sy}) do
    midx = div(sx, 2)
    midy = div(sy, 2)
    cond do
      px == midx or py == midy ->
        0
      px < midx and py < midy ->
        1
      px > midx and py < midy ->
        2
      px < midx and py > midy ->
        3
      px > midx and py > midy ->
        4
    end
  end
end
1 Like

For whatever reason, this is correct for the example, but incorrect for the input. I’m confused as to why. My initial implementation looked a lot like @adamu’s. I’ve since refactored it to be nearly identical, but it still doesn’t pass. ← see my reply. This works with a different regex.

I also noticed that the final output for the example has one robot at position 9,0 instead of 10,0 where my code calculates it. :slightly_frowning_face: Maybe a typo in the example output?

Anyone able to point me in the right direction?

defmodule Day14.Part1 do
  @seconds 100
  @width 101
  @height 103
  @center_column div(@width, 2)
  @center_row div(@height, 2)

  defp parse(str) do
    str
    |> String.split("\n", trim: true)
    |> Enum.map(&parse_bot/1)
  end

  defp parse_bot(line) do
    Regex.scan(~r/-?\d,-?\d/, line)
    |> Enum.flat_map(fn [pair] ->
      [
        String.split(pair, ",")
        |> Enum.map(&String.to_integer/1)
        |> List.to_tuple()
      ]
    end)
  end

  defp iterate(bots) do
    bots
    |> Enum.reduce(
      {0,0,0,0},
      fn [{p_x, p_y}, {v_x, v_y}] = _bot, {q1_bots, q2_bots, q3_bots, q4_bots} = bots ->
        delta_x = v_x * @seconds
        delta_y = v_y * @seconds
        final_x = Integer.mod(p_x + delta_x, @width)
        final_y = Integer.mod(p_y + delta_y, @height)

        case {final_x, final_y} do
          {x, y} when x < @center_column and y < @center_row -> {q1_bots + 1, q2_bots, q3_bots, q4_bots}
          {x, y} when x < @center_column and y > @center_row -> {q1_bots, q2_bots + 1, q3_bots, q4_bots}
          {x, y} when x > @center_column and y < @center_row -> {q1_bots, q2_bots, q3_bots + 1, q4_bots}
          {x, y} when x > @center_column and y > @center_row -> {q1_bots, q2_bots, q3_bots, q4_bots + 1}
          _ -> bots
        end
      end
    )
    |> Tuple.product()
  end

  def solve() do
    File.read!("lib/advent_of_code/year/2024/day/14/input.txt")
    |> parse()
    |> dbg()
    |> iterate()
    |> IO.puts()
  end
end

Woops. Got it.

My regex for parsing was missing + chars after matching each \d :person_facepalming:

Working regex for the above code: ~r/-?\d+,-?\d+/