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.

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.

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

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.

Haven’t tried part 2 yet, but I’m very pleased that I got part 1 without any false starts and refactors. I do have a suspicion that were I to try and parallelize some of the logic I’d have problems b/c there are some steps where a function takes a value from an ETS table, then either replaces it or leaves it off the table depending on that value. If another process were to attempt to take the value for the same key before that first process finished I think I’d be in trouble. For this problem it was not an issue.

defmodule Day14 do
  alias Day14.{Robot, Board}

  @real File.read!(__DIR__ <> "/input.txt") |> String.trim()

  @re ~r/p=(\d+),(\d+) v=(-*\d+),(-*\d+)/

  def parse(input) do
    Regex.scan(@re, input, capture: :all_but_first)
    |> Enum.map(fn robot -> Enum.map(robot, &String.to_integer/1) end)
  end

  def run(input \\ :real, board_x \\ 101, board_y \\ 103)
  def run(:real, board_x, board_y), do: run(@real, board_x, board_y)

  def run(input, board_x, board_y) do
    Robot.init_roster()
    Board.new(board_x, board_y)

    input
    |> parse()
    |> Robot.init_bots()

    Robot.move_all(100)

    Board.search_quadrants() |> safety_factor() |> IO.inspect(label: :part_1)
  end

  def quit() do
    Board.close()
    Robot.shut_down_all()
  end

  defp safety_factor(groups) do
    groups
    |> Enum.map(fn {k, grp} -> {k, List.flatten(grp)} end)
    |> Enum.map(fn {k, grp} -> {k, grp |> Enum.flat_map(fn {_coord, bots} -> bots end)} end)
    |> Enum.reduce(1, fn {_, bots}, acc -> acc * length(bots) end)
  end

  defmodule Robot do
    def init_roster() do
      :ets.new(:robot_list, [:named_table, :ordered_set])
    end

    def init_bot(name, [px, py, vx, vy]) do
      :ets.insert(:robot_list, {name, %{px: px, py: py, vx: vx, vy: vy}})

      if :board not in :ets.all() do
        Board.new()
      end

      Board.add_to_spot(name, px, py)
    end

    def init_bots(robots) do
      robots
      |> Stream.with_index()
      |> Stream.each(fn {robot, ndx} ->
        name = "R2D#{ndx}"
        init_bot(name, robot)
      end)
      |> Stream.run()
    end

    def shut_down_all() do
      :ets.delete(:robot_list)
    end

    def shut_down_bot(robot) do
      :ets.take(:robot_list, robot)
    end

    def move_all(seconds) do
      Stream.iterate(0, &(&1 + 1))
      |> Stream.map(fn i -> :ets.slot(:robot_list, i) end)
      |> Stream.take_while(fn n -> n != :"$end_of_table" end)
      |> Stream.map(fn [{robot, state}] -> move_bot(robot, state, seconds) end)
      |> Stream.run()
    end

    defp move_bot(robot, state, seconds) do
      board_x = :ets.lookup_element(:board, :width, 2)
      board_y = :ets.lookup_element(:board, :height, 2)

      px =
        case rem(state.px + state.vx * seconds, board_x) do
          n when n >= 0 -> n
          n -> board_x + n
        end

      py =
        case rem(state.py + state.vy * seconds, board_y) do
          n when n >= 0 -> n
          n -> board_y + n
        end

      Board.remove_from_spot(robot, state.px, state.py)
      :ets.update_element(:robot_list, robot, {2, %{state | px: px, py: py}})
      Board.add_to_spot(robot, px, py)
    end
  end

  defmodule Board do
    def new(x \\ 101, y \\ 103) do
      :ets.new(:board, [:named_table, :ordered_set])

      :ets.insert(:board, [{:width, x}, {:height, y}])

      define_quadrants(x, y)
    end

    defp define_quadrants(x, y) do
      mid_x = div(x, 2)
      mid_y = div(y, 2)

      quadrants = [
        {:nw, {0..(mid_x - 1), 0..(mid_y - 1)}},
        {:ne, {(mid_x + 1)..x, 0..(mid_y - 1)}},
        {:sw, {0..(mid_x - 1), (mid_y + 1)..y}},
        {:se, {(mid_x + 1)..x, (mid_y + 1)..y}}
      ]

      :ets.insert(:board, quadrants)
    end

    def remove_from_spot(occupant, x, y) do
      case :ets.take(:board, {x, y}) do
        [{{_x, _y}, [^occupant]}] -> true
        [{{^x, ^y}, occupants}] -> :ets.insert(:board, {{x, y}, occupants -- [occupant]})
        [] -> true
      end
    end

    def add_to_spot(occupant, x, y) do
      case :ets.take(:board, {x, y}) do
        [{{x, y}, occupants}] -> :ets.insert(:board, {{x, y}, [occupant | occupants]})
        [] -> :ets.insert(:board, {{x, y}, [occupant]})
      end
    end

    def search_quadrants() do
      Stream.iterate(0, &(&1 + 1))
      |> Stream.map(fn i -> :ets.slot(:board, i) end)
      |> Stream.take_while(fn res -> res != :"$end_of_table" end)
      |> Stream.filter(fn [{k, _v}] -> k not in [:width, :height, :nw, :sw, :ne, :se] end)
      |> Enum.group_by(fn [{{x, y}, _robots}] -> quadrant(x, y) end)
      |> Enum.reject(fn {k, _grp} -> k == nil end)
    end

    defp quadrant(x, y) do
      [:nw, :ne, :sw, :se]
      |> Enum.find(fn q ->
        case :ets.lookup_element(:board, q, 2) do
          {x1..x2//_, y1..y2//_} when x1 <= x and x2 >= x and (y1 <= y and y2 >= y) -> true
          _ -> false
        end
      end)
    end

    def close() do
      :ets.delete(:board)
    end
  end
end

PS Sorry to everyone who moved on two weeks ago. I finally have some time and enjoy the puzzles more than the competition aspect. Hope no one minds the necro bumps of these threads.

PPS I haven’t checked the thread but did people actually implement edge detection and pattern recognition for finding the undefined christmas tree for part 2? I really think I’m just going to make it print the board every second and watch it until I see a tree.