Advent of Code 2022 Day 21 in Elixir - Monkey Math 풀이

문제 보기

AoC2022 또 하나의 난관. 여러 변수가 있고, 각 변수에 값(자연수)이나 다른 변수 사이의 관계식(이 경우 항상 두 항의 사칙연산)이 주어질 때, 관계식을 풀어 원하는 값을 계산하는 문제였다. 문제 1은 그대로 주어진 관계식을 풀어 최상위의 root 값을 구하는 문제였다. 문제 2는 조건을 조금 바꾸어, root를 이루는 관계식의 두 항이 사칙연산 관계가 아니라 같은 값이어야 할 때, humn(=human=나...)가 어떤 값을 가져야 하는지를 묻는 문제였다. 다시 말해 root를 이루는 관계식의 두 항 중 humn이 포함되지 않은 한 쪽은 지금까지처럼 값을 구할 수 있으니, 다른 한 항의 최상위 값을 알고 있을 때 거꾸로 연산 트리의 하위로 내려가 humn을 구해야 했다.

문제 1은 주어진 관계식을 순서대로 따라가면 될 뿐이라 제법 빨리 풀었는데, 문제 2는 식을 전부 뒤집으면서 동시에 관계식이 연속되도록 해야 해서 제법 애를 먹었다. 이를테면 c = a - b라는 식이 있고 c를 알고 있다면 a = b + c와 b = a - c라는 두 식을 만들 수 있는데 (방금 예에서도 볼 수 있듯 심지어 원래 식의 부호를 덮어놓고 반대로 쓴다고 되는 것도 아니다), 만약 변수 b의 값이 실제로는 숫자라면 첫 번째 식만을 취해야 하는 것이다.

고민 끝에 숫자를 대입할 수 있는 변수는 이른 단계부터 아예 숫자로 바꿔 놓고(처음에는 가급적 변수를 유지하려 했다), 연산을 뒤집으며 숫자가 연산 결과가 되는 식을 제거하는 등등의 방법으로 어찌어찌 해결했다.

defmodule Omicron.Day21 do
  @dir "data/day21/"

  def q1(file_name \\ "q.txt") do
    build_tree(file_name)
    |> fill_number()
    |> Map.get("root")
  end

  defp build_tree(file_name) do
    File.read!(@dir <> file_name)
    |> String.split("\n")
    |> Map.new(fn line ->
      [left, right] = String.split(line, ": ")

      case String.split(right, " ") do
        [one, operator, two] ->
          {left, %{operator: operator, depends_on: [one, two]}}

        [v] ->
          {left, String.to_integer(v)}
      end
    end)
  end

  defp fill_number(tree, _last_tree \\ nil)

  defp fill_number(tree, tree), do: tree

  defp fill_number(tree, _last_tree) do
    tree
    |> Map.map(fn
      {_k, v} when is_number(v) ->
        v

      {_k, %{depends_on: [one, two], operator: op} = map} ->
        val_one =
          cond do
            is_number(one) -> one
            is_number(tree[one]) -> tree[one]
            true -> one
          end

        val_two =
          cond do
            is_number(two) -> two
            is_number(tree[two]) -> tree[two]
            true -> two
          end

        if is_number(val_one) and is_number(val_two) do
          calc_number(val_one, val_two, op)
        else
          %{map | depends_on: [val_one, val_two]}
        end
    end)
    |> fill_number(tree)
  end

  def q2(file_name \\ "q.txt") do
    tree =
      file_name
      |> build_tree()
      |> Map.delete("humn")

    [root_left, root_right] = tree["root"].depends_on

    fixed_tree = tree |> fill_number()

    [root_left_maybe_value, root_right_maybe_value] = fixed_tree["root"].depends_on

    fixed_tree
    |> inverse_lines()
    |> then(fn v ->
      if is_number(root_left_maybe_value) do
        v |> Map.put(root_right, root_left_maybe_value)
      else
        v |> Map.put(root_left, root_right_maybe_value)
      end
    end)
    |> fill_number()
    |> Map.get("humn")
  end

  defp calc_number(a, b, operator) do
    case operator do
      "+" -> a + b
      "-" -> a - b
      "*" -> a * b
      "/" -> a / b
    end
  end

  defp inverse_lines(lines) do
    lines
    |> Enum.flat_map(fn
      {k, %{depends_on: [a, b], operator: op}} ->
        b_map =
          case op do
            "+" -> %{depends_on: [k, a], operator: "-", type: :b}
            "-" -> %{depends_on: [a, k], operator: "-", type: :b}
            "*" -> %{depends_on: [k, a], operator: "/", type: :b}
            "/" -> %{depends_on: [a, k], operator: "/", type: :b}
          end

        [
          {a, %{depends_on: [k, b], operator: inverse_operator(op), type: :a}},
          {b, b_map}
        ]
        |> Enum.reject(fn {k, _} -> is_number(k) end)
        |> Enum.reject(fn {_, %{depends_on: [a, b]}} -> a == "humn" or b == "humn" end)

      entry ->
        [entry]
    end)
    |> Enum.group_by(fn {k, _v} -> k end, fn {_k, v} -> v end)
    |> Map.map(fn {_k, v} ->
      maybe_number = Enum.find(v, &is_number/1)

      if is_nil(maybe_number) do
        hd(v)
      else
        maybe_number
      end
    end)
  end

  defp inverse_operator(op) do
    case op do
      "+" -> "-"
      "-" -> "+"
      "*" -> "/"
      "/" -> "*"
    end
  end
end