Advent of Code 2022 Day 16 in Elixir - Proboscidea Volcanium 풀이

문제 보기

센서가 가리키는 길로 가다 보니 어느새 화산 지하의 동굴에 도착한 일행. 분출이 얼마 남지 않아, 주어진 시간(30분)동안 동굴을 돌아다니며 밸브를 열어 최대한 압력을 줄여야 한단다. 각 밸브가 줄일 수 있는 압력의 양과 지도가 주어졌을 때, 줄일 수 있는 최대 압력은 얼마인지 묻는 문제였다.

2번째 문제는 조금 더 복잡해서, 동료 코끼리에게 4분동안 밸브 여는 방법을 가르쳐준 후 26분 동안 둘이 각자 밸브를 열러 다닐 때 줄일 수 있는 최대 압력을 묻는 문제였다.

아무 생각 없이 접근한 결과 그래프 DFS와 비슷한 꼴로 문제를 풀게 되어 연산 시간이 제법 오래 걸렸던 문제로 기억한다. 덕분에 정답임을 확인하자마자 지쳐서 코드 정리고 뭐고 그냥 에디터를 닫아버렸던(...) 그런 문제. 25일차까지 문제를 풀고 난 지금 이 문제를 다시 풀게 되면 중복된 경우의 수를 줄이는 쪽으로 조금 더 잘 짤 수 있지 않을까 싶다.

자잘하지만, 사람과 코끼리의 행동을 Action 구조체로 만들어 받아 문제 1과 문제 2를 하나의 로직 함수(코드는 조금 더 정리할 수 있겠지만)로 대응할 수 있었던 부분은 조금 만족스럽다.

defmodule Omicron.Day16 do
  @dir "data/day16/"

  defmodule Action do
    defstruct [:current, :destination, :next_action_min]
  end

  def q1(file_name \\ "q.txt") do
    valve_map = build_valve_map(file_name)
    distance_map = build_distance_map(valve_map)

    move(
      valve_map,
      distance_map,
      30,
      %Action{current: "AA", next_action_min: 30},
      nil,
      0,
      %{}
    )
  end

  def q2(file_name \\ "q.txt") do
    valve_map = build_valve_map(file_name)
    distance_map = build_distance_map(valve_map)

    move(
      valve_map,
      distance_map,
      26,
      %Action{current: "AA", next_action_min: 26},
      %Action{current: "AA", next_action_min: 26},
      0,
      %{}
    )
  end

  defp build_valve_map(file_name) do
    File.read!(@dir <> file_name)
    |> String.split("\n", trim: true)
    |> Map.new(fn line ->
      [_, valve_name, rate, _, lead_to] =
        Regex.run(
          ~r/^Valve ([A-Z]+) has flow rate=([0-9]+); (tunnels lead to valves|tunnel leads to valve) (.*)$/,
          line
        )

      {valve_name, %{rate: String.to_integer(rate), lead_to: lead_to |> String.split(", ")}}
    end)
  end

  defp build_distance_map(valve_map) do
    has_flows =
      valve_map
      |> Map.filter(fn {k, v} -> v.rate > 0 end)
      |> Map.keys()
      |> Kernel.++(["AA"])

    has_flows
    |> Map.new(fn k ->
      {k, Map.new(has_flows, fn d -> {d, get_distance(valve_map, k, d)} end)}
    end)
  end

  defp move(_, _, min_last, _, _, total_flow, _) when min_last <= 0, do: total_flow

  defp move(
         valve_map,
         distance_map,
         min_last,
         human = %Action{current: current, next_action_min: min_last},
         elephant,
         total_flow,
         opened
       ) do
    candidates =
      valve_map
      |> Map.filter(fn {k, v} -> v.rate > 0 and not Map.has_key?(opened, k) end)
      |> Map.map(fn {k, v} ->
        # IO.inspect("#{current} #{k}")

        v
        |> Map.put(:distance, distance_map[current][k])
        |> Map.put(:score, (min_last - distance_map[current][k]) * v.rate)
      end)
      |> Map.filter(fn {_k, v} -> v.score > 0 end)
      |> Enum.sort_by(fn {k, v} -> v.score end, :desc)

    if candidates == [] do
      total_flow
      |> IO.inspect(label: "opened")
    else
      candidates
      |> Enum.filter(fn {k, v} ->
        v.score >= elem(hd(candidates), 1).score / 3
      end)
      |> tap(fn cand ->
        opened
        |> Enum.sort_by(fn {k, v} -> v end, :desc)
        |> IO.inspect(label: "opened")

        cand
        |> Enum.map(fn {k, v} -> {k, Map.take(v, [:distance, :rate, :score])} end)
        |> IO.inspect(label: "#{min_last} minutes last")
      end)
      |> Enum.map(fn {k, v} ->
        move(
          valve_map,
          distance_map,
          min_last,
          human
          |> Map.merge(%{current: k, destination: k, next_action_min: min_last - v.distance}),
          elephant,
          total_flow + v.score,
          Map.put(opened, k, "H#{min_last - v.distance}")
        )
      end)
      |> Enum.max()
    end
  end

  defp move(
         valve_map,
         distance_map,
         min_last,
         human,
         elephant = %Action{current: current, next_action_min: min_last},
         total_flow,
         opened
       ) do
    candidates =
      valve_map
      |> Map.filter(fn {k, v} -> v.rate > 0 and not Map.has_key?(opened, k) end)
      |> Map.map(fn {k, v} ->
        # IO.inspect("#{current} #{k}")

        v
        |> Map.put(:distance, distance_map[current][k])
        |> Map.put(:score, (min_last - distance_map[current][k]) * v.rate)
      end)
      |> Map.filter(fn {_k, v} -> v.score > 0 end)
      |> Enum.sort_by(fn {k, v} -> v.score end, :desc)

    if candidates == [] do
      total_flow
      |> IO.inspect(label: "opened")
    else
      candidates
      |> Enum.filter(fn {k, v} ->
        v.score >= elem(hd(candidates), 1).score / 2
      end)
      |> tap(fn cand ->
        opened
        |> Enum.sort_by(fn {k, v} -> v end, :desc)
        |> IO.inspect(label: "opened")

        cand
        |> Enum.map(fn {k, v} -> {k, Map.take(v, [:distance, :rate, :score])} end)
        |> IO.inspect(label: "#{min_last} minutes last")
      end)
      |> Enum.map(fn {k, v} ->
        move(
          valve_map,
          distance_map,
          min_last,
          human,
          elephant
          |> Map.merge(%{current: k, destination: k, next_action_min: min_last - v.distance}),
          total_flow + v.score,
          Map.put(opened, k, "E#{min_last - v.distance}")
        )
      end)
      |> Enum.max()
    end
  end

  defp move(
         value_map,
         distance_map,
         min_last,
         human,
         elephant,
         total_flow,
         opened
       ) do
    move(
      value_map,
      distance_map,
      min_last - 1,
      human,
      elephant,
      total_flow,
      opened
    )
  end

  defp get_distance(valve_map, from, from), do: 0

  defp get_distance(valve_map, from, dest) do
    do_get_distance(valve_map, [[from]], dest)
  end

  defp do_get_distance(valve_map, pathes, dest) do
    new_pathes =
      pathes
      |> Enum.flat_map(fn path ->
        valve_map[hd(path)].lead_to
        |> Enum.map(fn l ->
          [l | path]
        end)
      end)

    if Enum.any?(new_pathes, fn path -> hd(path) == dest end) do
      hd(new_pathes) |> length()
    else
      do_get_distance(valve_map, new_pathes, dest)
    end
  end
end