Advent of Code 2025 day10

day10 的输入是：

[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}

看第一行， [.##.] 表示是一排灯，其中 . 表示对应下标（从 0 开始）的灯是熄灭的； # 表示灯是亮起的。默认灯全部都是熄灭的。

(1,3) 表示一个按钮，连接了下标 1 和下标 3 的灯，按一次，下标 1 和 3 的灯就会亮起，变成 # ；再按一次，下标 1 和 3 的灯就会熄灭，变回 . 。

part1 的问题是，你可以按任意的按钮任意次，使得灯的状态变成每一行开头 [] 里的状态，找到每一行需要的最少次数，累计求和。

针对一个按钮，按 1 次，对应下标的灯会亮起；按 2 次，对应下标的灯会熄灭，相当于没按过；按 3 次和按 1 次的效果是一样的。

也就是说，对一个按钮，按奇数次，会把对应下标的灯亮起，偶数次相当于这个灯没被按过。所以对任何一个灯，最多按 1 次就够了。

那么问题就变成了，对任意的灯按 1 次，它们的组合使得灯的状态变成 [] 中的状态。

假设有 A、B、C 三个按钮，我可以有很多组合：

只按 1 次 A / 只按 1 次 B / 只按 1 次 C （总操作数 1 次）
只按 1 次 A 和 B / 只按 1 次 A 和 C / 只按 1 次 B 和 C （总操作数 2 次）
只按 1 次 A、B、C （总操作数 3 次）

对每一行，我只要枚举所有的按钮组合，都按 1 次，从组合数量少的开始遍历（这样次数就是最少的），找到一个组合，使得灯的状态和 [] 中的状态一致就好了。

得到按钮的所有组合，需要用到回溯算法，在 python 中也可以利用 itertools.combinations。

判断状态的时候，我是按照按钮的下标拼接成 .# 组合的字符串，和 [] 中的字符串做比较，效率可能比较低。

Yordi Verkroost 在 Advent of Code 2025 - Day 10 中使用二进制表示按钮，用 XOR（异或）运算得到最终的状态，效率应该会更好。

part2 的输入不变，不过此时需要关注的是 {} 里的部分。

[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}

还是看第一行， [] 可以忽略， {3,5,4,7} 表示的是电压，下标 0 的电压是 3；下标 1 的电压是 5；依次类推。{} 中的电压默认都是 0。按钮 (1,3) 可以使得下标 1、3 的电压增加 1。

part2 的问题是，你可以按任意按钮任意次，最终使得电压达到 {} 里面的要求，找到需要的最少次数，累计每一行的最小次数求和。

一开始没什么头绪，我尝试随便按一个按钮看看会如何，例如我先尝试按 (0,2) ，先满足把下标 0 的电压：

按 1 次，电压变成 {1,0,1,0}
再按 1 次，电压变成 {2,0,2,0}
再按 1 次，电压变成 {3,0,3,0}

此时我就不能继续按 (0,2) 了，因为下标 0 的电压已经达到了 {3,5,4,7} 中的要求，再按就会超了。也就是说，现在我不能操作下标包含 0 的按钮了。

继续尝试操作其他按钮，再满足一个下标的电压，直到达到 {} 中的电压要求。

为什么我先开始满足下标 0 的电压？

因为在 {3,5,4,7} 中，下标 0 的电压是最小的，无论我操作哪个按钮，当下标 0 的电压达到要求的时候，其他下标的电压也不会超出。

按钮 (0,2) 、 (0,1) 都能使得下标 0 的电压增加 1，我怎么判断用哪个呢？我不知道，干脆穷举算了。

我先尝试都用 (0,2) 满足下标 0 的电压，下标 0 电压满足了，我就排除所有包含下标 0 的按钮，从剩下的按钮里，继续满足当前电压较小的，不断循环这个过程。

最后如果找到一个组合，能够满足 {} 中的电压要求，就记录按钮的操作次数，再找到操作次数的最小值。

尝试完 (0,2) ，就继续尝试 (0,1) ，看看哪个的操作次数是最少的。

折腾了好久写出一段代码，通过了示例输入，但死活过不了实际输入，看来思路是不对了。

没什么思路，于是去 reddit 找找思路，发现很多人提到了 Z3 和 ILP (Integer Linear Programming)，都是我不了解的东西。

和 LLM 进行了一些对话，把 part2 的问题丢给了它，让它分析问题，我大概明白了应该如何做。

对于 [.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7} ：

有这么几个按钮：

(3) → 下标 3 加 1
(1,3) → 下标 1 和 3 加 1
(2) → 下标 2 加 1
(2,3) → 下标 2 和 3 加 1
(0,2) → 下标 0 和 2 加 1
(0,1) → 下标 0 和 1 加 1

假设：

a: (3) 的次数
b: (1,3) 的次数
c: (2) 的次数
d: (2,3) 的次数
e: (0,2) 的次数
f: (0,1) 的次数

设最终需要的操作总次数是 T，那么 T = a + b + c + d + e + f。

其中：

下标 0 的电压要求是 3，(0,2) 和 (0,1) 会影响下标 0，操作 e 次 (0,2) 和 f 次 (0,1) 最终应该达到电压 3，所以有 e + f = 3。

类似的：

下标 1 的电压要求是 5: b + f = 5
下标 2 的电压要求是 4: c + d + e = 4
下标 3 的电压要求是 7: a + b + d = 7

于是得到了几个线性方程：

T = a + b + c + d + e + f
e + f = 3
b + f = 5
c + d + e = 4
a + b + d = 7
a、b、c、d、e、f 都是整数，且大于或等于 0 （每个按钮可以不操作或操作任意次）

目标是使得 T 最小。

此时再看看线性规划 (Linear programming, LP) 的定义：

线性规划（LP），也称为线性优化，是一种在数学模型中实现最佳结果的方法，该模型的各项要求和目标均由线性关系表示。

[…]

更正式地说，线性规划是一种优化线性目标函数的技术，该函数受线性等式和线性不等式约束。其可行域是一个凸多面体，该多面体定义为有限多个半空间的交集，每个半空间都由一个线性不等式定义。其目标函数是定义在该多面体上的实值仿射（线性）函数。如果存在这样的点，线性规划算法会在多面体中找到该函数具有最大（或最小）值的点。

说实话我没太看懂，但大体的意思是，有一种数学模型，可以用一些线性等式和线性不等式来表示，同时存在一些约束条件。通过这样的模型，最终可以找到最值。

而当线性规划中，变量被约束为整数，问题就会变成了整数线性规划 (Integer Linear Programming, ILP)。

此时回过头来看看上面得到的结论：

T = a + b + c + d + e + f

e + f = 3

b + f = 5

c + d + e = 4

a + b + d = 7

a、b、c、d、e、f 都是整数，且大于或等于 0 （每个按钮可以不操作或操作任意次）

目标是使得 T 最小。

可以发现这个模型是符合整数线性规划的：

可以用线性等式表达问题
存在约束条件，例如 e + f 需要等于 3
变量 a,b,c,d,e,f 要求是整数

所以，这就是一个整数线性规划问题，而在 python 中，可以利用 Z3 或 PuLP 来处理整数线性规划问题。

不过就算知道可以用 Z3，我也不会用 _(:3 」∠)_。

还是求助了 LLM，得到这样的一个函数，并问它每一行代码的含义：

from z3 import Int, Optimize, sat

def min_operations_z3(ops, target):
    """使用 Z3 求解最小操作次数，返回整数最优值（若无解返回 None）"""
    n = len(ops)           # 操作数量
    m = len(target)        # 索引数量

    # 创建变量，表示的是每个按钮的操作次数，x0 表示第一个按钮的操作次数
    vars = [Int(f'x{i}') for i in range(n)]

    opt = Optimize()
    # 添加约束，操作次数只能大于或等于 0
    for v in vars:
        opt.add(v >= 0)

    # 遍历所有的目标电压
    for i in range(m):
        # 遍历所有的按钮，当按钮会影响目标电压，则累计操作次数，相当于构造 e + f = 3
        coeff_sum = sum(vars[j] for j in range(n) if i in ops[j])
        opt.add(coeff_sum == target[i])

    # 最小化总操作次数，使用 minimize 求最小值
    total = sum(vars)
    opt.minimize(total)

    # 当所有约束都能满足的时候，得到这个模型对象，获取操作总次数的最小值
    if opt.check() == sat:
        model = opt.model()
        return model.evaluate(total).as_long()
    else:
        return None

使用 Z3 问题就很轻松就解决了。

如果你对 PuLP 的方法感兴趣，可以看看 Yordi Verkroost 的 Advent of Code 2025 - Day 10。

day10 依然是让人折磨的一天 _(:3 」∠)_，希望以后我碰到类似问题能想起来可以用线性规划解决。