Advent of Code 2025 day8
day8 的输入是：
162,817,812 57,618,57 906,360,560 592,479,940 352,342,300 466,668,158 542,29,236 431,825,988 739,650,466 52,470,668 216,146,977 819,987,18 117,168,530 805,96,715 346,949,466 970,615,88 941,993,340 862,61,35 984,92,344 425,690,689
每一行对应一个三维空间的坐标点，例如 162，817，812 表示的是 X=162，Y=817，Z=812 的一个点。
在谜题里，每个点对应的是一个 接线盒，精灵们会用灯串连接接线盒，当两个接线盒通过一串灯连接时，电流可以在这两个接线盒之间通过。但是精灵们的灯串不够多，所以他们希望专注于连接那些 直线距离 尽可能靠近的接线盒对。
换句话说，在空间里有很多个点，需要计算每个点之间的距离，优先连接距离短的两个点。按照这样的规则，连接几次后，可能某几个点会连成一组，另外几个点也会连成一组。
例如在上面的例子里：
- 162,817,812 和 425,690,689 距离最短，它们连接在一起。形成了一个组 [162,817,812, 425,690,689]
- 接下来，距离最短的是 162,817,812 和 431,825,988，把它们连在一起。又发现 162,817,812 已经和另一个点连接了，所以这三个点都连在了一起，形成了 [162,817,812, 425,690,689, 431,825,988]
- 接下来距离最短的是 906,360,560 和 805,96,715。形成了 [906,360,560, 805,96,715]
- 接下来距离最短的是 431,825,988 和 425,690,689。它们已经连在一起了，在 [162,817,812, 425,690,689, 431,825,988] 之中。
- 依次类推
- 在这个例子中，做 10 次连接之后，会得到：
- 一个包含 5 个点的组、一个包含 4 个点的组、两个包含 2 个点的组，以及七个包含 1 个点的组
part1 的问题是，按照最短距离连线 N 次后，找到前三个点的数量最多的组，获取这三个组中点的数量，计算它们的乘积。
在上面的例子中，分别是 5、4、2，乘积是 40。
part1 的思路是：
- 首先计算所有点之间的距离，存储在一个数组中，数组的每一个元素记录一对点的坐标、两点之间的距离
- 数组按照两点距离升序排序，截取前 N 个数据
- 遍历这 N 个数据，获取每一对点的坐标，对它们进行连接分组：
- 如果两个点不在任何分组中，则把它们归类到一个新的分组
- 如果两个点都在已有的分组中，且是同一个分组，什么都不用做
- 如果两个点都在已有的分组中，但所在的分组不一样，合并这两个分组
- 如果只有一个点在已有的分组中，则把另一个点加入到这个分组中
- 按照分组中的点的数量降序排序，获取点的数量最多的前 3 个分组，获取分组中点的数量，计算乘积
由于示例中没有给出最终分组的情况，我无法验证我连接分组做的对不对。所以我先计算了所有点的距离并排序，例如这是我处理得到的数据：
{
('162,817,812', '425,690,689'): 316.90219311326956,
('162,817,812', '431,825,988'): 321.560258738545,
('906,360,560', '805,96,715'): 322.36935338211043,
('431,825,988', '425,690,689'): 328.11888089532425,
('862,61,35', '984,92,344'): 333.6555109690233,
('52,470,668', '117,168,530'): 338.33858780813046,
('819,987,18', '941,993,340'): 344.3893145845266,
('906,360,560', '739,650,466'): 347.59890678769403,
('346,949,466', '425,690,689'): 350.786259708102,
('906,360,560', '984,92,344'): 352.936254867646,
('592,479,940', '425,690,689'): 367.9823365326113,
('352,342,300', '542,29,236'): 371.70552861102294,
('352,342,300', '117,168,530'): 372.02284876066415,
('352,342,300', '466,668,158'): 373.41130138226936,
...
}
('162,817,812', '425,690,689'): 316.90219311326956 的意思是
162,817,812 和 425,690,689 的直线距离是 316.90219311326956。
然后按照规则，对点进行分组：
格式说明
第 N 次连线：当前连线的点 (备注)
分组1
分组2
分组3
…
例如：
3: '906,360,560', '805,96,715'
'162,817,812', '425,690,689', '431,825,988'
'906,360,560', '805,96,715'
表示第 3 次连线，当前连线的两个点是 '906,360,560', '805,96,715'。
连线后，形成了 2 个分组：
- 分组 1: '162,817,812', '425,690,689', '431,825,988'
- 分组 2: '906,360,560', '805,96,715'
1: '162,817,812', '425,690,689' '162,817,812', '425,690,689' 2: '162,817,812', '431,825,988' '162,817,812', '425,690,689', '431,825,988' 3: '906,360,560', '805,96,715' '162,817,812', '425,690,689', '431,825,988' '906,360,560', '805,96,715' 4: '431,825,988', '425,690,689' (没有变化) '162,817,812', '425,690,689', '431,825,988' '906,360,560', '805,96,715' 5: '862,61,35', '984,92,344' '162,817,812', '425,690,689', '431,825,988' '906,360,560', '805,96,715' '862,61,35', '984,92,344' 6: '52,470,668', '117,168,530' '162,817,812', '425,690,689', '431,825,988' '906,360,560', '805,96,715' '862,61,35', '984,92,344' '52,470,668', '117,168,530' 7: '819,987,18', '941,993,340' '162,817,812', '425,690,689', '431,825,988' '906,360,560', '805,96,715' '862,61,35', '984,92,344' '52,470,668', '117,168,530' '819,987,18', '941,993,340' 8: '906,360,560', '739,650,466' '162,817,812', '425,690,689', '431,825,988' '906,360,560', '805,96,715','739,650,466' '862,61,35', '984,92,344' '52,470,668', '117,168,530' '819,987,18', '941,993,340' 9: '346,949,466', '425,690,689' '162,817,812', '425,690,689', '431,825,988','346,949,466' '906,360,560', '805,96,715','739,650,466' '862,61,35', '984,92,344' '52,470,668', '117,168,530' '819,987,18', '941,993,340' 10: '906,360,560', '984,92,344' (合并了两个分组) '162,817,812', '425,690,689', '431,825,988','346,949,466' '906,360,560', '805,96,715','739,650,466', '862,61,35', '984,92,344' '52,470,668', '117,168,530' '819,987,18', '941,993,340'
通过这样的过程，我验证了整个分组过程，也是在这个过程中发现了我忽略的一个细节，即分组之间可能会合并。
具体的代码见：day8/solution.py
用少量的数据，验证逻辑，观察规律，有助于找到思路。
分组的代码我折腾了很久才写出来，因为我在遍历的过程中修改了被遍历的数组，产生了很多混乱，后来把查找和修改两个动作分开，逻辑才清晰了。
part2 的问题是，一直连线，最后所有的点都会连接在一起，找到最后的那根连线，获取连线上两个点的 X 坐标，计算两个 X 坐标的乘积。
所有点都连接在一起，意味着最终只会有一个分组，且分组中包含所有的点。
完成 part1 后，part2 就很简单了，只需要在每次连线之后，判断当前是否只有一个分组，且分组中点的数量等于所有点的数量。当找到这样的连线，就返回对应的两个点，获取点的 X 坐标，计算乘积即可。
具体的代码见：day8/solution.py
