Advent of Code 2024

[Coding] Posted on Dec 25, 2024 · 110 minute read

https://adventofcode.com/
https://github.com/livexia/advent-of-code-2024

移除所有的 input.txt

根据社区和作者的规定，其实参与者并不允许上传 input 到公共仓库，我之前一直没有意识到这个问题，所以为了可确定性所以一直上传输入，今天意识到这个问题，所以删除了所有的输入，也许还有少量残留（不太可能）。

使用的方法来自社区：

Puzzle Inputs
git filter-repo --path-glob "2022/*/input" --invert-paths --force was the nice way to fix this for me. Edit the glob to match how you had inputs saved
- 需要重新配置仓库远端地址，同时需要强制推送代码，以及 github 可能存在短暂的更新延时，以及可能的云端缓存，不是很确定，以及会丢失本地的 input 文件，也算是我的教训吧，下次记得要检查类似的问题。
- fragger
newren/git-filter-repo

Day 1

太久没编程，还好大部分的记忆还在，有一点点手生，但是没什么问题。

Day 2

第二天的题目并不困难，第一部分很简单，前后比较即可，第二部分虽然想有更好的方法，但是思路并不那么清晰，最后就暴力解决了，因为输入的问题，所以效率也不差。输入的数据每行的长度也不大，同时数据每行大都是有序的，而且也只考虑移除一个元素后数列的变化情况，所以实际上问题的求解空间就不大。如果输入数列趋于无序，同时需要计算删除最少元素以保证数列排序要求，那么求解空间就变得很大了，暴力实现也就不怎么现实了。在社区上简单浏览了一下也没有看见贴别好的方法，也许还要再等等吧，就这样了。

Day 3 （正则处理输入）

第三天的题目依旧不困难，但是在输入的处理上稍有麻烦，太久没编程都忘了还能用 regex 处理输入了，刚开始想要自己实现输入的匹配，但是没能下定决定，然后浪费了不少时间。虽然对 regex 并不是很熟练，但是基础还是有的，所以写个简单的表达式并没有问题，利用网站简单的测试，再根据 regex 的文档很容易的就实现了输入的解析和处理。对输入的计算其实很容易，再处理完输入之后很容易就可以得出结果。

Day 4

今天的题目真的很简单，但是我却花了太多的时间，第一部分很快就有解决方法了，以为会出现的深度搜索也不需要，最后我的示例答案和正确答案差 1 ，我就知道有个边界错误了，但是光看是看不出来的，最后在纸上手动计算了一下，对比了差异，果然在边界上判断错误了。可能是小瞧了难度，所以写代码的时候有点过于花样多了，导致要从代码调试输出更加困难，而我又不想改，所以浪费了很多的时间。第一部分需要在水平、垂直和对角方向上搜索单词，注意无论是什么方向，单词都是在一行的，这极大的降低了问题难度。从一个位置出发，实际上需要匹配八个方向的所有可能，因为单词可以是翻转的，所以我并没有匹配八个方向，而是判断当前位置是和单词的第一个字符还是最后一个字符相同，如果和最后一个字符相同，那就翻转单词，这样在一个位置其实最多只需要寻找四个方向。第二个部分更加简单，只需要找到所有的字符 A 即可，判断以 A 为中心的，两个对角线的单词是否是 MAS 或 SAM 即可，只有都满足的情况才是正解，也就是说对于一个字符 A 其实只存在一个可能性。第一部分中无论是对于字符 X 还是 S ，其实都存在四种可能（我的解法）。吸取教训，不要求快，求快反而更慢了。

Day 5

今天的题目依旧不难，但我还是太不熟练了，在很多的地方有的思路并不是最佳的，这些思路可能一年前对我来说是很自然的。题目给出的输入是一组排序规则，其中确定部分元素的前后关系，还有的一部分输入是可能有序的序列，第一部分要寻找其中已经按照排序规则有序的序列，取得中间元素的值。第二部分则要对未排序的序列进行排序，取得排序后序列中间元素的值。我的思路很直接明了，就是搜索，我先把输入的序列规则进行了处理，确定在一个元素之后的所有元素（对输入规则进行拓扑排序）。题目要求的是，需要排除序列中没有元素的排序规则，所以实际上对每一个序列都需要处理输入规则，也就是说对不同的序列，其实有不同的排序规则，因为如果不针对输入序列进行再次处理，会发现输入规则的拓扑排序存在环，那么所有的排序都是可行的，但其实存导致环的规则并不会同时出现在一个序列中，所以对于任一序列，规则是不存在环的（因为排除了）。按照我的方法，处理排序规则就已经有不少的复杂度了。然后在第二部分，需要对未排序的序列进行排序，我使用的排序算法也不是最好的，遍历比较前后元素，如果不符合排序规则就交换两个元素，然后回溯比较前一对是否有序（当前两个交换会影响前一对的比较结果）。

其实除了没有使用更好的排序算法，我的方法没啥问题，对需要的规则进行拓扑排序，但是在阅读社区的解法和讨论之后，我意识到对于序列中任何两个相邻的元素，必然存在规则确定二者的大小关系，即如果存在 a|b 和 b|c 两条规则，那么规则 a|c 必然存在，所以对于某一输入序列而言，实际上一定存在对应的规则，也就是说对于某一输入而言，其实完全不需要进行拓扑排序，即可能发生的比较都已经在需要的规则中确定好了，只需要取用即可。在对自己爹输入测试之后果然如此，理所当然的这个方法比我自己的方法要快很多。

参考：[2024 Day 5]Rules are not a DAG

Day 6 （关注细节）

今天的题继续不难，提交的成绩比前几天好太多了，但是在完成之后需要进行优化时依旧卡壳。这类型的题目已经是 AOC 的传统艺能了，所以在输入处理和抽象建立上并没有问题，第一部分就是按照提议要求模拟行走就行，很简单。第二部分很明显复杂了一些，但是本质上还是做 N 次第一部分的内容，所以实际上理解也不困难，并没有很直接的算法能够加快这个过程。很自然的，我尝试用暴力法，逐一替换给出地图中的路径为障碍，然后一一测试是否存在环路，环路判断只需要用 HashSet 保存守卫的位置和前进方向，然后当再次遇到状态一模一样的守卫时，就发现了环。理所当然的这个方法的效率并不好。因为每次守卫巡逻，最多只允许替换一次路径为障碍，那么实际上对那些守卫本就不会走到的路径就没有必要替换为障碍进行测试，所以可以先把不替换时守卫巡逻的所以位置进行记录，然后只需要对这些位置进行替换，再测试环即可，这可以大量降低运行时间。那么能不能再进一步加快运行效率呢？我就是卡在这个问题上了。在前面两种方法中，每次替换并检测环的时候，守卫都是从起始位置行走的，那存在大量的重叠运算，假如被替换的位置处于守卫巡逻路径的最后部分并且相邻，那么理论上可以对部分的运算进行复用。所以我就有了这样的思路，守卫在巡逻路径上某一个位置的时候，他存在两种选择，第一就是按照未替换的巡逻路径前进一个位置，或者把路径下一个位置替换为障碍，即守卫进行转向。对于巡逻路径上的每一个位置都存在两种选择，所以对于长度为 N 的巡逻路径未替换的路径需要计算一次，除去初始位置其余位置都需要计算一次。如果路径不存在交叉，也就是最理想的情况，那么总共需要移动的次数就是 N + (N - 1) + (N + 2) + ... + 1，这个结论不完全正确，因为当一个位置被替换后，其实路径的长度也会变化。刚开始我一直没有考虑可能的路径交叉情况，正是在这个情况的判断上，我无法取得正确的结果。

考虑位置 A 处于巡逻路径的某个位置，而且路径会多次经过 A ，如果在首次前进到 A 处，测试将 A 替换为路障是否存在环路。如果不存在那么按照原本的巡逻路径继续前进再次到达 A 位置时是否需再次测试？这个情况下是不需要测试的，因为如果进行替换，那么首先到达当前状态的前提就不存在了，替换并不是在前进到某个时刻随意选择替换的，而是在守卫开始走的时候就进行替换的。回到如果 A 存在回路的情况，那么按照原本路径再次到达 A 时同样的也不需要进行测试，因为替换 A 已经验证是存在回路的。

按照这个思路实现的代码结果依旧不对，相比于正解更少的位置在替换后能使得守卫巡逻路径为环路，也就是存在部分环路没有被成功的检测，也许是环路检测部分的代码有问题。考虑边界情况，起始和路径上的其他位置没差别，因为替换的是下一个位置的，路径最后一个位置时，下一个位置不在输入范围内，所以也就不存在两种情况。在写下这段思考之后，仔细研究发现在判断交叉位置的部分是存在错误的，调整之后这个方法毫无问题。

代码在 release 编译下从最初的 8s 到中间的 2s 到现在的 500ms ，代码效率提升明显，但是仍旧不快，因为大量使用了 HashSet ，在火焰图中也可以发现 Hash 的相关操作占据了大部分的运行时，这个部分依旧可以优化。需要哈希的主要数据类型是两个 usize 构成的 tuple 和一个 enum ，理论上的哈希操作并不困难。观察火焰图可以发现存在大量的 rehash ，就是说存在大量哈希重新计算的情况，大概率是 HashSet 的容量增长导致的，所以在新建 HashSet 的时候可以提前分配一个较大的空间，这样操作之后运行时间减少一半，同样的 rehash 在火焰图中也没有多少。当然这样的性能提升依旧有限，因为还是存在大量的 insert 操作，也许可以换第三方的哈希库，但是也许可以用完全不同的方法。

在某一个位置，守卫最多存在四种前进方向，也就是说某一个位置最多存在四种状态，那么就可以用一个三维数组存储这些，直接利用数组替换哈希，测试发现数组比哈希更慢，这也可以理解，因为数组需要更大的空间，哈希其实还是只用了较少的空间。因为输入的大小为 130x130 理论上可以用大小为 [[u64; 43]; 130] 的 array 对应输入二维矩阵每个位置的状态，同样只需要四个这样的 array 对应守卫在每一个位置可能有的四种状态。通过位运算，可以将每个坐标对应到这个 array 中 u64 的一个 bit 上，这也是 AOC 中经常出现的优化。我在今天的题目上已经花了很多的时间，就随它去。

参考了 Reddit 的评论和帖子我意识到在环检测的时候，只需要保存在守卫发生转向时的状态即可，如果成环那么守卫一定会走过每个角落多次，这可以减少需要保存和检查的状态值。这个优化是显著的，在 debug 编译下，运行时间降低到了 300ms ，release 下则降低到了 70ms。

Day 7

也许是最简单的一天，这让我担心明后天的题目了，没有什么特别的花样，老老实实的暴力递归解决，清晰明了，看社区貌似也没更好的方法。有一个 rust 的语法糖（？），可以用 checked_ilog10 确定一个数的十进制长度。

Day 8

题目在描述上有些含糊不清，和前后矛盾，理论上一条直线上的三个点，分别为 A，B 和 C，其中 A 和 C 的距离刚好是 B 和 C 的距离的一半或者一倍，A 和 B 位置确定，那么满足这个条件的点 C 应该有四种可能，题目却说只有两种可能。对这两种可能题目很明确的说是在两点的两侧，也就是说不可能落在两点之间。从这个条件出发，计算 A 和 B 两个方向上的距离差，然后第一部分只要点 A 减去距离差以及点 B 加上距离差即可，第二部分则是不断进行这个延伸，直到超出边界。题目很简单，说实在的也没什么优化的空间。

Day 9 （区间、线段）

一看见题目就知道应该采取怎么样的思路，但是太久没写类似的题目了，所以只有大概的思路，很明显是需要用区间解决的。但是我在决定该如何表达区间上犹豫不决花了太多的时间，所以我决定用暴力法试试看，在计算了需要的数组大小并不是特别大之后，用模拟的方法很容易的就解决了今天的问题，当然运行时间并不好，所以我还是需要用区间的思路解决。输入包含了两类区间，分别是文件和空闲，第一部分需要将文件拆分，填满空闲区间，文件从尾部开始拆分，而空闲空间从头部开始填满。第二部分则是不将文件拆分，需要将整个文件移动到可以容纳的空闲区间。

考虑第二部分，当一个文件移动到一个空闲空间时，首先文件占用的位置设为空，因为是从尾部的文件开始移动，而且一个文件最多只能尝试移动一次，所以位置上在这个文件之后的文件都已经被尝试过了，同时因为文件都是向前移动，所以这个文件移动后留空的部分只需要置空，而无需将其是做可能有文件会移动的空闲空间（空闲但不允许被写入）。然后考虑被占用的空闲空间，首先存在两种情况，一是大小刚刚好，那么这个空闲空间需要被删除，后续其他文件的移动无需考虑，而是大小大于文件的大小，那么就要调整空闲空间的区间值。

考虑第一部分，当一个文件移动后留下的空闲空间依旧是无法作为移动的空闲空间使用。当文件小于空闲空间时，实际上就是第二部分，而当文件大于空闲空间时，则需要拆分文件的区间，优先处理一部分文件，同样的处理过的文件不在移动。实际上对于第一部分，其实用暴力法来的更加方便，因为并不存在文件间的区分，而且从头部开始的空闲空间总是会被填满的，以及尾部的占用空间总是会移动，所以只需要用双指针分别表示最初的空闲空间以及最后的占用空间即可，然后不断的替换两个指针处的空间即可，时间复杂度是 O(N) ，虽然利用区间进行计算，时间复杂度应该也是 O(N) ，但是涉及到文件间的区分，逻辑上就更加复杂了。实际上的运行时也有差距，在第一部分就使用区间涉及到更多的查找操作，或者是移除无用的空闲空间所耗费的开销。

应该能进一步的优化，第二部分中查找符合大小的空闲区间我是直接线性搜索的，应该存在更好的搜索算法，也许可以维护一棵树？Reddit 社区有提到区间树，应该可以更快的找到满足要求的区间，只不过题目比一般的区间树其实存在更多的要求，比如移动后的空闲区间不能再使用（不插入区间树），以及区间要移动到起点较小的区间（需要修改区间树的查询？）。

参考：Interval tree

Day 10

今天的题目很简单，输入处理也很简单，输入也很小，搜索路径。两个部分之间也没什么差别，第一部分需要计算从一个位置能达到多少个目标，第二部分则需要计算从一个位置能有多少路径达到目标。第一部分误读了几次题意，其实就出现了第二部分的解。第一部分可以保存搜索过的路径，减少搜索空间，第二部分则可以保存搜索过的每个位置到目标的路径数，动态规划，减少搜索空间。但是因为输入太小了，所以根本无所谓，递归的深度优先搜索或者迭代的广度优先搜索都可以实现。

Day 11

给定的输入其实很小，处理也相当容易，看完题目其实就知道是存在某种循环、规律，第一部分往往都可以直接模拟解决，经过一次变化，石头数最多翻倍，第一次的变化次数很少，所以在时间、空间复杂度上，简单的模拟是完全可以实现的。

第二部分循环的次数增加的，对于模拟而言次数增加一次，模拟操作是翻倍的，所以时间、空间复杂度是指数增长的，需要寻找某种模式或者更好的算法。对于类似的变化题目，很大程度上都是要寻找某种固定的模式，减少实际需要模拟的次数。简单的检查每次变化后石头的数字，发现第二部分很明显会进入一个循环的状态，所有石头可能的数字并不增加，数字相同的石头不断增加。那么就可以对石头的转换进行缓存，保存每次缓存的结果，当再次遇到一样数字的石头时直接从缓存中取得即可，不需要重复的模拟。同时在计算过程中并不保存所有石头，而是记录每个石头出现的次数，那么就可以很轻易的计算（乘法）出所有这些相同数字的石头经过变换后会变为哪些石头。也许可以进一步分析每一次变化后，相同数字石头数量的变化，确定这个规律后，甚至可以直接取消重复模拟计算。当然这个规律并不容易取得，而且存在石头间的变化，所以单对一个数字进行分析是很难推出规律的，实际的测试也说明这一点。

再阅读了部分社区的解法之后，也有一个类似但不同的思路，类似动态规划，令 f(x, n) 为数字为 x 的石头经过 n 次变化后可能的石头数，那么根据变化规则就可以判断 f(x, n) 为 f(1, n - 1) 或者 f(left(x), n - 1) + f(right(x), n - 1) 或者 f(x * 2024, n) ，同时如果 n 为 0 f(x, 0) = 1，这就是石头变化数量的转换方程。转换过程中只需要缓存即可。某种程度上这两种角度是同一个方法的不同表现，第一种方法减少了每次需要判断的石头数，第二种方法则是减少了转换的次数。

Day 12 （参考 Reddit 解法，计算角的数量以计算边的数量）

应该是连通性的问题，连接区域的面积比较容易计算，可以计算区域中和相邻区域接触的数量即可，用深度搜索实现即可，当前位置的四个方向上存在不是本区域的植物即是边界的一部分，第一部分还是很轻松的，只是要在搜索过程中排除已经搜索过的位置即可。

第二部分需要计算连接面积的边的数量，处在边上的元素最多只和两个相同元素相连，当存在转弯时，搜索到新的边。这个思路没问题，但是实际的实现并不清晰，浪费了很多时间，最后我决定用笨办法，遍历区域中所有的点，确定四个相邻的点有多少是在区域内的，如果四个都在区域内说明这个点不在边上。如果有三个都在区域内，说明这个点在边上，只有一个方向与其他区域相邻，然后我记录这个边的直线以及这个点是在这个边的哪个方向（边的哪个方向是不在区域内的），将边和边的方向作为哈希表的键，以及点作为哈希表的值进行保存。同样的如果只有两个相邻的点在区域内，那么这个点就存在两个边上，同样的写入哈希表。一样的保存只有一个相邻点在区域内时三边和对应方向到哈希表。

参考 Reedit 的解法之后，其实我的第一个思路是没问题的，只不过我没意识到只要确定区域每有一个角就有一个边。~而实际上在我的第二个方法里，我已经计算了角的数量，如果一个位置的四个相邻位置中有四个都在区域内，这个位置一定不是角，如果有三个都在区域内，这个位置也一定不是角，如果有两个在区域内，并且两个位置的垂直和水平方向上的距离都是1，即这两个相邻位置不在一条直线上，那么这个位置一定是一个角，最后如果只有一个相邻位置在区域内，说明这个位置存在两个角（在三个边上）。如果没有相邻位置在区域内，那么就有四个角，其实区域大小为1。~没有意识到角的数量等同于边的数量让我做了不少无用功。

计算区域角的数量并没有我最初所想的那么简单，仅仅通过判断一个位置的四个相邻位置是否在区域内并不行。自己尝试从各种角度解决，但是依旧没能取得正确的答案，没能静心分析，最后参考了 Reddit/Polaric_Spiral 的计算角数量的思路。大致思路如下，在每一个位置，可能有的四个角中，每个角都可能有两种状态，内凹或者外凸的。对于是外凸的角，那么在两个 90 度相邻位置的邻居必然不在区域内，可见示例对于北方和东方的角：

..
#.

对于内凹的角，那么在两个 90 度相邻位置的邻居必然在区域内，同时在这两个位置构成的对角线位置必然不在区域内，例如示例：

#.
##

刚开始我一直以一个位置四周的四个位置落在区域内的数量，作为位置是否在边上的判断条件，考虑形状为十字架的区域，十字架中心的位置实际上也是落在边上的，但是它的相邻四个位置都在区域内。我是直到计算角的数量才发现我在这个边界情况上的错误判断，对于我自己的方法，这个错误并不影响计算，因为既然是十字架形状，那么四个方向上除了中心位置肯定还有其他位置落在同一个边上，那么没有这个点也不影响边数量的计算。但是在计算角的数量的时候就要考虑到这一点，因为如果只计算边上的位置存在角的数量时，少掉一个位置肯定会影响结果。这个误判也不只出现在十字架的形状中，对于大部分内凹的角的位置，其实都会收到这个误判的影响，例如下例中 (1, 1) 处其实存在一个内凹的角，这个位置也落在边上，同时四个相邻的位置都在区域内。

AA.
AAA
AAA

今天的题目依旧不难，至少在时间、空间复杂度上不是偏难的题目，需要用的算法也很常见，但是在细节的处理上需要很好的分析。对于多边形边的数量等于角的数量这一知识点没能第一时间意识到，还有就是自己下了一些错误的决定，比如判断点是否在边上。这类题目其实就是考察边界情况，以及耐心。

Day 13 （线性代数）

今天的题目和让人措手不及，总感觉应该是需要用到算法了吧，题目的描述又好像存在某种最优解，某种最优的抓取方式使得最后的耗费最少。带着这种偏见，我就用动态规划解决第一部分，令 m(p) 为到达奖品 p 处的最少耗费，那么就有如下转移方程 m(p) = min{3 + m(p - 1), 1 + m(p - b)}，其中 a 和 b 为按钮 a 和 b 移动的距离，同时还有边界条件 m((0, 0)) = 0 。根据这个就可以实现递归的方式从上往下依次计算，期间保存 m(p) 可以减少中间的计算过程，当然运行时间并并不好，因为还是有很多无用功。

第二部分把求解空间瞬间放大，再用动态规划就不现实了，花了我好一会才意识到这个题目根本不需要动态规划，有一个很重要的提示是题目不断地说起某些机器永远无法到达奖品位置，一般来说对于动态规划的问题，往往是存在多解，比如最短路径，往往是需要从中选择最优，有两个关键词很重要，就是多解和最优。因为最优把我引导到了动态规划，但是我却没有思考一下究竟是不是存在多解，是不是真的有所谓最优的情况。

动态规划里很常见的题目就是青蛙跳的题目了，一次跳一步还是两步计算最少的跳跃次数，在这个常见的问题里，求解空间是一维的，也就是说其实是一个二元一次方程，这样的话是存在多个解的，动态规划也就适用了。

而这个题目，抓取爪是在两个方向上移动，同时每个按钮也是控制抓取爪在两个方向上移动一定距离，同时奖品位于二维空间的特定位置，而且只有当抓取爪恰好处于所需要的位置时才能抓取成功，所以需要同时在两个方向上到达奖品位置，那么就构成了两个个二元一次方程组，其中参数和元都要是整数。只要计算这个方程组的解即可，而对于两个二元一次方程，是存在唯一解的，同时题目涉及到的解又只可能是整数，所以只要解方程就好了，用消参法可以很容易的计算唯一解，只要判断是不是整数即可。对于这个问题，其实根本不存在什么最优解，因为就一个解，对于算法的适用场景，还是要更仔细的分析才行，不要轻易被部分关键词所误导。

Day 14

今天的题目依旧有些出其不意，第一部分简单的模拟即可，当然不需要构建地图进行一步一步的模拟，直接更新机器人的坐标即可，不过要注意当机器人移动到边界时会瞬移，也就是可能会溢出边界，需要对坐标进行求余操作，rust 中 % 的运算符会保留符号，取得的结果并不靠向 0 ，所以需要用 rem_euclid 计算非负的余数才行。

第二题其实很让人困惑，即没给出大概范围，又没给出需要搜索的形状，只是很模糊的表示大部分机器人可能会构成一个圣诞树的图片，那就只能自己找规律了。我先在每一次移动之后都打印出机器人的现有位置，自然的这样有大量的干扰输出，保存输出的文件不一会就超过 1G ，然后观察输出可以发现其中部分输出机器人会大部分的位于几行或者几列。最初我想是不是应该统计在集中出现几行和几列的频率，然后当同时出现在几列和几行的时候，就是结果，但是对我来说这个思路有点麻烦，因为既要检测形状，又要检测环。然后我就想到，如果大部分的机器人都构成一个图片，那这些机器人之间的距离应该是较小的，于是在每一次移动之后我都计算每对机器人间的距离，如果距离小于之前记录的最小距离，说明这个时候可能是构成了圣诞树。用这个方法很容易的过滤了大量的输出，同时也可以很容易的从中发现的确有正解。取得正解之后，为了避免程序不断循环，我增加了最小距离更新的时间间隔上限，如果超过这个上限最小距离还没更新，就退出程序，当然这是事后之明，这个方法其实也是有些运气的，如果作者夹杂了其他的不是圣诞树的图片，那么就可能会有错误的解，但是这类题目本身就有点像脑筋急转弯，严谨并不是最重要的部分，这类题目的有趣也就在此。

Reddit 上除了我这样的方法还有其他一些方法，都各有创意，也各有运气。就我个人而言这类题目最有趣，略微脱离某种严谨的编程，我还记得几年前有个题目最好的方法是折纸盒，这类问题阅读大家的方法也很有启发。

将输出存为 PNG 格式，然后检查文件大小较小的输出，因为有规律的图片压缩更加优秀
计算连接机器人的数量，当数量超过一个人为给定的阈值之后，可能就是正解
检查位置重叠机器人的数量，当没有机器人重叠的时候，即为正解
我的第一思路，计算大部分集中在行和列的频率，计算相交也是可行的
也许可以检查四个象限接触部分机器人的数量，因为最后结果圣诞树大致处于图片中间的位置。

参考：rem_euclid

Day 15

今天的题目有点麻烦，第一部分其实还好，利用递归检查移动方向上下一个位置是否可以通行，存在如下三种可能：

当下个位置空闲时可直接交换前后两个位置。
当下个位置为墙壁时说明机器人无法移动。
当下个位置为箱子，而且这个箱子通过递归判断最终是可移动的，那就交换当前位置和下一个位置。

在这个递归中，总是在遇到空闲位置时开始交换位置，也就是说空闲位置不断的向最初位置进行交换，同时有且仅有递归搜索最后存在空闲位置才进行交换。

第二部分复杂了一点，地图被拉伸了，一个箱子本来只占据一个位置，现在箱子占据了左右两个位置（高度不变，宽度翻倍），但是机器人的大小不变。那么当机器人遇到箱子后，就存在多种情况。如果机器人的运动方向是向左或向右，那么机器人推动箱子的逻辑和之前其实是一致的，机器人推动一个箱子，然后箱子可能继续推动同一个方向上的箱子，依次类推直到遇到一个空闲位置。复杂的情况就是当机器人的运动方向为向上或向下，当机器人推动箱子时，因为箱子的宽度增加变成 2 了，那么一个箱子在运动方向上可能就会推着两个箱子，依次类推机器人最终推动的箱子可能是像一棵树一样，只有每一层的多个箱子都能被推动机器人才能移动。这个箱子树之间是存在依赖关系的，考虑机器人推动一个箱子 a ，而箱子 a 推动了两个箱子 b 和 c ，假设箱子 b 能被推动，但在确认箱子 c 能否被推动之前，是不应该推动箱子 b 的，反之亦然。也就是说对于第二部分简单的搜索回溯并不行，因为搜索的分支会决定是否需要回溯。

基于这个认识，我写出了解决方案，但是我的方法很丑陋，大致是进行了 2 次搜索，第一次确定机器人是否能够移动，如果机器人能够移动，第二次则移动箱子。这个思路虽然不是最优雅的，但却是没错的，结果我浪费了很多的时间在这个方法上，因为确定思路没错，所以不断的尝试取得正确答案，最后发现是在分支的判断上存在问题，导致部分情况没考虑到，而这些情况只存在复杂的情况中，对于给出的示例根本就不会遇到这些情况。

更好的思路是只进行一次搜索，在判断机器人能否移动的搜索中记录所有可能被推动的箱子，如果机器人能移动，那么最后只要循环推动这些记录的箱子即可。即便得到了所有可能需要移动的箱子，依然有一个问题没有解决，那就是推箱子的顺序问题，箱子移动留下的空间要么置空，要么被其他需要移动的箱子占用，那么就存在一个移动顺序，如果不按照移动的先后顺序修改地图，就有可能导致置空被写入，或者本需要的空间被置空。但是可以首先将所有需要移动的箱子占用空间置为空闲，再一次性的将所有箱子移动后需要的空间写入箱子，这样可以直接规避写入顺序的问题。对一个箱子而言，移动前的位置须要被置空，新的位置的箱子需要移动，所以不妨先都置空，再一次性重新写入箱子。移动并不导致箱子增加或减少，这样也避免由于移动顺序导致的箱子重叠问题。

上面这个思路没问题，但是应该还存在优化空间，我其实将机器人推动箱子和箱子推动箱子分开看了，但是理论上我可以将这二者归纳起来，箱子推箱子几乎就是两个机器人推箱子，这样应该能实现一定程度的优化。参考：SuperSmurfen

自己实现了这个方法，这个方法有一个弊端，如果将所有移动都视为机器人移动，那么在判断箱子能否移动的时候就需要根据情况检查两个可能位置的情况。假如一个箱子的正上方刚好是另一个箱子，那么在判断当前箱子的两个部分时就会分别判断对应上方整个箱子空间是否适适用，会涉及较多的重复判断，所以需要引入哈希表记录当前位置是否正在判断，而这会增加运行耗时。

Day 16 （重新学习 Dijkstra ）

今天终于遇到了我不会的题目了，题目其实很简单，就是最短路径，但是我并不熟悉相关的算法，尝试用 DFS 解决的时候，发现自己在很多细节上并不是最短路径的解决方法，我不断的在类似的题目上犯这个错误。然后用 BFS 解决的时候才理清了思路，但是无论是 BFS 还是 DFS 其实都会耗费大量的时间，因为在我的 BFS 和 DFS 方法中并没有实现什么缓存，也就是说我在搜索过程中不断的进行重复计算。

可以从题目中取得转移方程，令 m(c, f) 为坐标 c 和方向 f 到目标位置的最小分数，那么就有 m(c, f) = min{m(c-1, f) + 1, m(c, clockwise(f) + 1000, counterclockwise(f) + 1000} ，转移方程很明确，如果采用动态规划就能减少计算量，自顶向下要从初始点开始搜索，自底向上则要从目标位置开始，，无论是自顶向下还是自底向上其实都要穷尽可能性，否则将会出现我一直反的错误，即缺失了部分路径。

最后自己绞尽脑汁依旧没想到该怎么实现，当然我是知道 Dijkstra 的最短路径算法是可以的，可是我并没有掌握这个算法，于是最后选择查看了相关的 wiki 页面，阅读了伪代码，然后自己实现了，在细节上因为对算法的理解不够，所以过程也不是一帆风顺，好在最后完成了第一部分。

第二部分实际上则是要取得所有的最短路径，应该也可以用 Dijkstra 算法解决。通过在过程中每当从起始节点到当前位置节点减少或不变时，记录当前位置的前置节点，并及时根据新的最短距离更新当前节点的前置节点集合，用 HashMap 进行表示，其中键为当前节点，而值为一直的最短距离和这个最短距离时已经发现的前置节点集合，当距离不变时将新的前置节点加入集合，当距离变小时，清空集合，同时将前置节点加入集合。在阅读了 wiki 中关于这个部分的内然后，wiki 中没有提到需要根据距离大小维护前置节点集合，我自己测试之后发现即使不清空集合，在这个问题中最后的解是不变的，也许这只是这个问题涉及的图比较特殊。在逻辑上，每次有新的节点进入优先队列时，实际上只是表示找到了这个节点目前的最短路径，而不是最终的最短路径，如果不维护前置节点集合，那么就可能最终的最短路径的节点中，前置节点集合包含非最优的情况，按照我的理解就会存在错误的路径分支才对。

再阅读了不少的解之后，我意识到 Dijkstra 实际上是特殊的 BFS ，一般来说 BFS 是采用先进先出的队列进行搜索，Dijkstra 则是采用优先队列，除去队列的不同，其他方面的差别很小。优先队列是为了将当前已知最短距离较小的节点优先进行搜索，采用优先队列的同时，记录在某一个节点前，起始节点到所有节点的已知最好距离，如果当前优先队列弹出节点的邻居节点的距离已经大于所记录的已知最小距离，那么当前节点的状态所在的路径一定不是最短路径，就不需要进行搜索了。有点类似在普通 DFS 或 BFS 中的剪枝，但是使用优先队列可以最大限度地剪枝，因为总是从较小的路径开始搜索，逐渐增加距离的过程。

今天的题目相比于一般的深度搜索或广度搜素，复杂的地方在于移动是存在方向限制的，而且方向存在着权重，所以一个位置上以某一种方向运动的麋鹿存在三个可能的走向，一个位置的麋鹿最多可能有四种方向，所以一个位置有个状态，四个节点。

阅读了部分社区的解之后，DFS 和 BFS 其实也是可行的，只不过需要将平时法访问表改变一下，一般来说访问表一般是检查/搜索过的集合，当再次遇到相同状态就跳过，但在最短路径的算法中这个方法不可行，因为可能会跳过较优解，所以需要将访问表设为该状态目前的最短距离，如果再次遇到时距离大于访问表中的最短距离，就可以跳过搜索。通过剪枝是可以实现的，这个方法在第一部分可以在 10s 内运行完成，如果我刚开始在细节处理上没错，估计就会这样结束了。没必要纠结这个方法，因为这个方法本就不高效，好像每次自己都会在这个方法失败后纠结，反而没怎么深究 Dijkstra 或者其他的最短路径算法，不能老是踩一个坑。

即使用了 Dijkstra 我发现我的方法依旧不算快，然后通过火焰图发现我犯了一个很严重的错误，极其不应该的错误，Dijkstra 算法最后会取得其实状态到所有状态的最短距离，因为题目最后需要求的状态可能有好几个（不同方向进入目标位置），我的错误就在如何从所有最短距离中找到我需要的状态。我用目标位置的坐标去匹配所有节点的坐标，然后筛选出需要的最短距离。正确的方法，应该是直接构造目标位置可能的四种状态，直接用哈希表的查找即可。相当于 O(1) 能完成的操作，我用了 O(N) 的操作完成。

今天的题目在转弯的情况和直行的情况时，权重差别很大，所以其实无论在哪一条最短路径中，转弯的数量总是一定的，所以也可以在第二部分采用普通的 BFS ，检查转弯的数量。也可以直接 BFS 计算每条路径的长度，如果等于第一部分的答案就说明找到了一条可行路径。今天就这样吧，思路不清晰，算法也不熟悉，下次遇到不熟悉的算法，但是知道该用什么算法，不妨直接参考算法，靠自己苦思没什么价值。

参考：Dijkstra's algorithm

Day 17

今天的题目也是常见的题目，模拟 CPU 寻址执行，第一部分只要老老实实进行模拟就好。第二部分则让我绞尽脑汁，最后自己也没能解决，我首先根据提议将给定的输入程序转为伪代码，存在 3 个寄存器，但是经过转换后，可以确定从寄存器 A 直接得到输出的公式，需要确定寄存器 A 的初始值以得到满足题意的输出，如果暴力循环测试，对于我的输入，求解空间大小是 2^47 。往年这类题目的输入程序，往往没有这么容易就被化简，今年反而更容易化简，结果却无法轻易根据化简的结果取得想要的答案。

鉴于在尝试几小时后也没有很好的思路，我决定直接去 Reddit 寻找思路。参考1 ：jlhawn，根据我的分析，可以确定 A 初始值的每 3 位(二进制)，对应每一个输出，根据这个提示，需要做的就是从 A 的最左侧 6 位和最后两个个输出进行判断。对我的输入程序的化简，可以得到每一个输出为 a & 0b111 ^ 0b101 ^ (a >> (a & 0b111 ^ 1)) & 0b111，同时当每一次输出后都需要对 a 进行右移三位，直到 a 为 0 ，然后程序退出。根据这个化简，可以得出每一个的输出和 a 是有直接关联的，如果这个公式中不存在 a 的右移，那么输出甚至只和 a 的最第三位有关，但是因为其中涉及到 a 的右移操作，所以并没有这么简单。每一个输出之后，a 的最左侧三位总是被丢弃，然后 a 右移三位，根据这一点可以从最后一位输出开始分析。

对每一个程序的输出，a 其中至少有 3 位和这个输出关联。如果有 16 个输出，那么寄存器 A 至少有 48 位长，对其中每 3 位，都有 8 种可能，可以对输出进行反向搜索，即先确定 a 的高位，根据化简的公式，可以发现当前的输出除了对应的三位，还和 a 更左侧的部分有关（公式中存在移位的部分），那么如果确定了a 左侧的部分，就能更容易的测试当前对应的三位，通过反向搜索正可以达到这个目的。在确定输出的最后一位，即确定 a 的最高三位时，a 不存在更左侧的部分，理论上可能对最后一个输出可能存在不止 8 个可能，但是对于我的输入和示例的输入，则最多只有 8 种可能，即存在大于等于 0 和小于 8 的 a 使得程序的输出为 0 。

在确定了 a 的最高 3 位之后，只需确定接下来的三位，对应输入程序中的倒数第二个，只需要将已经确定的 a 左移三位（对应输入程序中对 a 的右移三位），然后继续在这个基础上，再在 0..8 中搜索可能的 3 位，逐渐的递归搜索，直到搜索到输入程序中的第一个。也许可能存在多个 a 满足条件，但是因为要求的是最小的 a ，同时又因为这个方法是反向搜索，所以第一个满足条件的 a 一定就是最小的。

本来以为我的方法会是只针对我的输入的，但经过测试，实际上给出的示例也是能够通过的，只要在搜索过程中使用第一部分的模拟方法取得输出，而不是用针对我的输入进行化简的公式计算输出即可，实现中也分成了两个部分，一个部分只支持我的输入，一个部分则是支持所有输入（题目给定的输入，随意的程序肯定是不行的）。

今天的题目不是那种往常的题目，方法其实很大程度取决于输入的程序，就好像编译器中对编译的优化，某种优化能不能实现很大程序取决于编译的程序，这类题目也很有趣，并不想 leetcode 之类的题目，不过也更加开放，需要动脑筋，只会算法并没有什么特别的帮助。自己的思路其实没有问题，但是在最后临门一脚上自己却思虑不够，我都能化简输入的程序，其实也已经发现了大致的规律，就是没意思的我应该反向搜索构造 a 。Reddit 社区上很多人都是测试程序运行输出，发现输出和 a 中的 3 位有关系，进而解决问题。如果把发现寄存器 A 和输出的关联规律算作第一部分的话，我是很完美的达成了这部分的。但是对于用深度搜索进行反向构造 a 的部分，我却没能很好解决。

社区上还有其他的一些方法，例如：1. 确定结果的大致区间，发现输入和输出的大致规律后，直接暴力测试。2. 在化简程序后，用 Z3 之类的外部依赖解决方程。

Day 18

今天的题目我感觉比前两天更简单，至少实现一个能解决题目的方法并不困难。题目虽然在开始说会每隔一纳秒掉下一块记忆，也就是每隔一纳秒地图会被阻塞一块，但是第一部分题目求的是当给定块记忆掉下后，从左上角到右下角的最短距离，最短距离而且每个方向上的权重都是一样的，那么简单的用 BFS 搜索即可，队列配合记录搜索过的位置即可实现。

本以为第二部分终于会用到题目中关于每一纳秒地图就会被堵塞的说明，结果也可以不用，第二部分只要判断在第几个记忆下落后从头开始前进，会无法到达右下角的位置。我先直接套用了第一个方法，遍历计算在 N 个记忆下落后的最短路径，当无法达到时，前一个结果既是正确答案。这个实现虽然慢，但是也很快的跑出结果了，因为搜索空间并不大。然后我意识到根本不需要计算最短路径，直接用 DFS 深度优先搜索路径即可，这个方法可以将运行时减半。

然后如果从尾部开始搜索更好，假设最初所有记忆都落下，那么只要从尾部移除记忆，然后进行路径搜索即可，如果联通那么可能路径很多，而且为了确认是联通的一般都要走到最后，但是如果被阻断了，那么搜索往往会提前结束。如果所有记忆中存在一块记忆使得路径被阻断，那么在这块记忆落下之后，其他记忆落下也不会使得路径开放。逆向测试搜索必然能找到最早使得路径被阻断的记忆，这个记忆的前一个记忆既是正确答案。同样的逆序搜索也可以不需要每次增加记忆块，而可以每次移除记忆块，根据实现的不同这也可能是有点。还有逆序搜索的时候，即使用广度优先搜索最短路径的算法效率也不必深度优先搜搜差，因为大部分的搜索都是不通的，往往搜索都会提早结束，这个情况下深度优先还是广度优先就差别不大了。

第二部分也可以用二分查找进一步减少搜索空间，Reedit 社区上很多人都用的这个方法，实现之后发现的确效率有提升，30ms 减少到 20ms 提升还是明显的。在社区上我还注意到了一个特别的地方，那就是其实不需要额外引入访问表，只需要把访问过的地方视作被阻塞的位置即可，这可以省去部分操作开销，现在我记起来这个操作的确是很常见的，在我的实现里这么做会有一点点冲突，当然在这个问题里也不是很有必要，总之这也是一个可能的优化点。简单的一天，Good.

Day 19

今天的题目很轻松，第一部分是深度优先搜索，搜索到符合条件的模式即可，第二部分则需要计算所有可能的匹配模式，为了减少重复计算量，第二部分只需要加上缓存记录中间搜索状态即可，第二部分就是记忆化搜索。我为了快速得出答案，还采用了很直接的输入处理模式，我把输入都转为 bytes 的数组，搜索都是基于数组进行搜索，这个开销并不小，实际上可以直接使用字符串进行搜索，甚至可以进一步直接将字符串转为数字，不过这个不见得会比字符串要好。使用字符串直接进行处理的时候，在中间搜索过程就可以使用字符串的方法，比如匹配前缀，这些方法应该也能提升运行效率，虽然实际上 rust 的 Slice 也有 start_with 直接判断前缀，同时查看源代码可以发现，其实也是简单的判断长度是否合适，然后简单比较，所以在这个实现上并没有效率提升，实际上我不需要使用 String 直接使用 Vec 也是没问题的，只不过在中间搜索过程中使用 Slice 就行。

在进一步阅读了部分社区的讨论之后，今天的题目也可以直接用正则表达式解决，第一题其实就是很简单的正则搜索，第二题则有的正则引擎能够直接实现，参考： [2024 Day 19] Alternative solutions

Day 20 (Dijkstra)

今天的题目对我而言难度不小，还是 2D 最短路线搜索，只不过多了一个条件，那就是在搜索过程中地图会发生变化，部分位置会变为可通行。第一部分在每次搜索中最多只有一个位置可以发生改变，在第二部分中则最多可以有 19 个相连的本不可以通行的位置发生改变，需要计算的就是有多少种位置发生改变的情况，可以使最短距离减少到题目所要求的距离。

第一部分我先列出所有可能的位置变化情况，然后依次进行广度优先搜索确定最短路径，然后筛选出正确的结果，运行效率并不好，但是也取得了正确结果。对于第二部分好像就不能这么简单的实现了，题目中提及的作弊，其实就是给两个节点之间增加新的边，也许可以先确定满足题意要求的边有多少。第二部分的搜索空间大到连两个节点间有多少可能的边都无法计算。

对我而言题意不是很明晰，相比于最初的思路，我意识到可以计算出所有作弊的可能和对应的作弊所需要的时间（距离），然后利用 Dijkstra 算法，计算出起点到每个作弊开始的最短距离，然后用同样的方法计算出终点到每个作弊结束的最短距离，那么对于任意中作弊就可以很容易的计算出最短距离。这个方法可以做到有结果输出，而且对于给出的示例是能取得正确答案的，但是对于实际的输入却不对。题意对我而言模糊的点有好几个：

作弊中是否遇到可行驶的位置就停止作弊。实际测试中发现如果遇到可行驶的位置就停止，示例的结果会比示例给出的正确答案少很多，同时实际输入的答案也不正确。
作弊是否需要遇到墙壁才能启动，根据测试这个条件也是不必要的。
作弊过程中遇到终点是否结束作弊？我很明确的记得刚开始的题目要求中是有这一点的，但是刚刚测试了没有这个要求的答案，居然过了。

根据这三个前提，我得到了正确答案，但是我的方法很慢，因为我计算作弊的路径时用了 Dijkstra 算法，但是根本不需要这么复杂，只需要计算两个空闲位置的曼哈顿距离即可。

在阅读 Reddit 的讨论中我也意识到题目给出的路径其实只有一条，所以根本就不需要用 Dijkstra 算法。使用 rayon 可以快速的实现迭代器的并行，不过并不是对所有的场景都有提升，在某些场景可能并行本身的开销就要大于实际操作的开销，在我的使用中大致可以实现运行效率翻2-3倍。

今天算是被题目描述坑了，根据最新的描述，其实大概率我可以提早完成，还有今天的题目并不是路径搜索，不过我自己的实现也算是对 BFS 和 Dijkstra 的进一步练习了。

Day 21 （参考 Reddit 题解，善用记忆化搜索）

今天的题目有点链式搜索的意思，还是路径搜索，总共有好几层的搜索，需要求最后的最短路径，我不是很喜欢这个题目，有点让人心烦。我用 BFS 能求出某个层级的最短路径，但是这个路径传递到下一层时，对这个路径进行再次搜索的时候，又不见的就能取得最短的路径了。

我感觉我应该实现多层级的对应，直接确认当最外层的我按下按钮时，最内层的按钮是如何被按下的。实现多层级的映射以及直接搜索后，第一部分顺利通过。第二部分则没有这么轻松了，因为求解空间被放大了，而且增长是指数级的，每增加一个机器人分支的数量就指数增长，第一部分的方法就不再现实了。无论是逐层的求解最短路径，还是我的映射求解，这个问题都很严重吧，如果能保证每层搜索得到的最短路径都能确保下一层依照这个路径进行搜索也能得到最短路径，那么也许逐层的方法能够减少大量的求解空间，但就是这点困住了我，再想想吧。初步预估，按照第一部分的方法，大致需要 5^25 s ，不知道有没有超过宇宙的寿命。第一部分方法的时间复杂度是 O(N^5) ，N 是机器人的数量。

一些观察：

对于数字输入，例如 029A ，长度为 4 ，那么外层的方向键盘输入，至少存在 4 个 A，对于数字 0 ，机器人的机械臂从数字键盘的 A 位置（初始位置），移动到 0 位置，然后外层机器人按下控制这个机器人的方向键盘上的 A 按键。假设每次输入 A 最少需要移动机械臂 N 次，N应该是介于 0 到 3 之间的数，假设平均为 2 ，那么最后的路径长度大致是 4 * 2^26 ，仅仅是某一条路径，也许都改变走不完。
对于方向键盘而言，从一个位置到另一个位置最多需要移动 3 次。
我发现当数字键盘输入某个特定的值时，所有机器人的机械臂都处于相同的位置，所有外层机器人的机械臂都在 A 处。
对于单个键盘而言，从一个位置到另一个位置，是存在某种较优的情况的，比如对于数字键盘而言，从 5 走到 A ，如果方向是向右或向下，这些路径一定大于向上或者向左。同时即使走了并不是曼哈顿距离的路线，对于最外层而言，依旧会有子集是曼哈顿距离的路线，5 走到 A ，在不存在穿越边界的情况下，总是需要向下和向右的。不难发现，对于再外层而言，曼哈顿距离的路线一定是较优解。
第 4 点里提及的较优路线，这些较优路线很大程度上会体现在外层的路线上，内层每少按一个按钮，外层机器人移动机械臂到 A 的次数就少一次。也就是说对于某一层的最短路线，它内一层的路线，一定是那一层最短路线中的一个。

有点像多维的情况，有点难理解，需要很强的想象力，我总感觉存在一个地方能进行缓存。如果采用我的映射方法，那么每次的状态包括，所有机器人机械臂的坐标，同时也包括剩余的数字输入。根据第 5 点，也许能实现一个可行的方法，需要计算每一层的所有最短路径，再在这个基础上搜索其中的最短路径。

对于普通的 Dijkstra 算法而言，节点是位置的坐标，对于这个题目，节点是什么呢，如果同样是机器人机械臂的坐标，那么最后的图将是有环的，而且满足条件的路径是有要求的，也许这个题目改变就不是最短路径的题目。

对于任意的序列，例如数字键盘上从 5 走到 A ，这个的最短距离其实就是曼哈顿距离，其中存在几种不同的路线，但是路线中包含的移动策略类型是一样的，即至少需要向下走两次，然后向右走一次，对于外层而言，实际上就是要确定向下走两次和向右走一次以怎么样的方式排列能实现最少的移动。对于方向键盘，实际上也就是不断的递归计算，而对于数量众多的方向键盘，其实它们的规律都是一致的，所以可以很容易的计算出所有组合的规律。依照这个思路，也就可以用动态规划进行完成。

对每种键盘构造最短距离表，二维数组表示从一个键位到另一个键位所需要的最短距离，每个元素表示这个最短距离所需要的向上，向下，向左和向右移动分别需要的次数。直接用排列的方法取得所有可能的最短路径并不行，因为键盘上存在空白的位置，这会引入错误的路径，这就导致原本可以一个方向走到底，然后再转弯的情况，必须要提前转弯。

根据这个情况，可以发现，最短的路径应该是转弯最少的路径，如果机器人要不断的往一个方向移动，那么控制这个机器人的机器人只需要不断的将机械臂指向那个方向，同时再外层的机器人只要按 A 即可。即使我通过搜索完全确定从一个位置到另一个位置的所有最短距离修复了这个问题，根据之前预估的分支数量，求解空间依旧巨大。

如何直接确定最短路径中哪一条最可能获得最后的最短路径呢？是转向最小的路径吗？这个方法还是不对，搜索空间被排除的太多了，而且即使是这个方法在第二部分的运行效率依旧不高，也许可以加上缓存，记录所有方向键的序列对应的最短路径，但是我不觉得能有什么帮助，是时候去社区获取一点提示了。阅读了一个题解，大部分的提示都和我的观察不谋而合，只不过加上了缓存，缓存是同当前键盘的深度以及机械臂所在的位置相关连的，对某一层次的机器人而言，当使得数字键盘从一个按键移动到另一个按键时，这层的机器人总是从 A 开始到 A 结束。

总是在关键的地方就放弃了，我以为缓存不会巨大的求解空间有什么效果，结果事实证明我完全错误，当然我最初的缓存设想也不正确，缓存记录的是在某一层的机器人，从一个按键移动到另一个按键时直到最外层的最短移动距离。对于某一层的机器人而言，从特定的一个按键移动到另一个特定的按键，这层之外的其他机器人都是从 A 开始移动，并以 A 结束，于是对于相同的按键序列，总是能够得到相同的最完成最短距离。

在上面我实验了直接用排列构造下一层可能的最短距离，以及只选择转弯最少的方案的最短距离进行测试，要不是因为没有排除实际上不可行的路径，要不是把过多可行的路径删除，实际上我只需要对所有可能的最短路径进行移动测试即可，进行测试就能保证路径可行且是最短的，我需要更加耐心才行。这两种方法实际都可行，而且直接全排列构造可能的最短距更加快，实际上两个按键间的距离必然不可能太大，再加上可能有的全排列优化。

参考：ndunnett

Day 22

今天的题目很好理解，也没什么特别难的，第一部分就是简单的数学运算，第二部分实际上还是数学运算。第二部分需要计算某个价格变化的序列，使得每个买家在首次遇到序列时出价，最终能得到最高的价格。我直接对每个买家的 2000 个序列计算价格，和价格变化，然后将所有长度为 4 的价格变化序列作为哈希表的键，以及首次遇到时对应的价格作为哈希表的值。在对所有买家都取得了价格变化序列对应价格的哈希表后，遍历所有可能的序列取得每个买家首次遇到这个序列时的出价，再计算所有买家对这个价格变化序列的总出价，最后只需要计算其中的最大值即可。这个方法可以在 10s 内获得正确答案，也可以进一步优化，直接在建立哈希表的时候，就计算对应序列对所有买家的初次遇到时的出价总和，最后只要对这个哈希表计算值最大即可，这样优化之后程序的运行时间是 200ms 内。还有进一步的优化吗？

一些观察：

价格变化的值的范围在 -9 到 9 ，对于长度为 4 的价格变化序列，总共存在 20 * 20 * 20 * 20 种可能。
遍历所有的价格变化序列是程序中最需要计算的部分，对于每个卖家总共存在 2000 个价格变化序列，每次遍历都需要检查对于这个卖家这个变化序列是否出现过，还可能修改价格变化序列对应总价的哈希表。

将长度为 4 的价格变化序列对应为一个数字，这可以降低在检查序列是否出现时用 HashSet 的操作成本。参考 semi_225599 的题解，我意识到在构造计算序列变化的出价总和时，只需要价格变化的序列反向进行计算即可，这样可以不需要检查是否出现过，逆序计算可以确保最终在哈希表中的价格是序列最早出现时的价格，不过这个优化不是很适用我的实现。

发现一个诡异的情况，那就是测试运行的速度居然比二进制运行的快，特别是在 release 模式下，破案了，运行的命令错了，加了一个错误的空格，鬼知道从几天前开始就这样了。

在将价格变化序列对应为一个数字，同时用数组记录序列对应的价格，以及序列出现的情况后，运行时间在 debug 下在 500ms 左右，而在 release 下则在 50ms 左右，这个优化还是很明显的，这才对嘛，难怪这两天总感觉自己做的优化效果不明显，原来是命令错了。

Day 23 （第一次知道的算法 Bron-Kerbosch）

第二部分需要找到一个 LAN party ，其中每个成员都与其他成员互相连接。假设电脑 A 为满足要求中的一台电脑，令与电脑 A 互相连接的所有电脑为集合 Sa ，那么 Sa + {A} 既是所求 LAN party 的所有电脑，同时 Sa 中的一台电脑 B 对应的互相连接的集合 Sb ，就存在 Sa 和 Sb 的互相相对补集只有电脑 A 和 B 。这个思路并不对，因为并不是 Sa 中的所有电脑都要满足这个条件，最终的 LAN party 可能只是 A 和 Sa 的子集。

如果不从集合的角度入手，从图的角度呢？~应该不是图的题目，并不涉及间接相连，只考虑直接相连的情况。~集合和图密切相关的，只不过我的认知不足罢了。直接试试看暴力法吧，思路不是很清晰，也许暴力法能够给我一些提示。暴力法能够给出示例的正确答案，但是对于实际的输入就太慢了，因为可能的组合数太大了，而且每次检查的花费也不少。

我意识到暴力搜索所有可能的结果并不现实，但是可以对每台电脑进行逐一的暴力搜索。假如 A 在满足条件的 LAN party 中，那么 {A} + Sa 一定是最终 LAN party 所有电脑集合的超集，那只需要对 {A} + Sa 的所有元素进行组合搜索即可，搜索从最大的可能开始，到长度为 2 的最小的满足要求的集合，这样可以直接搜到 A 所在的满足条件的 LAN party 的最大集合。依次对所有电脑进行搜索，确定其中满足条件的最大集合即可。这样的实现，在 release 下运行的还是比较快的，30 ms 左右完成运行。这个方法得益于最初的观察和暴力法的测试，二者缺少一个都可能没法这么快的想到这个方法。

这个方法其实和我最初的设想一致，怎么根据集合的要求，从 Sa 中排除不满足要求的电脑，但最初的思路是从底向上，也就是慢慢的确定集合的成员。最后的方法则是反向的从顶向下，逐渐移除 Sa 中的电脑，检查移除后的集合是否满足要求。自顶向下我用了 Itertools 的方法实现组合，最初的思路其实也可以这样操作，但是我没能很好的意识到这一点，我想一步一步构造正确的答案，而被其中可能的复杂所绕晕了。因为一台电脑所直接连接其它电脑的数量并不多，所以可以直接构造所有的可能，然后进行逆序搜索，这样的方法就能快速得出答案。

社区的题解也有好几种思路，比较多的就是直接从图的思路入手，其中有直接使用第三方能够解决这个问题的库，还有的则是实现了对应的算法，因为这个问题是已经被明确定义的问题，中文应该是最大团/最大聚类，初步来看，其实就是我的最初思路，从一台电脑组建构建出可能的最大集合。

在对输入的处理上，刚开始纠结了好一会，因为不确定是不是用数字索引代表电脑更好，最后还是引入了索引表，但在这个问题中并不需要。

Bron-Kerbosch算法

阅读 Bron–Kerbosch algorithm 以及其他的一些资料后，我可以照抄的实现算法，大致的思路我也知道了，描述如下：

是一个递归加回溯的算法
对于某一个最大团 R ，R 为最大团的集合（所有元素互相连接）。
存在一个集合 P ，P 中的元素可能会被加入到 R 中。
存在一个集合 X ，X 的作用我并不是很理解，大致的作用是去重，在搜索最大团的过程中，如果不重复，X 总是为空。X 中的元素的最大团都已经被搜索过了。
初始时 R 为空集，同时 P 为所有节点，X 为空集。
每次搜索时，都循环遍历 P 中的边（元素） v ，这时产生分支。
将 R ⋃ {v} 作为新的 R 进行递归搜索。
1. 对于这个集合而言，对应的 P 就是 P 和 v 邻居的交集，只有同时在 P 中，又是 v 的邻居，才可能加入到新的最大集中。
2. 同样的对应的 X 就是 X 和 v 邻居的交集，如果结果不为空说明目前的这个最大团，是某一个最大团的一部分。
回溯：当递归搜索完成后，将 v 从 P 中移除，同时将 v 加入 X
1. 从 P 中移除是在搜索其他最大团时避免再搜索到 v
2. 把 v 加入到 X 是为了当 P 为空的时候，判断此时的 R 是否为新的最大团，如果 X 不为空，说明目前的 R 是某一个以及找到的最大团的子集。

这个算法存在一些其他的优化，但是目前的我并不是很明确，即便是最基础的部分依旧存在让我困惑的部分，也许再次遇到我就能更加明白了，目前就先这样。

参考链接：

Clique
Clique problem
[Bron–Kerbosch algorithm](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorith
OI Wiki 最大团搜索算法
Lecture 6b: Cliques and the Bron–Kerbosch algorithm
Can you find: five five-letter words with twenty-five unique letters?

Day 24 （手动推导得出答案）

第二部分需要调试输入给出的加法器的程序，部分逻辑门被调换了位置，导致加法器结错误。在我的输入中最终结果的部分位并不对，需要修正的逻辑门应该是和这些逻辑门相关的部分。如果用暴力法，那就需要从所有逻辑门中选择八个进行排列，然后两两对换逻辑门右侧的部分，接着再对所有逻辑门进行重新求解，暴力法需要的实际无法想象，并不现实。

暴力是跑不完的，今天的注意力很难集中，没想到很完整的思路。逻辑门的加法应该是从最低位开始，逐渐往上实现计算的，也许进行深度搜索。从 x0 和 y0 开始，计算所有涉及到 x0 和 y0 的逻辑门，然后得到新的变量 gtb 和 z0 ，判断 z0 是否符合预期，如果不符合预期说明 x0 和 y0 的逻辑门存在错误，尝试调换顺序？

在我的输入中，第 17 位出现了不一致，第十七位应该是受到所有之前位运算的影响的，和 z17 直接相关的有两个变量，两个变量又分别对应一个逻辑门，难道调换这两个逻辑门吗？在考虑通用的方法无果后，我意识到还是要从二进制加法入手：

根据参考，可以确定用逻辑门实现加法主要涉及以下两种结构，半加器：

- sum = a xor b
- carry = a and b

全加器：两个半加器和一个或门

- sum = carry_in xor (a xor b) 
- carry_out = (carry_in and (a xor b)) or (a and b)

题目给出的加法输入逻辑门，刚刚好和一般的逻辑门实现加法一致，从 x 和 y 到 z 中间，除去 x 和 y ，还会会存在一个 carry_in 变量，然后有三个中间变量，以及一个输出的 carry_out 变量，每个中间变量都需要一个逻辑门得出，以及输出的变量也需要一个逻辑门，所以再每一位的计算中，至少存在四个逻辑门。当某一位出现错误时，可能是 carry_in 计算出错，也可能是 x 和 y 半加时的中间变量错误。

我首先实现了所有的逻辑演算，大致如下，对于 z 的任意一位，可以根据逻辑门实现的全加器推导到已知的 y 和 x ，那么我也可以根据输入的逻辑门，也推导出依靠已知 y 和 x 的计算某一位 z 的公式。又因为知道输入的逻辑门程序，其实就是多位全加器，那么理论上这两个公式应该是一致的，接着对 z 的每一位，都通过这两个途径取得公式，根据全加器得出的公式必然正确，而根据输入得出的公式则不一定正确，那么当这两个公式不一致时，就可以确定在计算 z 的这一位时输入的逻辑门（公式）存在问题。

通过实现解析方程，可以确定在第几位的时候，题目给出的逻辑门发生了错误，但是如何调换顺序呢？在我的输入中有 x12 AND y12 -> z12 ，也就是说在第 12 位就不考虑进位了，错误应该就是从这里开始的，虽然实际对应到位的值上，第 12 位的值是正确的。 x12 AND y12 应该是第二十位进位运算的一部分，右值 z12 应该换为其他的变量，已经出现过的变量不应该被替换，而且也不是 x y 和 z 开头的变量，是直接遍历测试吗？对于这个情况一般来说，只需要替换涉及到 z12 的所有逻辑门（包括中间逻辑门）即可，这就涉及到哪些变量和哪些逻辑门相关的问题了，难道要拓扑排序吗。

总感觉自己把问题想的太复杂了，或者是我又想偷懒了，有点犹豫不解。还是回到那个问题，要怎么替换呢，用代码我没想到好的方法，所以我决定那就自己手动推导一下，因为题目中最多只有 8 个逻辑门存在错误，在确定问题的大致范围后，其实手动推导并不困难，事实也是如此，通过手动推导我很容易的就发现了需要调换位置的逻辑门，最后利用 Python 解释器很容易的也得出了正确答案。

在手动推导的过程中，有几个关键的点：

那就是对于直接得出 z 的某一位的逻辑门，根据全加器的实现，除了最后一位必然是异或逻辑门，在我的输入中，需要调换位置的 3 对逻辑门都是这种情况
同时对于直接得出 z 的某一位的逻辑门，同样根据全加器的实现，其中一个必然是由或门得到，因为是上一位的进位，而另一位则必然是由异或门得到，来自半加器的加和结果。
对于 x 和 y 某一位的异或门和与门，其中异或门必然是参与对应 z 的直接计算的逻辑门（其中一个输入），而与门的结果则必然参与到计算进位的逻辑门（或门）。我的输入中第一个要进行调换的情况就是这个。
与门和异或门总是成对出现，两个输入如果有与门，那么一定有异或门。

根据这几点，是可以实现代码进行调换的，但是有一个很严格的前提，那就是给定的输入是严格的全加器，当然我也不确定是不是有其他的全加器实现。还有一个前提就是，需要调换的逻辑门数量很少，而且调换不会直接影响到其他位的计算。最终我还是没有实现代码自动替换，一是我感觉这个过程涉及的条件判断有点复杂，二是总感觉自己在做无用功，因为恰好题目和输入是这样，所以我的这些一个个复杂的条件恰好可行，我预见最后我还是不会对得到的代码感到满意。最后就是今天真的很没耐心，说实在的今天我居然能手推出结果，我都已经很满意了，更别提我还详细的知道了全加器的电路逻辑实现，这应该是今天题目的最大收获，所以今天就这样吧，最终还是需要知道全加器才能用我写的辅助程序进行定位，对的我的实现到最后也只能算是辅助程序。

参考：

Day 25

今年结束了，与往年一样，最后一天的题目总是让人心满意足，轻松并不随意。相比于往年，今年自己感觉更得心应手了，虽然有几天还是要苦思冥想，但是相比于第一年我遇到基本的算法都要琢磨推敲半天的情况，今年甚至感觉有些轻松，大部分的算法我都理解，除了刚刚开始还没怎么习惯，过去一年自己也基本没写什么代码，更别提看什么算法了，总的来说我对今年的题目很满意，但是对今年的自己和今年自己做的和没做的事情并不满意，加油！！！