livexia
reading
tags

参加2023年Advent of Code

[Coding] Posted on Dec 27, 2023 · 93 minute read

[toc]

Rust Hints

Things to Learn

Day 1

Part 2 一些特别的思路

Day 2

所耗时间均在对输入的处理上，解决问题的思路直截了当。

Day 3

依旧需要小心的处理输入，涉及到二维的矩阵，往往有两种方法：一是利用二维 Vec 进行表示，二则是利用 HashMap 进行表示。如果利用 Vec 那么在涉及到对周边节点遍历时，在 Rust 中要注意对 usize 数据类型可能的 underflow ，利用 HashMap 则可以利用 i32 作为矩阵的坐标数据类型。

在具体的算法上，我选择利用深度优先搜索，进行解决，具体思路如下：

  1. 从矩阵的右下角开始进行深度优先搜索，从右到左，从上到下的顺序分别进行dfs。
  2. 如果当前元素是数字，那么这个数字必然是一个数字的组成部分，同时也是这个数字的最低位，这样的搜索顺序可以方便的对最终结果进行结合。
  3. 同样的如果当前元素是数字，那么可以对这个数字的邻接元素（8个）进行判断，如果其中存在一个符号，设标识，表示当前数字同一个符号相邻。
  4. 除了对邻接元素进行判断，同时要对当前元素的左侧元素进行递归的深度优先搜索，深度优先返回得到整个数字除了最低位的部分，对这个结果乘 10 加上当前元素的数字，即是完整的数字。
  5. 同样的一个数字任意位的邻接是符号，则整个数字都与符号邻接，于是需要在深度优先的搜索过程中保留标识，每次都对标识进行或运算。
  6. 在深度优先搜索中引入 visited ，确保元素不被重复搜索。
  7. 总结：深度优先搜索是从一个数字开始，在一行中向左继续搜索，搜索过程中取得一个完整的数字，并确认整个数字是否存在部分与符号邻接。
  8. 第一部分的方法即是如此，第二部分则稍有不同，但整体思路是一致的，在深度优先搜索中，要判断数字的组成部分是否与齿轮符号邻接，并保留数字每个组成部分对应的齿轮符号坐标（一个齿轮可能与多个数字邻接，同时一个数字也可能与多个符号邻接）。
  9. 在每一次深度优先搜索后，就得到了数字与邻接齿轮的对应关系，在这个基础上再对问题进行解答即可。

Day 4

这个问题的输入并不复杂，每一行输入包含了两个数组，第一部分要求计算第二个数组中的数字在第一个数组中出现的次数，直接暴力匹配实现即可。第二部分需要在这个基础上再进一步的计算，在此以示例输入为例进行阐述：

性能优化？

Rust Tips

Day 5

输入稍显麻烦，并不是特别的困难，对每行进行循环处理即可。问题中的 Map 其实就是对应关系，每一条 Map 由三个部分组成分别是 dest src 和 length ，可以将 Map 表示为函数，对于范围在 [src, src+length) 的输入数字 input ，可以通过如下计算得到转化后的 result = dest - src + input ，第一部分就是对输入的 seed 不断的进行计算最后得到 location ，选取其中最小值即可。

第二部分在第一部分的基础上进行扩展，每两个输入的 seeds 表示 seed 的区间，同样需要计算所有区间内 seed 经过转化最后得到的 loaction 中的最小值。首先尝试直接对区间内的每一个 seed 进行暴力求解，但是因为的实际输入范围较大，运行时间较慢，所以很快的放弃，在完成后阅读 Reddit 社区的解答后发现，实际上暴力求解虽然慢，但是并不是需要几天的那种，如果让它跑完，也许在十分钟内也能取得结果。

既然不选择使用暴力，实际上这个问题就是涉及区间的问题，如果能够对整个输入的 seed 区间，进行转换，那就减少了大量的计算，对一个输入 input 区间作用某一 Map 转换逻辑如下：

  1. 将 Map 转为区间转换的表示方式：[src, src + length) ，同时 offset = dest - src ，那么就有 [src, src + length) -> [src + offset, src + length + offset)

  2. 设输入区间 input 为 [start, end)

  3. 那么只需要计算 [start, end) 和 [src, src + length) 的重叠区间 overlaps ，再加上 offset 即可得到输入区间 input 经过 Map 转换后的部分区间

  4. 根据题意，如果一个 seed 无法被同一阶段的任意 Map 进行转换对应，那么就直接进行转换 （10 → 10）

  5. 所以仅仅得到 input 和某一个 Map 的重叠区间仍旧不够，仍旧需要判断除重叠区间外的 input 区间是否能够被同一阶段的其他 Map 进行转换，也就是需要依次对剩余的 input 区间和剩余的同一阶段的 Map 进行转换，当所有同一阶段的 Map 都完成了转换后，如果 input 区间还剩下，那么依旧需要将剩下的区间保留到下一阶段，具体代码如下：

    fn convert_range(
    input: Range,
    dest: Number,
    src: Number,
    length: Number,
) -> (Vec<Range>, Option<Range>) {
    // src range: src..src+length
    // src and dest offset is: dest - src
    // then: dest = src + offset
    let offset = dest - src;

    let src_end = src + length;
    let (start, end) = input;
    if end <= src || src_end <= start {
        return (vec![input], None);
    } else {
        let overlaps = Some((start.max(src) + offset, end.min(src_end) + offset));
        // input range overlaps with range Number::MIN..src and range src_end..Number::MAX
        // is the remain range of input
        let remain_range: Vec<Range> = [(start, end.min(src)), (start.max(src_end), end)]
            .into_iter()
            .filter(|(a, b)| a < b)
            .collect();
        (remain_range, overlaps)
    }
}

fn convert_range_with_maps(range: Range, maps: &[SingleMap], converted: &mut Vec<Range>) {
    if maps.is_empty() {
        converted.push(range);
        return;
    }
    let (dest, src, length) = maps[0];
    let (r_ranges, overlaps) = convert_range(range, dest, src, length);
    if let Some(overlaps) = overlaps {
        converted.push(overlaps);
    }
    for r in r_ranges {
        convert_range_with_maps(r, &maps[1..], converted);
    }
}

  6. 根据输入，对每个阶段都进行同一阶段的 Maps 转化和对应，不断得到新的输入区间，直到完成所有的转换对应阶段，对最后得到的所有区间的起点取最小值即是第二部分的解

性能优化

Day 6

输入的处理很简单，第一部分将两行输入转换为数组，第二部分则将两个数组分别组成一个大数。直接根据题意进行了暴力解答，题意理解如下：

因为涉及的不等式并不复杂，而且第一第二部分给定的输入都并非超级巨大，所以暴力求解也可以轻松完成。但是既然涉及不等式，那么就可以简单的对不等式进行求解，取得答案，思路如下（虽然是初中数学，但是依旧进行了搜索，根本记不住公式，记住的部分也是错的，数学都还给老师了）：

Day 7

题目并不难，为了构造正确的数据类型而花费了大量的时间，思路如下：

Day 8（TODO）

第一部分直接按照题意思路求解即可，第二部分有以下几种思路。

  1. 暴力
    • 取得以 A 结尾的所有起始节点，在取得所有以 B 结尾的所有结尾节点
    • 每一次都按照指令对所有当前节点进行遍历，直到当前的所有节点与所有结尾节点相同
    • 但是实际输入巨大，而导致几乎不可能在有限时间内取得结果
  2. 提前计算
    • 按照第一部分的方法计算出所有的一个启示节点到一个结尾节点需要几步
    • 假如一个起始节点只能到达一个唯一的结尾节点，同时一个结尾节点也只能由一个唯一的起始节点到达，那么第二部分所求的就是这些路径长度的最小公倍数 lcm
    • 题目并未明确的指出起点和结尾是一一对应的，所以理论上是可能存在多种方式达成题意要求，而最后的结果则是这多种方式的最小值

环检测算法

DFS

性能优化

Day 9

题目很简单，输入并不复杂，按行解析为数组即可，第一部分直接按照题目要求进行解答即可。第一部分思路如下：

第二部分要预测输入数组的第一个元素：

实际上第二部分存在一种取巧的方法，可以将输入的每一个数组都进行倒序，然后按照第一部分方法计算即可。

Day 10

Brute Force and BFS [code]

Move along and DFS/BFS [DFS/BFS]

第一部分上述两种思路和方法都可以得出正确的解，但是对于第二部分，实际上第二种方法更加合理，从思路和逻辑上看也是第二种方法更加清晰，更容易理解题意。尝试在第一种方法的基础上实现第二部分，耗费了我大量的时间，同时因为这种方法存在混乱，使得迟迟无法对第二部分作出有效的解答，所以狠下心来重新按照第二种方法解决了第一部分，也较容易得处了第二部分所需要的循环路径上的节点，当然第二部分也依旧没有因此而快速解决，以下几种解决第二部分的方法，我只实现了第一种 Double Resolution / Flood Fill ，其余的方法都来自 Reddit ，我认为都是要优于我自己想到的方法。

Double Resolution / Flood Fill [code]

Line Crossing (Ray Casting) / Shoelace Theorem? [code]

这个方法我根本没想到，记忆里往年也是有用这个方法的，这个方法不算是平时算法练习里会出现的，感觉上这个方法是正确的，但是并没有阅读过完整的证明，即我只知其然，不知其所以然参，考链接如下：

算法概述

具体思路

More Solutions

计算机图像处理?

标记循环移动方向同一侧邻接节点（未实现）

Day 11 [code]

今天的题目思路简单明了，输入为网格，记录其中字符为 # 的位置，第一部分要求将网格的中不包含任何的行和列都翻倍，而第二部分则是将这个倍数增加到 1000000 倍，要求计算翻倍后每一对唯一的 # 间的最短距离。

网格翻倍： - 第一第二部分仅有扩张倍率不同，设变量 expansion_rate 表示

最短距离：因为是网格，同时网格间并不存在任何阻碍，所以直接计算曼哈顿距离即可 $D=∣x1​−x2​∣+∣y1​−y2​∣$

性能优化：利用 HashSet 保存 # 的坐标，固然可以在查找时避免麻烦，但是在这个问题中完全没有必要，可以直接用 Vec 保存。

Day 12 (TODO)

DFS with Cache [code] = DP ?

if springs[i] == ‘.’ dp[i] = dp[i - 1]

if springs[i] ≠ ‘.’ count += 1

Rust @

https://doc.rust-lang.org/book/ch18-03-pattern-syntax.html#-bindings

Day 13

题意要求查找矩阵的对称轴，题目并不难，逻辑很简单，因为对称轴可能是出现在行上也可能是出现在列上，可以先计算一个方向上的对称轴，再将矩阵转置在重复计算即可，直接暴力实现。

虽然题目的输入处理很简单，同时逻辑也不复杂，输入的数据量也不大，所以理论上应该是很容易的题目，但是我在第二部分卡了很长时间，原因就是在第二部分题意的理解上，第二部分有一句题目描述为 “you discover that every mirror has exactly one smudge” ，我没能注意到其中的关键词 exactly 以致于浪费了太多的时间，具体思路[code]如下：

性能优化

利用数字表示矩阵的每一行和每一列，同时用位运算进对称比较 [code]

Day 14 [code]

第二部分涉及环检测，使用了第八天里也用到的环检测算法，计算环的起始点和大小，再取得最后结果，题目并不难，但最后我对性能并不是特别的满意，所以在具体平台倾斜的实现上进行了优化。

环检测算法 [code]

往年我都是要用哈希表进行环检测，今年遇到环的问题，我都选择用快慢指针算法实现，相比于哈希表，两种方法的对比：

Floyd 快慢指针

性能优化

Day 15

第一部分需要实现哈希，第二部分则需要实现类似于哈希表。第一部分按照题意实现即可，第二部分的题意有点复杂，但是理解题意之后其实也是很简单的。输入的数据量也不大，直接实现即可。第一部分不需要说明，简单说明第二部分：

部分处理代码如下：

let mut map = vec![vec![]; 256];

for step in steps {
    let (k, l, v) = step_to_instr(step);
    let p = map[k].iter().position(|(i, _)| i == &l);
    match (v, p) {
        (Some(f), None) => map[k].push((l, f)),
        (Some(f), Some(i)) => {
            map[k][i] = (l, f);
        }
        (None, Some(i)) => {
            map[k].remove(i);
        }
        _ => (),
    }
}

Day 16

今天的问题并不难，光线按照方向移动，根据新位置处可能的镜子调整移动方向，计算光线移动的路径，除了方向的改变，光线在遇到特定的镜子时还会产生分裂，我通过利用 BFS 实现了第一部分。第二部分是在第一部分之上计算从四周发出光线，每个位置发出光线移动路径的最大值。唯一需要注意的点就是光线的起始点，如果光线在起始点就遇到了镜子，那就需要根据镜子先调整方向。这点可以通过在平台外设置一个虚拟的起点解决，也可以首先对起点和起点处的镜子计算下一个可能的方向。代码的实现很简单，可是性能却并不好，第二部分主要的运行时间都是在 BFS 中对当前状态的访问情况进行检查上，而我在尝试提升性能时引入了错误的逻辑，导致性能提升，但是结果错误。

错误的调整：调整了 BFS 中 visited 的检测位置，代码运行时间从 4s → 80ms [code]

image

性能提升

因为主要的时间损耗是在 BFS 中的访问检测上，那么就要考虑从这个方面入手。

Day 17 (TODO)

实现的思路并不复杂，但是求解空间巨大，无论用何种方法都需要剪枝，动态规划虽然不需要剪枝，但是因为路径选择存在前后依赖关系，需要保存的状态几乎等同于求解空间，也不现实。位置的移动并不是简单的上下左右移动一个，第一部分要求最长的同一方向移动距离为三，也就是说以一个方向移动三次必须要转向，那么对于当前位置最多存在六种可能的状态。这个地方存在两种处理，一就是只关心这六种可能的状态，省略中间状态，这个方法的好处是不需要考虑连续移动的次数，也一定程度减少了求解空间，但是却也影响了剪枝的范围（剪枝时依旧需要考虑当前连续移动的距离）。最后通过剪枝的 BFS 取得两个部分的解，但是应该可以用最短路径的算法进行求解。

BFS

尝试通过 BFS 实现，但是在节点的访问状态判断上 BFS 并不正确，如果应用一个 visited 到整体的 BFS 会导致搜索路径的不完全，虽然节点是完全访问了，但是却无法取得所有的搜索路径，自然也就无法取得最终的结果，应该使用 DFS。

如果不使用 Visited 那么就要进行剪枝，引入 HashMap 记录当前位置和移动方向的最小 loss ，当遇到同样的状态时，判断当前 loss 是否小于记录值，如果不小于记录值，那么就不入队，实现剪枝。运行速度依旧堪忧，release 版本，运行需要 3s。第二部分和第一部分完全一致，引入节点的移动范围参数即可。

虽然没有对单条路径使用 Visited ，但是实际上如果在一条路径中，以同样的方向进入同一个节点两次，那么第二次的 loss 一定大于第一次，这样也就组织了可能的重复访问。

如果能够证明在一条路径中，无论以何种方向进入同一个节点两次，第二次的 loss 一定大于第一次，那么就能进一步剪枝。

DFS

可能的路径太多，需要剪枝，引入缓存。应该可以用同 BFS 一样的方法进行剪枝。

BFS + 最小堆：依旧需要剪枝，子问题的最优解之和并不等同于最优解。

动态规划

前一次选择的路径会影响到下一次的路径选择，dp 应该是不能用的，(0, 0) 到 (1, 2) 的最短路径应该是 3 ，但是(0, 0) 到 (4, 6) 的最短路径中(0, 0) 到 (1, 2) 的路径长度应该是 5， 也就是说部分的最优解并不等同于最终最优解

1111999
9911999
9919999
9911199
9999111

Dijkstra's algorithm (TODO)

Day 18 (TODO)

问题的输入处理并不复杂，第一部分根据输入首先构造边，再利用 Ray Cast 算法计算被边包含的大小即可。第二部分对输入的变化依旧不复杂，但是每一条边的长度都被放大，再用第一部分的方法，求解空间将会变得巨大，简单的将所有边包含的位置记录在 HashSet 中就需要及其长的时间，更别提在 Ray Cast 中需要遍历的一个一个位置了。

鞋带定理

https://en.wikipedia.org/wiki/Shoelace_formula

皮克定理

https://en.wikipedia.org/wiki/Pick's_theorem

Day 19 [code]

今天的题目依旧不算特别难，但是我在输入的处理上花费了太多的时间，第一部分的排名并不优秀，第一部分的实现根据题意实现模拟即可，注意细节即可。第二部分扩大了第一部分的求解空间，如果依旧按照第一部分的模拟实现，那么程序将无法完成运行，第二部分要求 x m a s 在 [1, 4000] 的范围内进行组合，计算所有组合中会被工作流接收的个数。如果构造组合，再根据第一部分实现的模拟一一判断，这是不现实的，所以需要另辟蹊径。问题太大的时候首先考虑对问题进行分解，初始问题描述如下：

分解问题：以工作流 in{s<1351:px,qqz} 为例

递归代码实现，也可以用队列迭代实现。

Day 20

第一部分根据题意模拟实现即可，求解空间并不大，循环一千次的模拟在可承受范围内。第二部分首先依旧尝试模拟实现，可惜短时间内根本无法取得解，最后得结果数量级是 100千亿 ，这不是模拟能够解决的，需要寻找更好的方法。自己虽然观察了输入，但是却没能想出具体的实现，最后参考了 Reddit 的题解，才终于得处答案。第一部分代码对任何的输入都可行，第二部分则只支持 rx 依赖一个 Conjunction 模块，同时这个 Conjunction 模块又依赖于其他的 Conjunction 模块，同时这些 Conjunction 模块发出高位是存在循环规律的，第二部分会给出每一个模块的可能循环大小，需要手动根据循环计算这些模块的最小公倍数，最后取得结果。

第二部分

观察给定的输入，可以发现 rx 仅依赖 vd ，而 vd 则依赖于 rd bt fv 和 pr ，vd rd bt fv 和 pr 都为 Conjunction 模块，所以如果 rx 要接收到低位，那么 vd 要发出低位，则 vd 的四个输入模块都必须发出高位，那么当 rd bt fv 和 pr 都发出高位时，rx 就能接收到低位。因为 rx 仅依赖于 vd ，那么求 rx 和求 vd 的求解空间应当是一样大的，所以就需要考虑 vd 依赖的四个模块，如果这四个模块存在一定的规律那么就可以将问题划分，减少求解空间。根据分析输入所得到的依赖关系，利用代码计算这四个模块发出高位所需要的按键次数，如果循环出现，那么说明存在规律，最后只需要计算四个模块发出高位次数的最小公倍数即是题解。

虽然第二部分涉及的代码是同第一部分一致的，但是在利用代码计算这四个模块发出高位所需要的按键次数的时间点很重要，因为 vd 这四个模块，所以要在经过 vd 模块就检测这四个模块发出的高低位，如果在按完一次按钮的最后，再检测这四个模块，那就可能无法检测到这四个模块的状态变化。这个细节也是为何我虽然知晓求解方法，但是依旧耗费了不少时间的原因。

Day 21(TODO)

第二部分

Day 22[code]

今天的题目并不难，核心的问题就是砖块掉落，是否会和下方的砖块产生碰撞。第一部分第二部分都是在这个基础之上进行求解。我首先就想到砖块实际上就是两个线段，是否会产生碰撞，那么只需要计算线段是否存在交点即可，参考了几个 stackover flow 的解法，可惜最后的答案不对。最后用了笨办法，那就是记录砖块占据的所有网格位置，碰撞时统计各自占据的网格位置是否存在重叠即可，笨办法替换了线性代数之后可以顺利解决两个部分，虽然运行速度不快。对比两个检测碰撞的方法，发现在两个线段存在重叠时，线性代数的方法会得出错误的结果，可惜我的线性代数学不到家，只看数学我是根本不知道问题何在。

线性代数检测线段相交[code, fixed code]

性能优优化[code]

构造支撑图[code]

根据初始完全落下所有砖块，构造砖块与砖块之间的支撑关系

Day 23[code]

需要计算最长路径，第一部分限制了部分节点的移动可能，于是很容易的利用 DFS 求解即可。第二部分则无法这样简单的实现，因为涉及到大量的可能路径，求解空间巨大，于是用 DFS 首先可能会栈溢出，然后就是运行时间过久，无法得出结果。即然简单的 DFS 不行，那么是不是可以引入缓存呢？可惜还是不行，缓存只记录在某一个路径中的最长部分，但是这个最长并不适用于另一个路径，也就无法正确的得出结果。通过搜索我发现还存在一种方法就是利用拓扑排序确定最长路径，拓扑排序要求是有向无环图，实现之后依旧无法计算出最长路径，原因就是在网格中移动的路径的确是有向无环图，但是如果把所有的可能路径都考虑到，那么实际上题目给出的网格是有环图，所以拓扑排序依旧不可行。

不优化的 DFS 方法 release 编译运行了 1268s 得出正确的解

可行的缓存：缓存需要记录的状态，当前经过的所有路径，这样可以确保不同路径之间不会产生干扰，可是需要记录的状态太大，不太现实？

将网格转化为图，并对图进行合并（剪枝）[code]

性能优化[code]

Day 24

今天的题目不是编程题，更像是数学题，第一部分要求二元一次方程组，第二部分要求九元九次方程组。第一部分因为涉及到的方程组数量较少，所以我手动推导出求解过程，代码中再进行计算。第二部分我则代码打印出方程，寻找到在线求解方程组的网站进行求解，第二部分这样居然进了前一千。今天的问题主要就是需要计算直线相交的，这和第 22 天计算线段相交的问题实际上是一模一样的。涉及到数学和线性代数，我并不是完全理解，但是没办法，也就是这样了。

题意分析：

求解思路

使用 Solver 求解方程

z3 [code]

good_lp

Day 25

以为今天的题目会很简单，结果是我不熟悉的题目。给定的输入构成一个无向有环图，需要求解断开哪三个边可以使得图产生分裂，计算分裂后图的节点数乘积。因为不知道解决这个问题有什么特定的算法，所以我决定直接直接暴力遍历所有的可能边的组合，很可惜暴力是跑不出什么结果的。

对边进行排序，提升暴力搜索的效率 [code]

利用 Graphviz 生成图的可视化 [pic]