关于elixir:Advent-of-code-2020-elixir-解法回顾-上

Advent of code 2020 elixir 解法回顾（上）

网络上有很多乏味的编程题库，其中 Advent of code 近几年收到越来越多人的关注。起因是题目很乏味，联合圣诞节主题，在圣诞节前的 25 天每天一题。另外不限度编程语言，只须要输出正确答案即可。每做出一题还会失去一颗圣诞树上的小星星，有成就感。往年我应用 elixir 来解题，转眼间曾经做了过半的题目，于是写一篇文章来回顾一下。如果你也想尝试解题，倡议做完再看。

第一天

第一局部是从一个由数字组成的列表中，找到两个数，它们的和等于 2020，返回它们的积。为了让查问快一些，我用了一个 MapSet（查问复杂度 O(1)) 来代替 List (查问复杂度 O(n)) 存储这些数字，而后遍历 List，在 MapSet 中寻找可能和以后的数相加等于 2020 的数。

Enum.reduce_while(list, mapset, fn x, acc ->
  if MapSet.member?(acc, 2020 - x) do
    {:halt, x * (2020 - x)}
  else
    {:cont, MapSet.put(acc, x)}
  end
end)

第二局部是把两个数变成了三个数。能够三次遍历 List，而后应用 raise 语句来抛出异样从在找到满足条件的数时突破循环。因为题目规定不能够重复使用同一个地位的数，所以须要记录每个数的 index。也能够应用三次嵌套的 reduce_while 来寻找答案，益处是不须要 raise 和 index 了，毛病是代码看起来很丑。

Enum.reduce_while(list, list, fn x, list ->
  case Enum.reduce_while(tl(list), tl(list), fn y, list ->
         case Enum.reduce_while(tl(list), tl(list), fn z, list ->
                if x + y + z == 2020 do
                  {:halt, x * y * z}
                else
                  {:cont, tl(list)}
                end
              end) do
           [] ->
             {:cont, tl(list)}

           a ->
             {:halt, a}
         end
       end) do
    [] ->
      {:cont, tl(list)}

    a ->
      {:halt, a}
  end
end)

第二天

第一局部和第二局部都是依据既定的规定来统计非法的“明码”的数量，不同之处是应用的规定不同。第一局部的规定是字符串里某个字母呈现的次数，例如 1-2 z 示意字符串里只能由 1 到 2 个 z。比拟麻烦的中央可能就是把规定解码进去，如果你相熟正则表达式会比拟快。而后依据规定查看每个 “password”。

validate = fn {min, max, [letter], pass} ->
  String.to_charlist(pass)
  |> Enum.count(fn x -> x == letter end)
  |> (fn x -> if x >= min and x <= max, do: 1, else: 0 end).()
end

第二局部的规定是“明码”的某两个地位里，必须有且只有一个地位是给定的字母。例如 1-2 z 示意“明码”的第一位和第二位有且只有一位是 z。能够用 erlang 的字符串匹配来查看某一位的值，而后应用异或逻辑来形容“有且只有”。

xor = fn a, b ->
  if not (a and b) and (a or b) do
    1
  else
    0
  end
end

toboggan_corporate = fn {left, right, , pass} ->
  s1 = left - 1
  s2 = right - 1

  match?(<<_::bytes-size(s1), ^code, _::binary>>, pass)
  |> xor.(match?(<<_::bytes-size(s2), ^code, _::binary>>, pass))
end

第三天

第三天是很有画面感的一道题，甚至有人把它做成了动画。在一个二维的地图上，从左上角登程，依照肯定的规定跳跃前进，统计一路上会遇到多少颗树（用 # 示意），而后返回所有的规定里会遇到的树的数量的乘积。第一局部和第二局部惟一的区别只是口头的规定不同。

slops1 = [{3, 1}
]

slops2 = [{1, 1},
  {3, 1},
  {5, 1},
  {7, 1},
  {1, 2}
]

对于向下和向右，须要用不同的形式去解决，向右的时候，如果达到了地图边缘，像很多老游戏的解决形式一样，又从地图的右边呈现（也能够认为是把地图复制了一份到左边）。

check_tree = fn s, p ->
  p = rem(p, String.length(s))
  String.at(s, p) == "#"
end

for {slops, label} <- Enum.with_index([slops1, slops2]) do
  Enum.reduce(slops, 1, fn {right, down}, acc ->
    s =
      data
      |> Enum.take_every(down)
      |> tl()
      |> Enum.reduce({0, 0}, fn x, {count, p} ->
        p = p + right

        if check_tree.(x, p) do
          {count + 1, p}
        else
          {count, p}
        end
      end)
      |> elem(0)

    acc * s
  end)
  |> IO.inspect(label: "Day3 Part#{label}")
end

第四天

这一题是很常见的业务逻辑：数据格式校验。首先我把数据解析成了 map 格局便于解决，第一局部能够用 match? 来实现，map 构造里的元素是不保障程序的，所以在匹配的时候也不会要求程序统一。说到这个，elixir 里有一个可能会被坑到中央，就是如果你写了两个 function clauses，都用 map 去匹配，即便第二个 clause 永远不会匹配到，elixir compiler 也是不会提醒的。

第一局部的解法：

data
|> Enum.count(&match?(%{ecl: _, pid: _, eyr: _, hcl: _, byr: _, iyr: _, hgt: _}, &1))

第二局部就比较复杂了，还是那句话，如果你很相熟正则表达式，就能够很快地解答进去，如果是像我一样只会用最根底的正则，那可能就麻烦一点。但益处是正则做不到的性能，咱们也能够做到。

rules = [
  {:byr,
   rcheck.(~r/^[0-9]{4}$/)
   |> fand.(range.(1920, 2002))},
  {:iyr,
   rcheck.(~r/^[0-9]{4}$/)
   |> fand.(range.(2010, 2020))},
  {:eyr,
   rcheck.(~r/^[0-9]{4}$/)
   |> fand.(range.(2020, 2030))},
  {:hgt,
   rcapture.(~r/^([0-9]{2})in$/)
   |> fmap.(range.(59, 76))
   |> ffor.(rcapture.(~r/^([0-9]{3})cm$/)
     |> fmap.(range.(150, 193))
   )},
  {:hcl, rcheck.(~r/^#[0-9a-f]{6}$/)},
  {:ecl, fn x -> x in ~w(amb blu brn gry grn hzl oth) end},
  {:pid, rcheck.(~r/^[0-9]{9}$/)}
]

这里的 fand, fmap, ffor 是对匿名函数进行 and ,map,or 的操作，这样就能够用匿名函数来示意规定的一部分，而后用逻辑运算把不同的规定不便地联合在一起。

fand = fn f1, f2 ->
  fn x ->
    f1.(x) and f2.(x)
  end
end

ffor = fn f1, f2 ->
  fn x ->
    f1.(x) or f2.(x)
  end
end

fmap = fn f1, f2 ->
  fn x ->
    case f1.(x) do
      false -> false
      a -> f2.(a)
    end
  end
end

第五天

这道题一开始我规规矩矩地依照题目的形容去二分，计算座位 ID。而看到他人的解法之后，我的心田是解体的。因为所谓的座位 ID，其实就等于 FFFBBBFRRR 依照 F -> 0, B -> 1, L -> 0, R -> 1 转换为二进制后的值。

第二局部能够依照题目的形容去写代码，“找到一个地位，它不在列表里，但它的前一位和后一位都在列表里”.

for id <- 1..(heighest - 1) do
  if not MapSet.member?(set, id) do
    if Enum.all?([id - 1, id + 1], fn x ->
         MapSet.member?(set, x)
       end) do
      IO.inspect(id, label: "Day5 Part2")
    end
  end
end

第六天

问题是“在多个群组外面进行投票，统计合乎规定的选项的数量”，第一局部的规定是：“所有被抉择的选项（不反复）”，第二局部的规定是：“所有人都抉择了的选项”. 能够这样形容这两种规定:

uniq_in_group = fn g ->
  g
  |> List.flatten()
  |> Enum.into(MapSet.new())
  |> MapSet.size()
end

common = fn x, y ->
  Enum.filter(x, fn a -> a in y end)
end

common_in_group = fn [h | t] ->
  t
  |> Enum.reduce(h, common)
  |> length()
end

MapSet 是公认的“找不同”的利器。而“找雷同”能够用 reduce 依此 filter 出那些“我有你也有”的项。

第七天

我把这个问题称为“千层包”，很像是编译器开展宏的流程。首先应用一个嵌套的 map 构造去存储每个“bag”的“定义”，而后应用另外一个 map 去存储开展后的构造。反复地去开展 bag，即用 bag 的“定义”去替换 bag 自身，直到不能再开展为止。

expand = fn rules, contains ->
  Enum.reduce_while(Stream.cycle([1]), contains, fn _, acc ->
    new_acc =
      Enum.reduce(acc, %{}, fn {bag, n}, acc1 ->
        case rules[bag] do
          m when map_size(m) == 0 ->
            %{bag => n}

          nil ->
            %{bag => n}

          contains1 ->
            for {bag1, n1} <- contains1, into: %{} do
              {bag1, n * n1}
            end
            |> Map.merge(%{"opened #{bag}" => n})
        end
        |> Map.merge(acc1, fn _k, v1, v2 -> v1 + v2 end)
      end)

    if new_acc == acc do
      {:halt, new_acc}
    else
      {:cont, new_acc}
    end
  end)
end

这里有一个陷阱，被开展的 bag 本身也须要被记入总数。所以在开展后的 map 里我退出了 "opened #{bag}" 这样的 key，以不便计数。这里的 Stream.cycle([1]) 其实是为了以简略的形式联合 reduce_while 发明一个循环体。第一局部中，须要统计“shiny gold”，只需把它的定义置空，让其不再持续开展即可。

第八天

如果你已经尝试实现一个简略的虚拟机，那么这一题你肯定会感觉不生疏。实质上是依据“纸带”传来的命令去对 state 进行更新。在这一题里，咱们能够这样设计 state 蕴含的内容，别离是 以后的 index，以后的值，和执行过的命令的 indexes。说起这个 jmp 命令呀，就像这道题目外面说的一样，有可能引起有限循环。所以在有一些非凡的虚拟机中，是不存在 jmp 命令的，比方 Bitcoin Script 的虚拟机。

exe = fn
  {"nop", _}, i, a -> {i + 1, a}
  {"acc", v}, i, a -> {i + 1, a + v}
  {"jmp", v}, i, a -> {i + v, a}
end

run = fn d ->
  Enum.reduce_while(Stream.cycle([0]), {0, 0, MapSet.new()}, fn _, {i, a, history} ->
    cond do
      MapSet.member?(history, i) ->
        {:halt, a}

      i == map_size(d) ->
        {:halt, {:terminate, a}}

      true ->
        {i1, a1} = exe.(d[i], i, a)
        {:cont, {i1, a1, MapSet.put(history, i)}}
    end
  end)
end

第二局部，能够像题目中形容的那样，尝试替换 nop 和 jmp 命令，看看能不能运行出符合要求的后果。

第九天

第一局部，找出列表中不合乎“一个数字列表，除了结尾的 pre 个数，之后的数都满足：等于其之前的 pre 个数中的某两个数的和”的数。这里的问题有一点点像第一天的问题，不过因为 pre 的值很小（25），这里应用 List 去遍历就能够了。

one_valid = fn ins, x ->
  Enum.any?(ins, fn y -> (x - y) in ins and 2 * y != x end)
end

valid = fn data, pre ->
  {pres, data} = Enum.split(data, pre)

  Enum.reduce_while(data, pres, fn x, acc ->
    if one_valid.(acc, x) do
      {:cont, tl(acc) ++ [x]}
    else
      {:halt, x}
    end
  end)
end

第二局部，问题是“找出一段在列表里间断的数，它们的和等于指定的数”。咱们能够先假如符合条件的子数列的长度是 1，2，3... 以此类推。在计算子数列中数字之和的时候，也能够用到上一步的后果，例如一个从 index i 开始的，长度为 n 的子数列，它的元素和等于从 i 开始的，长度为 n-1 的子数列的元素和，加上 index i 处的值。这里我用 {sum_of_value, start_index, end_index} 来示意一个子数列。一个细节：子数列的长度每减少 n，子数列的数量就会缩小一个，换句话说，上一步里最初一个子数列不具备持续扩张的能力。

sets = fn
  idata, last_sets ->
    last_sets
    |> Enum.drop(-1)
    |> Enum.map(fn {v, s, e} ->
      {v + idata[e + 1], s, e + 1}
    end)
end

init_sets =
  Enum.map(data |> Enum.with_index(), fn {v, i} ->
    {v, i, i}
  end)

第十天

第一个问题次要是“找到间距为 3 和间距为 1 的相邻数字组合”，首先把数列从小到大排序，而后计算出相邻数字的间距。

distance = fn list ->
  Enum.reduce(list, {[0 | list], []}, fn x, {[h | t], r} -> {t, [x - h | r]} end)
  |> elem(1)
  |> Enum.reverse()
end

第二个问题，“从最低层到顶层有多少种门路”，首先在脑海中设想一下这些门路的的图，是一个树状的构造，须要统计它的叶子节点的数量。看到树，就想到了形象语法树，从而想到宏的开展，进而想到了第七天的问题，间接把第七天的代码复制过去稍作批改就能够解决。这里的细节是如何把被节点结构成 {node, children} 的构造，每个 child 必须是在汇合中，且满足比 node 的值小 1 到 3 .

before = fn x -> (x - 3)..(x - 1) end

attach_before = fn x, set ->
  {
    x,
    before.(x)
    |> Enum.filter(fn y ->
      MapSet.member?(set, y) and y >= 0
    end)
    |> Enum.map(fn x -> {x, 1} end)
    |> Enum.into(%{})
  }
end