Advent of Code 2020: Day 11

aoc_2020_day_11.exs

defmodule AOC2020.Day11 do
  def parse(input) do
    String.split(input, "\n", trim: true)
    |> Enum.map(&String.codepoints(&1))
  end

  def show(room) do
    Enum.map(room, &IO.puts(Enum.join(&1)))
    room
  end

  def count_occupied(room) do
    Enum.map(room, fn row -> Enum.count(row, &(&1 == "#")) end)
    |> Enum.sum()
  end

  def sample_input do
    """
    L.LL.LL.LL
    LLLLLLL.LL
    L.L.L..L..
    LLLL.LL.LL
    L.LL.LL.LL
    L.LLLLL.LL
    ..L.L.....
    LLLLLLLLLL
    L.LLLLLL.L
    L.LLLLL.LL
    """
  end

  defmodule PartOne do
    alias AOC2020.Day11

    defp new_seat_state(adj_seats, cur) do
      count = Enum.count(adj_seats, fn v -> v == "#" end)

      cond do
        count == 0 && cur == "L" -> "#"
        count >= 4 && cur == "#" -> "L"
        true -> cur
      end
    end

    defp do_traverse_row(
           [t_left, t],
           [c_left, c],
           [b_left, b]
         ) do
      [new_seat_state([t_left, t, c_left, b_left, b], c)]
    end

    defp do_traverse_row(
           [t_left | [t, t_right | _] = top],
           [c_left | [c, c_right | _] = cur],
           [b_left | [b, b_right | _] = bottom]
         ) do
      seat = new_seat_state([t_left, t, t_right, c_left, c_right, b_left, b, b_right], c)
      [seat | do_traverse_row(top, cur, bottom)]
    end

    defp traverse_row(
           [t, t_right | _] = top,
           [c, c_right | _] = cur,
           [b, b_right | _] = bottom
         ) do
      seat = new_seat_state([t, t_right, c_right, b, b_right], c)
      [seat | do_traverse_row(top, cur, bottom)]
    end

    defp do_traverse_room([top, cur]) do
      bottom = Enum.map(cur, fn _ -> "." end)
      row = traverse_row(top, cur, bottom)
      [row]
    end

    defp do_traverse_room([top, cur, bottom | rest]) do
      row = traverse_row(top, cur, bottom)
      [row | do_traverse_room([cur, bottom | rest])]
    end

    defp traverse_room([cur, bottom | _] = room) do
      top = Enum.map(cur, fn _ -> "." end)
      row = traverse_row(top, cur, bottom)
      [row | do_traverse_room(room)]
    end

    defp do_run(room) do
      new_room = traverse_room(room)

      if new_room == room do
        new_room
      else
        do_run(new_room)
      end
    end

    def run(input) do
      Day11.parse(input)
      |> do_run()
      |> Day11.count_occupied()
    end
  end

  # part 2

  defmodule PartTwo do
    alias AOC2020.Day11

    defp invert(m), do: Enum.reduce(m, [], &[Enum.reverse(&1) | &2])

    defp merge_row([], []), do: []

    defp merge_row([a | adj_rest], [b | i_adj_rest]) do
      [
        Map.merge(a, %{
          right: b[:left],
          bottom_right: b[:top_left],
          bottom: b[:top],
          bottom_left: b[:top_right]
        })
        | merge_row(adj_rest, i_adj_rest)
      ]
    end

    defp merge([], []), do: []

    defp merge([adj_row | adj], [i_adj_row | i_adj]) do
      [merge_row(adj_row, i_adj_row) | merge(adj, i_adj)]
    end

    defp do_row_cache([t_left, t], [c_left, c]) do
      seat_cache =
        case c do
          "." -> %{top_left: t_left.top_left, top: t.top, top_right: ".", left: c_left.left}
          "#" -> %{top_left: "#", top: "#", top_right: "#", left: "#"}
          "L" -> %{top_left: "L", top: "L", top_right: "L", left: "L"}
        end

      [seat_cache]
    end

    defp do_row_cache(
           [t_left | [t, t_right | _] = top],
           [c_left | [c | rest]]
         ) do
      seat_cache =
        case c do
          "." ->
            %{
              top_left: t_left.top_left,
              top: t.top,
              top_right: t_right.top_right,
              left: c_left.left
            }

          "#" ->
            %{top_left: "#", top: "#", top_right: "#", left: "#"}

          "L" ->
            %{top_left: "L", top: "L", top_right: "L", left: "L"}
        end

      [seat_cache | do_row_cache(top, [seat_cache | rest])]
    end

    defp row_cache([t, t_right | _] = top, [c | cur]) do
      seat_cache =
        case c do
          "." -> %{top_left: ".", top: t.top, top_right: t_right.top_right, left: "."}
          "#" -> %{top_left: "#", top: "#", top_right: "#", left: "#"}
          "L" -> %{top_left: "L", top: "L", top_right: "L", left: "L"}
        end

      [seat_cache | do_row_cache(top, [seat_cache | cur])]
    end

    defp adj_cache(top, [cur]), do: [row_cache(top, cur)]

    defp adj_cache(top, [cur, bottom | rest]) do
      new_cur = row_cache(top, cur)
      [new_cur | adj_cache(new_cur, [bottom | rest])]
    end

    defp create_adj_cache([cur, bottom | rest]) do
      top = Enum.map(cur, fn _ -> %{top_left: ".", top: ".", top_right: "."} end)
      new_cur = row_cache(top, cur)
      [new_cur | adj_cache(new_cur, [bottom | rest])]
    end

    defp new_seat_state(adj_seats, cur) do
      count = Enum.count(adj_seats, fn v -> v == "#" end)

      cond do
        count == 0 && cur == "L" -> "#"
        count >= 5 && cur == "#" -> "L"
        true -> cur
      end
    end

    defp do_traverse_row(
           [c],
           [t_left | [t | _]],
           [c_left | [_ | _]],
           [b_left | [b | _]]
         ) do
      seat =
        new_seat_state(
          [
            t_left[:top_left],
            t[:top],
            b[:bottom],
            b_left[:bottom_left],
            c_left[:left]
          ],
          c
        )

      [seat]
    end

    defp do_traverse_row(
           [c | row],
           [t_left | [t, t_right | _] = top],
           [c_left | [_, c_right | _] = cur],
           [b_left | [b, b_right | _] = bottom]
         ) do
      seat =
        new_seat_state(
          [
            t_left[:top_left],
            t[:top],
            t_right[:top_right],
            c_right[:right],
            b_right[:bottom_right],
            b[:bottom],
            b_left[:bottom_left],
            c_left[:left]
          ],
          c
        )

      [seat | do_traverse_row(row, top, cur, bottom)]
    end

    defp traverse_row(
           [c | row],
           [t, t_right | _] = top,
           [_, c_right | _] = cur,
           [b, b_right | _] = bottom
         ) do
      seat =
        new_seat_state(
          [
            t[:top],
            t_right[:top_right],
            c_right[:right],
            b[:bottom],
            b_right[:bottom_right]
          ],
          c
        )

      [seat | do_traverse_row(row, top, cur, bottom)]
    end

    defp do_traverse_room([cur], [near_prev, near_cur]) do
      near_next = Enum.map(cur, fn _ -> %{bottom_right: ".", bottom: ".", bottom_left: "."} end)
      [traverse_row(cur, near_prev, near_cur, near_next)]
    end

    defp do_traverse_room([cur | room], [near_prev, near_cur, near_next | rest]) do
      new_row = traverse_row(cur, near_prev, near_cur, near_next)
      [new_row | do_traverse_room(room, [near_cur, near_next | rest])]
    end

    defp traverse_room([cur | room], [near_cur, near_next | _] = near) do
      near_prev = Enum.map(cur, fn _ -> %{top_left: ".", top: ".", top_right: "."} end)
      new_row = traverse_row(cur, near_prev, near_cur, near_next)
      [new_row | do_traverse_room(room, near)]
    end

    defp compute_new_room_state(room) do
      adj = create_adj_cache(room)
      i_adj = create_adj_cache(invert(room))
      adj = merge(adj, invert(i_adj))

      traverse_room(room, adj)
    end

    defp do_run(room) do
      new_room = compute_new_room_state(room)

      if new_room == room do
        new_room
      else
        do_run(new_room)
      end
    end

    def run(input) do
      Day11.parse(input)
      |> do_run()
      |> Day11.count_occupied()
    end
  end
end