Advent of Code 2025 day7
day7 的输入是：
.......S....... ............... .......^....... ............... ......^.^...... ............... .....^.^.^..... ............... ....^.^...^.... ............... ...^.^...^.^... ............... ..^...^.....^.. ............... .^.^.^.^.^...^. ...............
这是一个超光速粒子歧管的图表（a diagram of the tachyon manifold）， S 是发射超光速粒子束的地方。超光速粒子束总是向下移动。超光速粒子束可以自由穿过空白区域 (.)。但是，如果超光速粒子束遇到分束器 (^)，光束就会停止；取而代之的是，新的超光速粒子束会被分束，从分束器的正左侧和正右侧继续向下移动。
于是，从 S 发射的超光速离子束最后会被分束成这样：
.......S....... .......|....... ......|^|...... ......|.|...... .....|^|^|..... .....|.|.|..... ....|^|^|^|.... ....|.|.|.|.... ...|^|^|||^|... ...|.|.|||.|... ..|^|^|||^|^|.. ..|.|.|||.|.|.. .|^|||^||.||^|. .|.|||.||.||.|. |^|^|^|^|^|||^| |.|.|.|.|.|||.|
part1 的问题是，超光速离子束被分束了几次？
当光束 (|) 往下碰到分束器 (^) 的时候，就会被分束，所以问题可以变成：
图中存在多少个这样的分束器：
| ^
统计这种结构的分束器的数量，对应的就是超光速离子束被分束的次数。
只要遍历每一行，对其中的每个分束器 (^) 判断它上面是否存在离子束 (|)，如果存在，就累计数量。
在遍历时，用一个变量维护上一行的离子束 (|) 状态，就可以方便地进行比较了。
part2 的问题是，实际只有一个超光速粒子，当它碰到分束器的时候，可能往左，也可能往右，统计最终有多少条路径可以走到底部。
例如粒子可以有一下几种走法：
一直沿着分束器的左边走
.......S....... .......|....... ......|^....... ......|........ .....|^.^...... .....|......... ....|^.^.^..... ....|.......... ...|^.^...^.... ...|........... ..|^.^...^.^... ..|............ .|^...^.....^.. .|............. |^.^.^.^.^...^. |..............
碰到分束器，交替地向左向右走
.......S....... .......|....... ......|^....... ......|........ ......^|^...... .......|....... .....^|^.^..... ......|........ ....^.^|..^.... .......|....... ...^.^.|.^.^... .......|....... ..^...^|....^.. .......|....... .^.^.^|^.^...^. ......|........
总之路径很多，最终能走到底部都算。
粒子时而往左，时而往右，看起来有非常多的组合。
但仔细一想，对于粒子而言，它只有 3 种选择：
- 要么穿过
.向下走 (↓) - 要么碰到
^，从左边往下走 (⮦) - 要么碰到
^，从右边往下走（⮧）
每往下走一次，粒子都要再做一次选择，直到走到底部。
为了更好的观察规律，可以从数据量较小的情况观察，例如只看前 5 行：
.......S....... ............... .......^....... ............... ......^.^......
上面的图中，总共有 4 种路径可以走到底，分别是：
.......S....... .......|....... ......|^....... ......|........ .....|^.^......
.......S....... .......|....... ......|^....... ......|........ ......^|^......
.......S....... .......|....... .......^|...... ........|...... ......^|^......
.......S....... .......|....... .......^|...... ........|...... ......^.^|.....
如何统计路径呢？可以一步步看看。
为了方便描述，用 diagram 表示这个图，diagram[0] 表示第一行，diagram[0][0] 表示第一行的第一列的位置。
用 timelines[x][y] 来表示在 x 行 y 列时，有多少的路径。
粒子从 S (diagram[0][7]) 出发，只能往下走，走到了 diagram[1][7]。
.......S....... .......|....... .......^....... ............... ......^.^......
此时 timelines[0][7] = timelines[1][7] 。
然后粒子碰到了一个分束器，可以向左，走到 diagram[2][6] ；也可以向右，走到 diagram[2][8] 。
.......S....... .......|....... ......|^....... ............... ......^.^......
.......S....... .......|....... .......^|...... ............... ......^.^......
此时 timelines[0][7] = timelines[1][7] = timelines[2][6] + timelines[2][8] 。
也就是说：
当没有碰到分束器时：
timelines[x][y] = timelines[x + 1][y]
即往下走一步的路径数量。
当碰到分束器时：
timelines[x][y] = timelines[x + 1][y - 1] + timelines[x + 1][y + 1]
即向左走和向右走的路径数量之和。
粒子继续往下走，式子可以一直写下去：
timelines[0][7] = timelines[1][7] = timelines[2][6] + timelines[2][8] = timelines[3][6] + timelines[3][8] = timelines[4][5] + timelines[4][7] + timelines[4][7] + timelines[4][9] = 1 + 1 + 1 + 1 = 4
当走到最后一行的时候，粒子已经走到走到底了，就只有一条路径，所以 timelines[4][y] = 1。
可以发现这是把一个大的问题，拆成一个更小的问题，直到这个问题知道确切的答案。可以利用递归实现，递归结束条件就是粒子走到了最后一行。
但是当我用这样的方法实现的时候，我发现代码执行了很久都没有结果。分析一下时间复杂度发现，当粒子到一个分束器，就会一分为二， 假设粒子在每一行都碰到分束器，相当于每往下走一行，计算量就会翻倍。假设有 N 行的话，时间复杂度就是 2 的 N 次方，是一个指数，所以随着 N 增加，时间复杂度会急剧上升。
观察式子，会发现 timelines[4][7] 被重复计算了，可以利用一个哈希表记录被计算过的位置的值，这样，每个位置只会被计算一次，假设有 N 个位置，时间复杂度就是 N，就会快很多了。
具体代码见：day7/solution.py
