news 2026/6/15 9:44:28

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

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
对clickhouse给出的二分法求解Advent of Code 2025第10题 电子工厂 第二部分的算法理解

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

WITHRECURSIVE tAS(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),bAS(SELECTrow_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,7translate(b1,'#.','10')::BIT::INTb1a,-- 转二进制位再转整数list_reduce([0]||string_split(unnest(string_split(replace(replace(b2,')',''),'(',''),' ')),',')::INT[],lambda x,y :(x+(1<<y)))b2a,-- 按钮转成整数列表string_split(b3,',')::INT[]b3aFROM(SELECTunnest(string_split(t,chr(10)))bFROMt))--from b;,dAS(SELECTrn,b1a,array_agg(b2a)a,b3aFROMbGROUPBYall),-- PART 2: 预计算按钮组合模式button_combination_patternsAS(SELECTrnaspuzzle_id,aasbutton_effects,b3aastarget_joltages,length(a)asnum_buttons,length(b3a)asnum_positions,combination_id,bit_count(combination_id)aspattern_cost,-- effect_pattern: 每个位置被按下的次数(SELECTlist((SELECTcount(*)FROMgenerate_series(0,length(a)-1)as_(buttonindex)WHERE(combination_id&(1<<buttonindex))!=0AND(a[buttonindex+1]&(1<<pos-1))!=0)ORDERBYpos)fromgenerate_series(1,length(b3a))as_(pos))::INT[]aseffect_pattern,-- parity_pattern: 每个位置的奇偶性 (模2)(SELECTlist((SELECTcount(*)FROMgenerate_series(0,length(a)-1)as_(buttonindex)WHERE(combination_id&(1<<buttonindex))!=0AND(a[buttonindex+1]&(1<<pos-1))!=0)%2ORDERBYpos)fromgenerate_series(1,length(b3a))as_(pos))::INT[]asparity_patternFROMdCROSSJOINgenerate_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_parityAS(SELECTpuzzle_id,button_effects,num_buttons,num_positions,parity_pattern,list((effect_pattern,pattern_cost))asavailable_patternsFROMbutton_combination_patternsGROUPBYpuzzle_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_solverAS(-- 基础情况: 从目标电压开始SELECTrn puzzle_id,a button_effects,length(a)asnum_buttons,length(b3a)asnum_positions,b3aascurrent_goal,0::BIGINTasaccumulated_cost,0asrecursion_depthFROMdUNIONALL-- 递归情况: 应用模式，减去，折半，继续selectpuzzle_id,button_effects,num_buttons,num_positions,current_goal,min(accumulated_cost)ASaccumulated_cost,min(recursion_depth)ASrecursion_depthfrom(SELECT--DISTINCTsolver.puzzle_id,solver.button_effects,solver.num_buttons,solver.num_positions,(-- New goal: (current - pattern) / 2SELECTlist((solver.current_goal[pos]-pattern_tuple[1][pos])/2ORDERBYpos)FROMgenerate_series(1,solver.num_positions)as_(pos))::INT[]ascurrent_goal,-- Accumulate cost: pattern_cost * 2^depthsolver.accumulated_cost+pattern_tuple[2]::BIGINT*(1<<solver.recursion_depth)asaccumulated_cost,solver.recursion_depth+1asrecursion_depthFROMrecursive_halving_solver solverJOINpatterns_grouped_by_parity patternsONpatterns.puzzle_id=solver.puzzle_idANDpatterns.parity_pattern=(SELECTlist(solver.current_goal[pos]%2ORDERBYpos)FROMgenerate_series(1,solver.num_positions)as_(pos))CROSSJOINunnest(patterns.available_patterns)as_(pattern_tuple)WHEREsolver.recursion_depth<100ANDEXISTS(SELECT1FROMunnest(solver.current_goal)as_(val)WHEREval!=0)-- 确保模式不会超出当前目标ANDNOTEXISTS(SELECT1FROMgenerate_series(1,solver.num_positions)as_(pos)WHEREpattern_tuple[1][pos]>solver.current_goal[pos]))GROUPBYpuzzle_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_solutionsAS(SELECTpuzzle_id,min(accumulated_cost)asminimum_costFROMrecursive_halving_solverWHERENOTEXISTS(SELECT1FROMunnest(current_goal)as_(val)WHEREval!=0)GROUPBYpuzzle_id)-- 输出Part 2结果SELECT'Part 2'aspart,sum(minimum_cost)assolutionFROMpart2_minimum_solutions;
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/6/13 1:28:38

AI视频修复实战指南：5大工具对比与操作技巧全解析

AI视频修复实战指南&#xff1a;5大工具对比与操作技巧全解析 【免费下载链接】ComfyUI-WanVideoWrapper 项目地址: https://gitcode.com/GitHub_Trending/co/ComfyUI-WanVideoWrapper 在视频内容创作日益普及的今天&#xff0c;AI视频修复技术正成为提升画质的有力武器…

作者头像 李华
网站建设 2026/6/14 14:15:15

Z-Image-Turbo_UI部署避坑指南：这些错误别再犯了

Z-Image-Turbo_UI部署避坑指南&#xff1a;这些错误别再犯了 你是不是也遇到过这样的情况&#xff1a;兴致勃勃地部署Z-Image-Turbo_UI&#xff0c;结果卡在启动环节&#xff0c;浏览器打不开界面&#xff0c;或者生成图片后找不到文件&#xff1f;别急&#xff0c;这些问题我…

作者头像 李华
网站建设 2026/6/15 5:10:57

开源向量模型怎么选？Qwen3-Embedding-4B实战测评指南

开源向量模型怎么选&#xff1f;Qwen3-Embedding-4B实战测评指南 在构建RAG系统、语义搜索服务或智能知识库时&#xff0c;嵌入模型&#xff08;Embedding Model&#xff09;就像整个系统的“语言翻译官”——它把人类语言转换成机器能理解的数字向量。选错模型&#xff0c;后…

作者头像 李华
网站建设 2026/6/14 8:45:51

Voice Sculptor捏声音模型解析｜附LLaSA与CosyVoice2集成实践

Voice Sculptor捏声音模型解析&#xff5c;附LLaSA与CosyVoice2集成实践 1. 模型核心能力与技术背景 1.1 什么是Voice Sculptor&#xff1f; Voice Sculptor是一款基于LLaSA和CosyVoice2两大语音合成框架二次开发的指令化语音生成系统。它最大的特点在于&#xff1a;你不需要…

作者头像 李华
网站建设 2026/6/15 5:32:58

YOLOv9权重文件在哪？/root/yolov9目录结构一文详解

YOLOv9权重文件在哪&#xff1f;/root/yolov9目录结构一文详解 你是不是也遇到过这种情况&#xff1a;刚部署好YOLOv9环境&#xff0c;准备跑个推理试试效果&#xff0c;结果执行命令时提示“找不到weights文件”&#xff1f;或者想训练自己的模型&#xff0c;却不确定该把预训…

作者头像 李华
网站建设 2026/6/13 2:30:39

SmartDNS网络加速：3个简单技巧让家庭网速飞起来

SmartDNS网络加速&#xff1a;3个简单技巧让家庭网速飞起来 【免费下载链接】smartdns A local DNS server to obtain the fastest website IP for the best Internet experience, support DoT, DoH. 一个本地DNS服务器&#xff0c;获取最快的网站IP&#xff0c;获得最佳上网体…

作者头像 李华