Advent of code 2020 elixir 解法回顾 (上)node
网络上有不少有趣的编程题库,其中 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, [code], 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 也是不会提示的。code
第一部分的解法:排序
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