Advent of Code 2021 Day 23 in Elixir - Amphipod 풀이

문제 보기

일정 규칙에 따라 방을 바꿔, 최소한의 비용으로 모든 사람들이 각자의 방에 들어가 있도록 만드는 방법(그리고 그 때의 비용)을 찾는 문제였다. 약간 하노이의 탑이 떠오르기도 했다. 첫 번째 문제는 각 방에 2명씩만 들어가는 경우, 두 번째 문제는 각 방에 4명씩 들어가는 경우였다.
첫 번째 문제는 그냥 휴리스틱으로 풀리더라. 방 밖의 여유공간이 생각보다 넉넉해서 어떻게 풀어도 잘 풀렸다. 다만 두 번째 문제는 휴리스틱이 잘 안 통해서, 코드를 동원하기로 했다. 이른바 '완전탐색'이라고도 하는, 모든 가능성을 확인한 뒤 불가능한 경우를 가지치기해가며 최종 답을 찾아가는 식으로 구현했다. (패턴 매칭의 덕을 많이 본 코드인데, 이런 식으로 쓰라고 패턴 매칭이 있는 것은 아닐 것 같기는 하다. 함수 하나 구현이 200줄짜리...) 일정 수준까지 경우의 수가 늘어나다가, 어느 정도 게임이 진행되면 답을 얻을 수 있는지 여부가 결정되는 경우가 많아 그때부터는 경우의 수가 확 줄어들어 어렵지 않게 찾을 수 있었다.
다만 문제 1에 대해서 같은 코드를 실행하면 오히려 문제 2보다도 더 오래 걸리는 것을 확인할 수 있었는데, 오히려 움직임이 더 자유로워 선택지가 늘어난 탓이 아닌가 하고 예상해 본다. 또, 이 코드에서는 복도 양 옆의 대기 장소를 무조건 맨 안쪽부터 채우도록 하고 있다. 문제 2에서는 모든 대기 공간을 최대한 활용하는 덕에 문제가 없었지만, 문제 1에서는 그런 일이 없어 작은 오차들이 생기는 이슈가 있다. 문제 1을 조금 더 잘 풀려면 이리저리 코드를 좀 고쳐봐야 할 것 같다.

defmodule Day23 do
  defstruct [:h_l, :h_ab, :h_bc, :h_cd, :h_r, :r_a, :r_b, :r_c, :r_d, :moves]

  @init %{
    h_l: [],
    h_ab: nil,
    h_bc: nil,
    h_cd: nil,
    h_r: [],
    r_a: ["C", "B"],
    r_b: ["D", "A"],
    r_c: ["D", "B"],
    r_d: ["A", "C"],
    moves: []
  }
  @room_depth Map.get(@init, :r_a) |> length()
  @room_pos %{
    h_l: 0,
    r_a: 0,
    h_ab: 1,
    r_b: 2,
    h_bc: 3,
    r_c: 4,
    h_cd: 5,
    r_d: 6,
    h_r: 6
  }
  @energy_by_t %{
    "A" => 1,
    "B" => 10,
    "C" => 100,
    "D" => 1000
  }

  @type t :: %Day23{
          h_l: list(String.t()),
          h_ab: nil | String.t(),
          h_bc: nil | String.t(),
          h_cd: nil | String.t(),
          h_r: list(String.t()),
          r_a: list(String.t()),
          r_b: list(String.t()),
          r_c: list(String.t()),
          r_d: list(String.t()),
          moves: []
        }

  def run_q1() do
    do_run_q1([struct(Day23, @init)], 0)

    nil
  end

  defp complete?(map) do
    r_a = Map.get(map, :r_a)
    r_b = Map.get(map, :r_b)
    r_c = Map.get(map, :r_c)
    r_d = Map.get(map, :r_d)

    length(r_a) == @room_depth and Enum.all?(r_a, fn v -> v == "A" end) and
      length(r_b) == @room_depth and Enum.all?(r_b, fn v -> v == "B" end) and
      length(r_c) == @room_depth and Enum.all?(r_c, fn v -> v == "C" end) and
      length(r_d) == @room_depth and Enum.all?(r_d, fn v -> v == "D" end)
  end

  defp calc_energy(complete) do
    complete
    |> Map.get(:moves)
    |> Enum.reverse()
    |> Enum.reduce({struct(Day23, @init), 0}, fn {f, d}, {map, acc_energy} ->
      t =
        Map.get(map, f)
        |> then(fn
          l when is_list(l) -> List.first(l)
          v -> v
        end)

      new_map = move(f, d, map, t)

      room_depth_f =
        case f do
          value when value in [:r_a, :r_b, :r_c, :r_d] ->
            @room_depth - length(Map.get(map, f)) + 1

          value when value in [:h_l, :h_r] ->
            2 - length(Map.get(map, f)) + 1

          _ ->
            0
        end

      room_depth_d =
        case d do
          value when value in [:r_a, :r_b, :r_c, :r_d] ->
            @room_depth - length(Map.get(map, d))

          value when value in [:h_l, :h_r] ->
            2 - length(Map.get(map, d))

          _ ->
            0
        end

      dist =
        abs(@room_pos[f] - @room_pos[d])
        |> Kernel.+(room_depth_f)
        |> Kernel.+(room_depth_d)

      {new_map, acc_energy + dist * @energy_by_t[t]}
    end)
    |> elem(1)
  end

  @spec do_run_q1([%Day23{}], integer()) :: [%Day23{}]
  defp do_run_q1([], _depth) do
    IO.puts("ended")
    []
  end

  defp do_run_q1(map_candidates, depth) do
    possible_positions = %Day23{} |> Map.keys() |> List.delete(:__struct__) |> List.delete(:moves)

    completes =
      map_candidates
      |> Enum.filter(&complete?/1)

    if completes != [] do
      IO.inspect(length(completes), label: "completed size")

      completes
      |> Enum.map(&calc_energy/1)
      |> Enum.min()
      |> IO.inspect()
    else
      map_candidates
      |> Enum.reject(&complete?/1)
      |> Enum.flat_map(fn map ->
        map
        |> Map.from_struct()
        |> Map.drop([:moves])
        |> Enum.map(fn
          {k, l} when is_list(l) ->
            if (k == :r_a and Enum.any?(l, &(&1 != "A"))) or
                 (k == :r_b and Enum.any?(l, &(&1 != "B"))) or
                 (k == :r_c and Enum.any?(l, &(&1 != "C"))) or
                 (k == :r_d and Enum.any?(l, &(&1 != "D"))) or
                 k in [:h_l, :h_r] do
              {k, l |> List.first()}
            else
              {k, nil}
            end

          {k, v} ->
            {k, v}
        end)
        |> Enum.reject(&(&1 |> elem(1) |> is_nil()))
        |> Enum.flat_map(fn {current_position, type} ->
          # 특정 하나의 개체가 이동 가능한 모든 경우 계산
          possible_positions
          |> Enum.map(fn p -> move(current_position, p, map, type) end)
          |> Enum.filter(fn v -> v != false end)
          |> then(fn candidates ->
            # r_a, r_b, r_c, r_d 로 향할 수 있는 경우가 존재하면 해당 경우를 우선해서 취함
            Enum.filter(candidates, fn candidate ->
              (Map.get(candidate, :moves) |> hd() |> elem(1)) in [:r_a, :r_b, :r_c, :r_d]
            end)
            |> then(fn
              [] -> candidates
              filtered_candidates -> filtered_candidates
            end)
          end)

          # |> IO.inspect(label: "#{current_position}, #{type}")
        end)
      end)
      |> tap(fn maps -> IO.puts("step #{depth} ended: #{length(maps)}") end)
      |> do_run_q1(depth + 1)
    end
  end

  # From hall_left
  @spec move(atom(), atom(), Day23.t(), String.t()) :: Day23.t()
  def move(:h_l = f, :r_a = d, %Day23{r_a: r} = map, "A" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:h_l = f, :r_b = d, %Day23{h_ab: nil, r_b: r} = map, "B" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:h_l = f, :r_c = d, %Day23{h_ab: nil, h_bc: nil, r_c: r} = map, "C" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:h_l = f, :r_d = d, %Day23{h_ab: nil, h_bc: nil, h_cd: nil, r_d: r} = map, "D" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  # From hall_ab
  def move(:h_ab = f, :r_a = d, %Day23{r_a: r} = map, "A" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_ab = f, :r_b = d, %Day23{r_b: r} = map, "B" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_ab = f, :r_c = d, %Day23{h_bc: nil, r_c: r} = map, "C" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_ab = f, :r_d = d, %Day23{h_bc: nil, h_cd: nil, r_d: r} = map, "D" = t),
    do: move_hall_to_room(f, d, map, r, t)

  # From hall_bc
  def move(:h_bc = f, :r_a = d, %Day23{h_ab: nil, r_a: r} = map, "A" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_bc = f, :r_b = d, %Day23{r_b: r} = map, "B" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_bc = f, :r_c = d, %Day23{r_c: r} = map, "C" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_bc = f, :r_d = d, %Day23{h_cd: nil, r_d: r} = map, "D" = t),
    do: move_hall_to_room(f, d, map, r, t)

  # From hall_cd
  def move(:h_cd = f, :r_a = d, %Day23{h_ab: nil, h_bc: nil, r_a: r} = map, "A" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_cd = f, :r_b = d, %Day23{h_bc: nil, r_b: r} = map, "B" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_cd = f, :r_c = d, %Day23{r_c: r} = map, "C" = t),
    do: move_hall_to_room(f, d, map, r, t)

  def move(:h_cd = f, :r_d = d, %Day23{r_d: r} = map, "D" = t),
    do: move_hall_to_room(f, d, map, r, t)

  # From hall_right
  def move(:h_r = f, :r_a = d, %Day23{h_ab: nil, h_bc: nil, h_cd: nil, r_a: r} = map, "A" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:h_r = f, :r_b = d, %Day23{h_bc: nil, h_cd: nil, r_b: r} = map, "B" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:h_r = f, :r_c = d, %Day23{h_cd: nil, r_c: r} = map, "C" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:h_r = f, :r_d = d, %Day23{r_d: r} = map, "D" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  # From room_a
  def move(:r_a = f, :h_l = d, %Day23{h_l: h} = map, t), do: move_room_to_lr(f, d, map, h, t)

  def move(:r_a = f, :h_ab = d, %Day23{h_ab: nil} = map, t), do: move_room_to_hall(f, d, map, t)

  def move(:r_a = f, :h_bc = d, %Day23{h_ab: nil, h_bc: nil} = map, t),
    do: move_room_to_hall(f, d, map, t)

  def move(:r_a = f, :h_cd = d, %Day23{h_ab: nil, h_bc: nil, h_cd: nil} = map, t),
    do: move_room_to_hall(f, d, map, t)

  def move(:r_a = f, :h_r = d, %Day23{h_ab: nil, h_bc: nil, h_cd: nil, h_r: h} = map, t),
    do: move_room_to_lr(f, d, map, h, t)

  def move(:r_a = f, :r_b = d, %Day23{h_ab: nil, r_b: r} = map, "B" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_a = f, :r_c = d, %Day23{h_ab: nil, h_bc: nil, r_c: r} = map, "C" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_a = f, :r_d = d, %Day23{h_ab: nil, h_bc: nil, h_cd: nil, r_d: r} = map, "D" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  # From room_b
  def move(:r_b = f, :h_l = d, %Day23{h_l: h, h_ab: nil} = map, t),
    do: move_room_to_lr(f, d, map, h, t)

  def move(:r_b = f, :h_ab = d, %Day23{h_ab: nil} = map, t), do: move_room_to_hall(f, d, map, t)

  def move(:r_b = f, :h_bc = d, %Day23{h_bc: nil} = map, t), do: move_room_to_hall(f, d, map, t)

  def move(:r_b = f, :h_cd = d, %Day23{h_bc: nil, h_cd: nil} = map, t),
    do: move_room_to_hall(f, d, map, t)

  def move(:r_b = f, :h_r = d, %Day23{h_bc: nil, h_cd: nil, h_r: h} = map, t),
    do: move_room_to_lr(f, d, map, h, t)

  def move(:r_b = f, :r_a = d, %Day23{h_ab: nil, r_a: r} = map, "A" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_b = f, :r_c = d, %Day23{h_bc: nil, r_c: r} = map, "C" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_b = f, :r_d = d, %Day23{h_bc: nil, h_cd: nil, r_d: r} = map, "D" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  # From room_c
  def move(:r_c = f, :h_l = d, %Day23{h_l: h, h_ab: nil, h_bc: nil} = map, t),
    do: move_room_to_lr(f, d, map, h, t)

  def move(:r_c = f, :h_ab = d, %Day23{h_ab: nil, h_bc: nil} = map, t),
    do: move_room_to_hall(f, d, map, t)

  def move(:r_c = f, :h_bc = d, %Day23{h_bc: nil} = map, t), do: move_room_to_hall(f, d, map, t)

  def move(:r_c = f, :h_cd = d, %Day23{h_cd: nil} = map, t), do: move_room_to_hall(f, d, map, t)

  def move(:r_c = f, :h_r = d, %Day23{h_cd: nil, h_r: h} = map, t),
    do: move_room_to_lr(f, d, map, h, t)

  def move(:r_c = f, :r_a = d, %Day23{h_ab: nil, h_bc: nil, r_a: r} = map, "A" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_c = f, :r_b = d, %Day23{h_bc: nil, r_b: r} = map, "B" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_c = f, :r_d = d, %Day23{h_cd: nil, r_d: r} = map, "D" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  # From room_d
  def move(:r_d = f, :h_l = d, %Day23{h_l: h, h_ab: nil, h_bc: nil, h_cd: nil} = map, t),
    do: move_room_to_lr(f, d, map, h, t)

  def move(:r_d = f, :h_ab = d, %Day23{h_ab: nil, h_bc: nil, h_cd: nil} = map, t),
    do: move_room_to_hall(f, d, map, t)

  def move(:r_d = f, :h_bc = d, %Day23{h_bc: nil, h_cd: nil} = map, t),
    do: move_room_to_hall(f, d, map, t)

  def move(:r_d = f, :h_cd = d, %Day23{h_cd: nil} = map, t), do: move_room_to_hall(f, d, map, t)

  def move(:r_d = f, :h_r = d, %Day23{h_cd: nil, h_r: h} = map, t),
    do: move_room_to_lr(f, d, map, h, t)

  def move(:r_d = f, :r_a = d, %Day23{h_ab: nil, h_bc: nil, h_cd: nil, r_a: r} = map, "A" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_d = f, :r_b = d, %Day23{h_bc: nil, h_cd: nil, r_b: r} = map, "B" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(:r_d = f, :r_c = d, %Day23{h_cd: nil, r_c: r} = map, "C" = t),
    do: move_lr_or_room_to_room(f, d, map, r, t)

  def move(_, _, _map, _type) do
    # IO.puts("error!")
    false
  end

  defp move_lr_or_room_to_room(f, d, map, r, t) do
    if only?(r, t),
      do:
        map
        |> Map.update!(f, &Enum.drop(&1, 1))
        |> Map.update!(d, &[t | &1])
        |> Map.update!(:moves, &[{f, d} | &1]),
      else: false
  end

  defp move_hall_to_room(f, d, map, r, t) do
    if only?(r, t),
      do:
        map |> Map.put(f, nil) |> Map.update!(d, &[t | &1]) |> Map.update!(:moves, &[{f, d} | &1]),
      else: false
  end

  defp move_room_to_lr(f, d, map, h, t) do
    if length(h) < 2,
      do:
        map
        |> Map.update!(f, &Enum.drop(&1, 1))
        |> Map.update!(d, &[t | &1])
        |> Map.update!(:moves, &[{f, d} | &1]),
      else: false
  end

  defp move_room_to_hall(f, d, map, t) do
    map
    |> Map.update!(f, &Enum.drop(&1, 1))
    |> Map.put(d, t)
    |> Map.update!(:moves, &[{f, d} | &1])
  end

  @spec only?(list(), String.t()) :: boolean()
  defp only?(room, type), do: Enum.all?(room, &(&1 == type))
end