乐趣区

关于leetcode:2021年做的最痛苦的一道编程题-Advent-of-code-2021-day24

老铁们是否据说过 https://adventofcode.com/ 这个网站,在每天的圣诞前夕,它就会开始间断 25 天公布编程谜题,吸引了有数人参加。从我开始学编程那会儿,就有用这里的题目来锤炼本人的编程能力。

2021 年的题目的难度是逐步加深的,越往后越艰巨,我保持做完了前 23 天的题目,直到看到第 24 天的题目,死磕了很久,还是想不进去。

题目大略是这样:有一种计算单元,具备 w,x,y,z 四个寄存器,反对以下几种指令:

  • inp a(读取用户输出的数字,保留于寄存器 a)
  • add a b (a 与 b 之和保留于 a。b 能够是数字或寄存器)
  • mul a b (… 乘积 …)
  • mod a b (… 余数 …)
  • div a b (… 整除 …)
  • eql a b (如果 a 等于 b,为 1,否则为 0。后果保留于 a。b 能够是数字或寄存器)

而后给定一串指令,令用户输出一串 1~9 的数字,使寄存器 z 的后果等于 0. 求用户输出的数字按程序组成的十进制数的最大和最小值。

尝试解题

一开始我千方百计优化给定的指令,比方 add a 0mul a 1 能够间接省略,最初发现优化完了还是很长一串,没什么卵用。

再起初想到 div a b 时如果 a < b 则为 0。加上咱们晓得单个输出的范畴是 1..9,往后能够依据数字的范畴来进行优化,最初失去 z 的范畴。

卡在这里没方法停顿上来了,一个月之后,我终于忍不了了,在 reddit 上查看了一下大家分享的解题办法。次要的办法是逆向剖析给定的指令,从而得出对于输出值的限度条件。看到这里我有点悲观,尽管逆向剖析也很酷,然而 AOC 之前的题目很少有对输出做假如的,我更心愿应用一种通用的解法,可能实用于任意的指令列表。

终于,我看到了某位大神的解法,完满满足了我的需要。

解法

次要的思路和我之前是一样的,即剖析每一次计算的后果的最大和最小值。最牛的中央是大神不是只剖析一次,而是每一次 inp a 指令读取完一个用户输出的值,就再从新剖析一次计算结果的范畴。设 i(n) 是第 n 个 inp 指令读取的用户输出。例如,当咱们没有给定 i(1) 的值时,i(1) 的范畴是 {1, 9},最初剖析进去 z 的范畴可能就是一个很大的区间。但咱们给定 i(1) 为一个常数,最初剖析进去的 z 的范畴就有可能会小很多。

以此类推,咱们每给定一个 i 值,就做一次剖析,如果 z 的范畴不包含 0,咱们就晓得这次的 i 的序列没必要继续下去。反之,就能够持续给下一个 i 的值。

以下是残缺的代码

inputs = File.read!("inputs/d24.dat")

defmodule S do
  @moduledoc """Thanks ephemient's excellent answer! Rewrote from https://github.com/ephemient/aoc2021/blob/main/rs/src/day24.rs .
  """@doc"""
  Parse instructions.
  """
  def parse(str) do
    str
    |> String.split("\n")
    |> Enum.map(fn line ->
      case String.split(line, " ") do
        [h | t] ->
          {parse_op(h), parse_args(t)}
      end
    end)
  end

  defp parse_op(op) when op in ~w(inp add mul div mod eql), do: String.to_atom(op)

  defp parse_args(list) do
    list
    |> Enum.map(fn x ->
      if x in ~w(w x y z) do
        String.to_atom(x)
      else
        String.to_integer(x)
      end
    end)
  end

  def new_alu, do: %{w: 0, x: 0, y: 0, z: 0}

  @nothing :nothing

  def check_range(ins, alu) do
    alu =
      for {r, v} <- alu, into: %{} do
        {r, {v, v}}
      end

    alu =
      ins
      |> Enum.reduce_while(alu, fn inst, alu ->
        case inst do
          {:inp, [lhs]} ->
            {:cont, %{alu | lhs => {1, 9}}}

          {op, [lhs, rhs]} ->
            {a, b} = alu[lhs]
            {c, d} = alu[rhs] || {rhs, rhs}

            lhs_range =
              case op do
                :add ->
                  {a + c, b + d}

                :mul ->
                  Enum.min_max([a * c, a * d, b * c, b * d])

                :div ->
                  cond do
                    c > 0 ->
                      {div(a, d), div(b, c)}

                    d < 0 ->
                      {div(b, d), div(a, c)}

                    true ->
                      @nothing
                  end

                :mod ->
                  if c > 0 and c == d do
                    if b - a + 1 < c and rem(a, c) <= rem(b, c) do
                      {rem(a, c), rem(b, c)}
                    else
                      {0, c - 1}
                    end
                  else
                    @nothing
                  end

                :eql ->
                  cond do
                    a == b and c == d and a == c ->
                      {1, 1}

                    a <= d and b >= c ->
                      {0, 1}

                    true ->
                      {0, 0}
                  end
              end

            case lhs_range do
              {a, b} ->
                {:cont, %{alu | lhs => {a, b}}}

              @nothing ->
                {:halt, @nothing}
            end
        end
      end)

    case alu do
      @nothing ->
        @nothing

      %{z: {a, b}} ->
        a <= 0 and b >= 0
    end
  end

  def solve([], _, prefix, alu) do
    if alu.z == 0 do
      prefix
    else
      nil
    end
  end

  def solve([inst | rest], nums, prefix, alu) do
    IO.inspect(prefix, label: "prefix")

    case inst do
      {:inp, [lhs]} ->
        nums
        |> Enum.find_value(fn num ->
          alu = %{alu | lhs => num}

          if check_range(rest, alu) != false do
            solve(rest, nums, 10 * prefix + num, alu)
          else
            nil
          end
        end)

      {op, [lhs, rhs]} ->
        a = alu[lhs]
        b = alu[rhs] || rhs

        result =
          case op do
            :add -> a + b
            :mul -> a * b
            :div -> div(a, b)
            :mod -> rem(a, b)
            :eql -> if(a == b, do: 1, else: 0)
          end

        solve(rest, nums, prefix, %{alu | lhs => result})
    end
  end
end

# test

insts =
  inputs
  |> S.parse()

# part 1
S.solve(insts, Enum.to_list(9..1), 0, S.new_alu())
|> IO.inspect()

# part 2
S.solve(insts, Enum.to_list(1..9), 0, S.new_alu())
|> IO.inspect()
退出移动版