对clickhouse给出的二分法求解Advent of Code 2025第10题 电子工厂 第二部分的算法理解

这是我对前文SQL的中间结果展示和理解笔记，使用第一行数据做示例。

WITH RECURSIVE t AS (
SELECT
'[.##.] (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}' t
),
b AS (
SELECT
row_number() OVER () rn,
reverse(substr(b, 2, instr(b, ']') – 2)) b1, — 信号灯字符串，格式.##.，注意要翻转字符串
substr(b, instr(b, ']') + 2, instr(b, '{') – 3 – instr(b, ']')) b2, — 按钮字符串，格式(3) (1,3) (2) (2,3) (0,2) (0,1)
substr(b, instr(b, '{') + 1, instr(b, '}') – 1 – instr(b, '{')) b3, — 伏特字符串，格式3,5,4,7
translate(b1, '#.', '10')::BIT::INT b1a, — 转二进制位再转整数
list_reduce([0] || string_split(unnest(string_split(replace(replace(b2, ')', ''), '(', ''), ' ')), ',')::INT[],
lambda x, y : (x + (1 << y))) b2a, — 按钮转成整数列表
string_split(b3, ',')::INT[] b3a
FROM (SELECT unnest(string_split(t, chr(10))) b FROM t)
)
–from b;
,
d AS (
SELECT rn, b1a, array_agg(b2a) a, b3a
FROM b
GROUP BY all
),

— PART 2: 预计算按钮组合模式
button_combination_patterns AS (
SELECT
rn as puzzle_id,
a as button_effects,
b3a as target_joltages,
length(a) as num_buttons,
length(b3a) as num_positions,
combination_id,
bit_count(combination_id) as pattern_cost,

— effect_pattern: 每个位置被按下的次数
(
SELECT list(
(
SELECT count(*)
FROM generate_series(0, length(a)–1) as _(buttonindex)
WHERE (combination_id & (1<< buttonindex))!=0
AND (a[buttonindex+1]& (1<< pos–1))!=0
)
ORDER BY pos
)
from generate_series(1, length(b3a)) as _(pos)

)::INT[] as effect_pattern,

— parity_pattern: 每个位置的奇偶性 (模2)
(
SELECT list(
(
SELECT count(*)
FROM generate_series(0, length(a)–1) as _(buttonindex)
WHERE (combination_id & (1<< buttonindex))!=0
AND (a[buttonindex+1]& (1<< pos–1))!=0
) % 2
ORDER BY pos
)
from generate_series(1, length(b3a)) as _(pos)
)::INT[] as parity_pattern
FROM d
CROSS JOIN generate_series(0, (1 << length(a)) – 1) as _(combination_id)
)
–select * from button_combination_patterns order by puzzle_id ,combination_id;
/*
combination_id是6个按钮的全部组合的序号，其的二进制数的各位表示相应按钮是否被选用。比如《a》行1表示只按第1个按钮，导致结果是8代表的电压第3位+1，见effect_pattern第4个元素。
pattern_cost表示当前模式所需的按钮组合需要按下几个按钮。比如《b》行，第1和第2个按钮被按下，按键次数为2，导致电压第1位+1，第3位+2，见effect_pattern第2和第4个元素。
parity_pattern对effect_pattern中的每个元素按2取模。偶数变0，奇数变1。
┌───────────┬──────────────────────┬─────────────────┬─────────────┬───────────────┬────────────────┬──────────────┬────────────────┬────────────────┐
│ puzzle_id │ button_effects │ target_joltages │ num_buttons │ num_positions │ combination_id │ pattern_cost │ effect_pattern │ parity_pattern │
│ int64 │ int32[] │ int32[] │ int64 │ int64 │ int64 │ int8 │ int32[] │ int32[] │
├───────────┼──────────────────────┼─────────────────┼─────────────┼───────────────┼────────────────┼──────────────┼────────────────┼────────────────┤
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 0 │ 0 │ [0, 0, 0, 0] │ [0, 0, 0, 0] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 1 │ 1 │ [0, 0, 0, 1] │ [0, 0, 0, 1] │《a》
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 2 │ 1 │ [0, 1, 0, 1] │ [0, 1, 0, 1] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 3 │ 2 │ [0, 1, 0, 2] │ [0, 1, 0, 0] │《b》
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 4 │ 1 │ [0, 0, 1, 0] │ [0, 0, 1, 0] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 5 │ 2 │ [0, 0, 1, 1] │ [0, 0, 1, 1] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 6 │ 2 │ [0, 1, 1, 1] │ [0, 1, 1, 1] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 7 │ 3 │ [0, 1, 1, 2] │ [0, 1, 1, 0] │
│ · │ · │ · │ · │ · │ · │ · │ · │ · │
│ · │ · │ · │ · │ · │ · │ · │ · │ · │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 61 │ 5 │ [2, 1, 3, 2] │ [0, 1, 1, 0] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 62 │ 5 │ [2, 2, 3, 2] │ [0, 0, 1, 0] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ [3, 5, 4, 7] │ 6 │ 4 │ 63 │ 6 │ [2, 2, 3, 3] │ [0, 0, 1, 1] │
├───────────┴──────────────────────┴─────────────────┴─────────────┴───────────────┴────────────────┴──────────────┴────────────────┴────────────────┤
│ 64 rows (40 shown) 9 columns │
└────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
*/
,

— 按奇偶性分组模式
patterns_grouped_by_parity AS (
SELECT
puzzle_id,
button_effects,
num_buttons,
num_positions,
parity_pattern,
list((effect_pattern, pattern_cost)) as available_patterns
FROM button_combination_patterns
GROUP BY puzzle_id, button_effects, num_buttons, num_positions, parity_pattern
)

–from patterns_grouped_by_parity order by puzzle_id,parity_pattern;
/*
按parity_pattern分组后的available_patterns具有一致的奇偶性，patterns.parity_pattern = (SELECT list(solver.current_goal[pos] % 2 ))保证了solver.current_goal[pos] – pattern_tuple[1][pos])总是能被2整除。
┌───────────┬──────────────────────┬─────────────┬───────────────┬────────────────┬──────────────────────────────────────────────────────────────────────────────┐
│ puzzle_id │ button_effects │ num_buttons │ num_positions │ parity_pattern │ available_patterns │
│ int64 │ int32[] │ int64 │ int64 │ int32[] │ struct(integer[], tinyint)[] │
├───────────┼──────────────────────┼─────────────┼───────────────┼────────────────┼──────────────────────────────────────────────────────────────────────────────┤
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ [([2, 2, 2, 2], 4), ([2, 2, 2, 2], 5), ([0, 0, 2, 2], 3), ([0, 0, 0, 0], 0)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 1] │ [([2, 2, 2, 3], 5), ([2, 2, 2, 1], 4), ([0, 0, 2, 1], 2), ([0, 0, 0, 1], 1)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 1, 0] │ [([2, 2, 3, 2], 5), ([2, 2, 1, 2], 4), ([0, 0, 1, 2], 2), ([0, 0, 1, 0], 1)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 1, 1] │ [([2, 2, 3, 3], 6), ([2, 2, 1, 1], 3), ([0, 0, 1, 1], 1), ([0, 0, 1, 1], 2)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 0, 0] │ [([2, 1, 2, 2], 4), ([2, 1, 2, 0], 3), ([0, 1, 2, 2], 3), ([0, 1, 0, 2], 2)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 0, 1] │ [([2, 1, 2, 1], 3), ([2, 1, 2, 1], 4), ([0, 1, 2, 3], 4), ([0, 1, 0, 1], 1)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 1, 0] │ [([2, 1, 3, 2], 5), ([2, 1, 1, 0], 2), ([0, 1, 1, 2], 2), ([0, 1, 1, 2], 3)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 1, 1] │ [([2, 1, 3, 1], 4), ([2, 1, 1, 1], 3), ([0, 1, 1, 3], 3), ([0, 1, 1, 1], 2)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 0, 0, 0] │ [([1, 2, 2, 2], 4), ([1, 2, 0, 2], 3), ([1, 0, 2, 2], 3), ([1, 0, 2, 0], 2)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 0, 0, 1] │ [([1, 2, 2, 3], 5), ([1, 2, 0, 1], 2), ([1, 0, 2, 1], 2), ([1, 0, 2, 1], 3)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 0, 1, 0] │ [([1, 2, 1, 2], 3), ([1, 2, 1, 2], 4), ([1, 0, 3, 2], 4), ([1, 0, 1, 0], 1)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 0, 1, 1] │ [([1, 2, 1, 3], 4), ([1, 2, 1, 1], 3), ([1, 0, 3, 1], 3), ([1, 0, 1, 1], 2)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 1, 0, 0] │ [([1, 1, 2, 2], 4), ([1, 1, 0, 0], 1), ([1, 1, 2, 2], 3), ([1, 1, 2, 2], 4)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 1, 0, 1] │ [([1, 1, 2, 1], 3), ([1, 1, 0, 1], 2), ([1, 1, 2, 3], 4), ([1, 1, 2, 1], 3)] │《c》
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 1, 1, 0] │ [([1, 1, 1, 2], 3), ([1, 1, 1, 0], 2), ([1, 1, 3, 2], 4), ([1, 1, 1, 2], 3)] │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 1, 1, 1] │ [([1, 1, 1, 1], 2), ([1, 1, 1, 1], 3), ([1, 1, 3, 3], 5), ([1, 1, 1, 1], 2)] │
├───────────┴──────────────────────┴─────────────┴───────────────┴────────────────┴──────────────────────────────────────────────────────────────────────────────┤
│ 16 rows 6 columns │
└────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
*/
,

— 递归折半算法
recursive_halving_solver AS (
— 基础情况: 从目标电压开始
SELECT
rn puzzle_id,
a button_effects,
length(a) as num_buttons,
length(b3a) as num_positions,
b3a as current_goal,
0::BIGINT as accumulated_cost,
0 as recursion_depth
FROM d

UNION ALL

— 递归情况: 应用模式，减去，折半，继续
select
puzzle_id,
button_effects,
num_buttons,
num_positions,
current_goal,
min(accumulated_cost) AS accumulated_cost,
min(recursion_depth) AS recursion_depth
from(
SELECT –DISTINCT
solver.puzzle_id,
solver.button_effects,
solver.num_buttons,
solver.num_positions,
(— New goal: (current – pattern) / 2
SELECT list(
(solver.current_goal[pos] – pattern_tuple[1][pos]) / 2
ORDER BY pos
)
FROM generate_series(1, solver.num_positions) as _(pos)
)::INT[] as current_goal,
— Accumulate cost: pattern_cost * 2^depth
solver.accumulated_cost +
pattern_tuple[2]::BIGINT * (1 << solver.recursion_depth) as accumulated_cost,

solver.recursion_depth + 1 as recursion_depth
FROM recursive_halving_solver solver
JOIN patterns_grouped_by_parity patterns
ON patterns.puzzle_id = solver.puzzle_id
AND patterns.parity_pattern = (
SELECT list(solver.current_goal[pos] % 2 ORDER BY pos)
FROM generate_series(1, solver.num_positions) as _(pos)
)
CROSS JOIN unnest(patterns.available_patterns) as _(pattern_tuple)
WHERE
solver.recursion_depth < 100
AND EXISTS (
SELECT 1
FROM unnest(solver.current_goal) as _(val)
WHERE val != 0
)
— 确保模式不会超出当前目标
AND NOT EXISTS (
SELECT 1
FROM generate_series(1, solver.num_positions) as _(pos)
WHERE pattern_tuple[1][pos] > solver.current_goal[pos]
)
)
GROUP BY puzzle_id, button_effects, num_buttons, num_positions, current_goal
)
–from recursive_halving_solver;
/*
[3, 5, 4, 7]各个元素%2的结果是[1, 1, 0, 1]， [1, 1, 0, 1]对应的模式是《c》行 [([1, 1, 2, 1], 3), ([1, 1, 0, 1], 2), ([1, 1, 2, 3], 4), ([1, 1, 2, 1], 3)]

([3, 5, 4, 7]各个元素-模式中各个元素)/2的结果是:
[3, 5, 4, 7]-[1, 1, 2, 1]=[2, 4, 2, 6], 再除以2得[1, 2, 1, 3]，
[3, 5, 4, 7]-[1, 1, 2, 3]=[2, 4, 2, 4], 再除以2得[1, 2, 1, 2]，
[3, 5, 4, 7]-[1, 1, 0, 1]=[2, 4, 4, 6], 再除以2得[1, 2, 2, 3]，
下轮迭代使用新目标去求解，因为提前除以2了，所以得到的按压次数需要乘2
┌───────────┬──────────────────────┬─────────────┬───────────────┬──────────────┬──────────────────┬─────────────────┐
│ puzzle_id │ button_effects │ num_buttons │ num_positions │ current_goal │ accumulated_cost │ recursion_depth │
│ int64 │ int32[] │ int64 │ int64 │ int32[] │ int64 │ int32 │
├───────────┼──────────────────────┼─────────────┼───────────────┼──────────────┼──────────────────┼─────────────────┤
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [3, 5, 4, 7] │ 0 │ 0 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 2, 1, 3] │ 3 │ 1 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 2, 1, 2] │ 4 │ 1 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 2, 2, 3] │ 2 │ 1 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 1] │ 9 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 10 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 1, 1] │ 6 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 0, 1] │ 6 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 10 │ 3 │
└───────────┴──────────────────────┴─────────────┴───────────────┴──────────────┴──────────────────┴─────────────────┘
若把min改成distinct，可以看出相同得到[0, 0, 0, 0]（即完成目标）有10、11、12、13、14等不同的按压次数，有的迭代了2层，有的3层。
┌───────────┬──────────────────────┬─────────────┬───────────────┬──────────────┬──────────────────┬─────────────────┐
│ puzzle_id │ button_effects │ num_buttons │ num_positions │ current_goal │ accumulated_cost │ recursion_depth │
│ int64 │ int32[] │ int64 │ int64 │ int32[] │ int64 │ int32 │
├───────────┼──────────────────────┼─────────────┼───────────────┼──────────────┼──────────────────┼─────────────────┤
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [3, 5, 4, 7] │ 0 │ 0 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 2, 2, 3] │ 2 │ 1 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 2, 1, 2] │ 4 │ 1 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [1, 2, 1, 3] │ 3 │ 1 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 1, 1] │ 6 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 0, 1] │ 6 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 10 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 11 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 0, 1] │ 8 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 1] │ 9 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 12 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 1, 0, 1] │ 7 │ 2 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 12 │ 3 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 14 │ 3 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 11 │ 3 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 10 │ 3 │
│ 1 │ [8, 10, 4, 12, 5, 3] │ 6 │ 4 │ [0, 0, 0, 0] │ 13 │ 3 │
├───────────┴──────────────────────┴─────────────┴───────────────┴──────────────┴──────────────────┴─────────────────┤
│ 17 rows 7 columns │
└────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
*/
,

— Part 2 最小成本解决方案
part2_minimum_solutions AS (
SELECT
puzzle_id,
min(accumulated_cost) as minimum_cost
FROM recursive_halving_solver
WHERE NOT EXISTS (
SELECT 1
FROM unnest(current_goal) as _(val)
WHERE val != 0
)
GROUP BY puzzle_id
)

— 输出Part 2结果
SELECT
'Part 2' as part,
sum(minimum_cost) as solution
FROM part2_minimum_solutions;