Advent of Code 2021 Day 24 in Elixir - Arithmetic Logic Unit 풀이

문제 보기

어셈블리 해석기 같은 것을 구현한 뒤, 실행해야 하는 프로그램의 결과를 특정 값(0)으로 만드는 입력의 최대값(문제 1), 최소값(문제 2)을 구하는 문제였다. 사실 구현 자체는 어렵지 않았지만, 문제가 문제가 아니라(?) 프로그램의 동작을 분석하는 것이 더 중요한 문제인 것으로 보였다. 내 경우의 입력은 다음과 같았다. (세로쓰기로, 왼쪽 컬럼부터 오른쪽 컬럼 순으로 읽으면 된다.)

x를 0으로 초기화한 뒤 값을 계산하고, x를 기반으로 y의 값을 얻고, y를 z에 누적해 가는 방식이었다. 내 입력을 점화식으로 나타내면 이렇게 된다.

z_0 = 0
z_k = if(z % 26 + m_k == w_k), do: z_{k-1} / d_k, else: z_{k-1} / d_k * 26 + w_k + a_k (단, 1 <= k <= 14)
아마도 1 <= a_k <= 16, d_k = 1 또는 26

z_14=0으로 만드는 것이 최종 목표인데, m_k >= 10인 경우에는 애초에 w_k와 같아질 수 없어 z에 항상 26이 곱해지므로, m_k < 0, d_k=26인 경우에 w_k와 값을 맞추어 가능한 한 z의 값을 줄여야 했다. 이 과정에서 서로를 상쇄하는 w끼리의 관계식을 만들 수 있었다. 내 경우에는 w_4 = w_5, w_3 + 4 = w_6, w_2 + 8 = w_7, ... 등이었다(이미지의 같은 색끼리 짝). 여기서 큰 쪽을 9가 되게 만들면 최대값이 되고, 작은 쪽을 1이 되게 만들면 최소값이 된다.

앞에서 작성한 해석기는 구한 답을 검증하는 데에만 사용했다(동작을 확인하기 위해 여러 로깅을 추가한 터라 코드가 조금 지저분하나, 일부러 정리하지 않고 올려 둔다). 브루트포스 외에 해석기만 사용해서 이 답을 찾을 수 있을까?

defmodule Day24 do
  def parse_input(file_name) do
    file_name
    |> File.read!()
    |> String.split("\n")
    |> Enum.map(&String.split(&1, " "))
  end

  def run_q1(file_name \\ "input/day24.txt") do
    bindings = %{
      "w" => 0,
      "x" => 0,
      "y" => 0,
      "z" => 0
    }

    records = %{
      "w" => [],
      "x" => [],
      "y" => [],
      "z" => []
    }

    instructions = parse_input(file_name)

    # 11_111_111_111_111..11_111_111_112_311

    # 12자리
    # 111_111_111_111..111_111_111_199
    # |> Enum.map(fn v -> v * 100 + 11 end)

    71_111_591_396_151..71_111_591_396_151
    |> Enum.map(fn model_no ->
      Integer.digits(model_no)
    end)
    |> Enum.reject(fn model_no -> 0 in model_no end)
    |> Enum.each(fn model_no ->
      instructions
      |> Enum.reduce({bindings, records, model_no}, fn
        ["inp", var], {acc_bindings, records, [input | acc_model_no]} ->
          new_bindings = Map.put(acc_bindings, var, input)
          new_records = Map.update!(records, var, &[{:in, var} | &1])

          {new_bindings, new_records, acc_model_no}

        ["add", a, b], {acc_bindings, records, acc_model_no} ->
          new_bindings =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(acc_bindings, a, &(&1 + v))

              :error ->
                Map.update!(acc_bindings, a, &(&1 + Map.get(acc_bindings, b)))
            end

          new_records =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(records, a, &[{:ad, v} | &1])

              :error ->
                Map.update!(records, a, &[{:ad, "#{b}=#{Map.get(acc_bindings, b)}"} | &1])
            end

          {new_bindings, new_records, acc_model_no}

        ["mul", a, "0"], {acc_bindings, records, acc_model_no} ->
          inspect_records(records, label: "#{a}=0")

          new_bindings = Map.put(acc_bindings, a, 0)
          new_records = Map.put(records, a, [])

          {new_bindings, new_records, acc_model_no}

        ["mul", a, b], {acc_bindings, records, acc_model_no} ->
          new_bindings =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(acc_bindings, a, &(&1 * v))

              :error ->
                Map.update!(acc_bindings, a, &(&1 * Map.get(acc_bindings, b)))
            end

          new_records =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(records, a, &[{:mu, v} | &1])

              :error ->
                Map.update!(records, a, &[{:mu, "#{b}=#{Map.get(acc_bindings, b)}"} | &1])
            end

          {new_bindings, new_records, acc_model_no}

        ["div", a, b], {acc_bindings, records, acc_model_no} ->
          new_bindings =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(acc_bindings, a, &div(&1, v))

              :error ->
                Map.update!(acc_bindings, a, &div(&1, Map.get(acc_bindings, b)))
            end

          new_records =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(records, a, &[{:di, v} | &1])

              :error ->
                Map.update!(records, a, &[{:di, "#{b}=#{Map.get(acc_bindings, b)}"} | &1])
            end

          {new_bindings, new_records, acc_model_no}

        ["mod", a, b], {acc_bindings, records, acc_model_no} ->
          new_bindings =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(acc_bindings, a, &rem(&1, v))

              :error ->
                Map.update!(acc_bindings, a, &rem(&1, Map.get(acc_bindings, b)))
            end

          new_records =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(records, a, &[{:mo, v} | &1])

              :error ->
                Map.update!(records, a, &[{:mo, "#{b}=#{Map.get(acc_bindings, b)}"} | &1])
            end

          {new_bindings, new_records, acc_model_no}

        ["eql", a, b], {acc_bindings, records, acc_model_no} ->
          new_bindings =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(acc_bindings, a, &equal?(&1, v))

              :error ->
                Map.update!(acc_bindings, a, &equal?(&1, Map.get(acc_bindings, b)))
            end

          new_records =
            case Integer.parse(b) do
              {v, _} when is_integer(v) ->
                Map.update!(records, a, &[{:eq, v} | &1])

              :error ->
                Map.update!(records, a, &[{:eq, "#{b}=#{Map.get(acc_bindings, b)}"} | &1])
            end

          {new_bindings, new_records, acc_model_no}
      end)
      |> tap(fn {result, records, []} ->
        model_no = Integer.undigits(model_no)

        x = if(rem(model_no, 100) in [51, 62, 73, 84, 95], do: 0, else: 1)

        y = if(rem(model_no, 100) in [51, 62, 73, 84, 95], do: 0, else: rem(model_no, 10) + 5)

        z =
          if(rem(model_no, 100) in [51, 62, 73, 84, 95],
            do: 3_007_898 + div(model_no - 11_111_111_111_111, 100),
            else: 78_205_348 + div(rem(model_no, 1000) - 111, 100) * 26 + y
          )

        prediction = %{"w" => rem(model_no, 10), "x" => x, "y" => y, "z" => z}

        IO.inspect(result,
          label: model_no,
          syntax_colors: [number: :yellow, string: :green, atom: :red]
        )

        # inspect_records(records)

        if(prediction != result) do
          prediction
          |> Enum.filter(fn {k, v} -> Map.get(result, k) != v end)
          |> Enum.into(%{})
          |> IO.inspect(
            label: "prediction    ",
            syntax_colors: [number: :yellow, string: :green, atom: :red]
          )
        end
      end)
    end)
  end

  defp equal?(a, a), do: 1
  defp equal?(_, _), do: 0

  defp inspect_records(records, opts \\ []) do
    label = Keyword.get(opts, :label, "")

    records
    |> Enum.map(fn {k, v} -> {k, Enum.reverse(v)} end)
    |> IO.inspect(
      syntax_colors: [number: :yellow, string: :green, atom: :red],
      label: label,
      width: 180
    )
  end
end