Advent of Code 2022 Day 19 in Elixir - Not Enough Minerals 풀이

문제 보기

초기 자원이 주어지고, 그 자원을 소비하여 다른 자원을 캘 수 있는 채굴 로봇을 생산할 수 있다고 할 때, 자원을 어떻게 모으고 어떤 로봇을 언제 어떤 순서로 생산해야 주어진 시간 내에 최종 단계 자원을 더 많이 모을 수 있는지를 알아내는 문제였다. 문제 1은 각 로봇 청사진(같은 종류의 채굴 로봇이어도 청사진에 따라 드는 자원이 다르다)마다 주어진 시간 안에 생산할 수 있는 최종 단계 자원의 최대량을 찾는 문제였고, 문제 2는 주어진 로봇 청사진 중 앞 3개에 대해 더 깊은 연산을 요구하는 문제였다. 클리커 게임이나 경영 게임이나... 주로 하는 시뮬레이션류 게임에서 무엇을 어떤 순서로 키울지를 고민하는 것과 비슷해서 개인적으로는 재밌는 소재의 문제였다.

처음에는 알고리즘적으로... 이 자원이 이만큼 쌓이면 이 로봇을 생산하고 하는 식으로 접근했었는데, 하다 보니 더 높은 단계의 로봇을 만들기 위해 한 턴을 일부러 넘기는 경우도 있고 하여 그렇게는 안 되겠더라(물론 좋은 기준을 내가 못 찾은 것일 수도 있다). 하는 수 없이 전체 경우의 수를 찾기로 했다.

지금까지 아무 생각 없이 썼던 일종의 DFS 방식은 일단 한 가지에서 끝을 보지 않으면 다음 계산으로 나아가질 못해서, 중복된 경우를 앞단계에서 잘 걸러내지 못해 시간이 오래 걸리는 경우가 많았다. 이번에는 그렇게는 도저히 풀 수가 없어 매 단계마다 전체 후보 목록을 가져가는 BFS에 가까운 방식을 택했고(각 단계마다 Enum.uniq, 그리고 최종 단계 자원이 적어 무의미한 연산으로 간주되는 경우를 전부 제거), 다행히 잘 맞아들어 비교적 빠른 시간에 풀 수 있었다.

defmodule Omicron.Day19 do
  @dir "data/day19/"

  def q1(file_name \\ "q.txt") do
    blueprints =
      File.read!(@dir <> file_name)
      |> String.split("\n")
      |> Enum.map(fn line ->
        [
          _,
          id,
          ore_cost_ore,
          clay_cost_ore,
          obs_cost_ore,
          obs_cost_clay,
          geode_cost_ore,
          geode_cost_obs
        ] =
          Regex.run(
            ~r/Blueprint ([0-9]+): Each ore robot costs ([0-9]+) ore. Each clay robot costs ([0-9]+) ore. Each obsidian robot costs ([0-9]+) ore and ([0-9]+) clay. Each geode robot costs ([0-9]+) ore and ([0-9]+) obsidian.$/,
            line
          )

        %{
          id: String.to_integer(id),
          ore_cost_ore: String.to_integer(ore_cost_ore),
          clay_cost_ore: String.to_integer(clay_cost_ore),
          obs_cost_ore: String.to_integer(obs_cost_ore),
          obs_cost_clay: String.to_integer(obs_cost_clay),
          geode_cost_ore: String.to_integer(geode_cost_ore),
          geode_cost_obs: String.to_integer(geode_cost_obs)
        }
      end)

    blueprints
    |> Enum.map(fn blueprint ->
      %{
        ore_cost_ore: ore_cost_ore,
        clay_cost_ore: clay_cost_ore,
        obs_cost_clay: obs_cost_clay,
        obs_cost_ore: obs_cost_ore,
        geode_cost_obs: geode_cost_obs,
        geode_cost_ore: geode_cost_ore
      } = blueprint

      1..24
      |> Enum.reduce(
        [
          {%{ore_robot: 1, clay_robot: 0, obs_robot: 0, geode_robot: 0},
           %{ore: 0, clay: 0, obs: 0, geode: 0}}
        ],
        fn i, candidates ->
          max_geode_robot =
            candidates
            |> Enum.max_by(fn {robots, _} -> robots.geode_robot end)
            |> elem(0)
            |> Map.get(:geode_robot)

          max_geode =
            candidates
            |> Enum.max_by(fn {_, resources} -> resources.geode end)
            |> elem(1)
            |> Map.get(:geode)

          candidates
          |> tap(fn _ ->
            # IO.inspect(candidates)
            IO.inspect(length(candidates), label: "Day #{i}")
          end)
          |> Enum.reject(fn {robots, resources} ->
            robots.geode_robot < max_geode_robot / 2 and resources.geode < max_geode / 2
          end)
          |> Enum.flat_map(fn {robots, resources} ->
            ore_action = if resources.ore >= ore_cost_ore, do: [:ore], else: []
            clay_action = if resources.ore >= clay_cost_ore, do: [:clay], else: []

            obs_action =
              if resources.clay >= obs_cost_clay and resources.ore >= obs_cost_ore,
                do: [:obs],
                else: []

            geode_action =
              if resources.obs >= geode_cost_obs and resources.ore >= geode_cost_ore,
                do: [:geode],
                else: []

            actions = [:skip] ++ obs_action ++ geode_action ++ ore_action ++ clay_action

            tmp_resources =
              resources
              |> Map.update!(:ore, &(&1 + robots.ore_robot))
              |> Map.update!(:clay, &(&1 + robots.clay_robot))
              |> Map.update!(:obs, &(&1 + robots.obs_robot))
              |> Map.update!(:geode, &(&1 + robots.geode_robot))

            Enum.map(actions, fn action ->
              case action do
                :skip ->
                  {robots, tmp_resources}

                :ore ->
                  {
                    robots |> Map.update!(:ore_robot, &(&1 + 1)),
                    tmp_resources |> Map.update!(:ore, &(&1 - ore_cost_ore))
                  }

                :clay ->
                  {
                    robots |> Map.update!(:clay_robot, &(&1 + 1)),
                    tmp_resources |> Map.update!(:ore, &(&1 - clay_cost_ore))
                  }

                :obs ->
                  {
                    robots |> Map.update!(:obs_robot, &(&1 + 1)),
                    tmp_resources
                    |> Map.update!(:ore, &(&1 - obs_cost_ore))
                    |> Map.update!(:clay, &(&1 - obs_cost_clay))
                  }

                :geode ->
                  {
                    robots |> Map.update!(:geode_robot, &(&1 + 1)),
                    tmp_resources
                    |> Map.update!(:ore, &(&1 - geode_cost_ore))
                    |> Map.update!(:obs, &(&1 - geode_cost_obs))
                  }
              end
            end)
          end)
          |> Enum.uniq()
        end
      )
      |> Enum.max_by(fn {_robots, resources} -> resources.geode end)
      |> elem(1)
      |> Map.get(:geode)
    end)
    |> Enum.with_index()
    |> Enum.map(fn {v, i} ->
      v * (i + 1)
    end)
    |> Enum.sum()
  end

  def q2(file_name \\ "q.txt") do
    blueprints =
      File.read!(@dir <> file_name)
      |> String.split("\n")
      |> Enum.map(fn line ->
        [
          _,
          id,
          ore_cost_ore,
          clay_cost_ore,
          obs_cost_ore,
          obs_cost_clay,
          geode_cost_ore,
          geode_cost_obs
        ] =
          Regex.run(
            ~r/Blueprint ([0-9]+): Each ore robot costs ([0-9]+) ore. Each clay robot costs ([0-9]+) ore. Each obsidian robot costs ([0-9]+) ore and ([0-9]+) clay. Each geode robot costs ([0-9]+) ore and ([0-9]+) obsidian.$/,
            line
          )

        %{
          id: String.to_integer(id),
          ore_cost_ore: String.to_integer(ore_cost_ore),
          clay_cost_ore: String.to_integer(clay_cost_ore),
          obs_cost_ore: String.to_integer(obs_cost_ore),
          obs_cost_clay: String.to_integer(obs_cost_clay),
          geode_cost_ore: String.to_integer(geode_cost_ore),
          geode_cost_obs: String.to_integer(geode_cost_obs)
        }
      end)

    blueprints
    |> Enum.take(3)
    |> Enum.map(fn blueprint ->
      %{
        ore_cost_ore: ore_cost_ore,
        clay_cost_ore: clay_cost_ore,
        obs_cost_clay: obs_cost_clay,
        obs_cost_ore: obs_cost_ore,
        geode_cost_obs: geode_cost_obs,
        geode_cost_ore: geode_cost_ore
      } = blueprint

      1..32
      |> Enum.reduce(
        [
          {%{ore_robot: 1, clay_robot: 0, obs_robot: 0, geode_robot: 0},
           %{ore: 0, clay: 0, obs: 0, geode: 0}}
        ],
        fn i, candidates ->
          max_geode_robot =
            candidates
            |> Enum.max_by(fn {robots, _} -> robots.geode_robot end)
            |> elem(0)
            |> Map.get(:geode_robot)

          max_geode =
            candidates
            |> Enum.max_by(fn {_, resources} -> resources.geode end)
            |> elem(1)
            |> Map.get(:geode)

          candidates
          |> tap(fn _ ->
            # IO.inspect(candidates)
            IO.inspect(length(candidates), label: "Day #{i}")
          end)
          |> Enum.reject(fn {robots, resources} ->
            robots.geode_robot < max_geode_robot and resources.geode < max_geode
          end)
          |> Enum.flat_map(fn {robots, resources} ->
            ore_action = if resources.ore >= ore_cost_ore, do: [:ore], else: []
            clay_action = if resources.ore >= clay_cost_ore, do: [:clay], else: []

            obs_action =
              if resources.clay >= obs_cost_clay and resources.ore >= obs_cost_ore,
                do: [:obs],
                else: []

            geode_action =
              if resources.obs >= geode_cost_obs and resources.ore >= geode_cost_ore,
                do: [:geode],
                else: []

            actions = [:skip] ++ obs_action ++ geode_action ++ ore_action ++ clay_action

            tmp_resources =
              resources
              |> Map.update!(:ore, &(&1 + robots.ore_robot))
              |> Map.update!(:clay, &(&1 + robots.clay_robot))
              |> Map.update!(:obs, &(&1 + robots.obs_robot))
              |> Map.update!(:geode, &(&1 + robots.geode_robot))

            Enum.map(actions, fn action ->
              case action do
                :skip ->
                  {robots, tmp_resources}

                :ore ->
                  {
                    robots |> Map.update!(:ore_robot, &(&1 + 1)),
                    tmp_resources |> Map.update!(:ore, &(&1 - ore_cost_ore))
                  }

                :clay ->
                  {
                    robots |> Map.update!(:clay_robot, &(&1 + 1)),
                    tmp_resources |> Map.update!(:ore, &(&1 - clay_cost_ore))
                  }

                :obs ->
                  {
                    robots |> Map.update!(:obs_robot, &(&1 + 1)),
                    tmp_resources
                    |> Map.update!(:ore, &(&1 - obs_cost_ore))
                    |> Map.update!(:clay, &(&1 - obs_cost_clay))
                  }

                :geode ->
                  {
                    robots |> Map.update!(:geode_robot, &(&1 + 1)),
                    tmp_resources
                    |> Map.update!(:ore, &(&1 - geode_cost_ore))
                    |> Map.update!(:obs, &(&1 - geode_cost_obs))
                  }
              end
            end)
          end)
          |> Enum.uniq()
        end
      )
      |> Enum.max_by(fn {_robots, resources} -> resources.geode end)
      |> elem(1)
      |> Map.get(:geode)
      |> IO.inspect()
    end)
    |> Enum.product()
  end
end