老铁们是否据说过 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 0，mul 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  endend# testinsts =  inputs  |> S.parse()# part 1S.solve(insts, Enum.to_list(9..1), 0, S.new_alu())|> IO.inspect()# part 2S.solve(insts, Enum.to_list(1..9), 0, S.new_alu())|> IO.inspect()