news 2026/2/11 2:27:04

对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/2/7 14:10:24

MinerU如何监控GPU利用率？nvidia-smi调优指南

MinerU如何监控GPU利用率&#xff1f;nvidia-smi调优指南 1. 引言&#xff1a;为什么需要关注GPU利用率&#xff1f; 你有没有遇到过这种情况&#xff1a;启动了MinerU模型处理PDF文档&#xff0c;但感觉速度不如预期&#xff0c;任务卡在某个阶段迟迟不推进&#xff1f;可能…

作者头像 李华
网站建设 2026/2/8 20:20:30

RemoveWindowsAI完整指南：一键禁用系统AI功能保护隐私安全

RemoveWindowsAI完整指南&#xff1a;一键禁用系统AI功能保护隐私安全 【免费下载链接】RemoveWindowsAI Force Remove Copilot and Recall in Windows 项目地址: https://gitcode.com/GitHub_Trending/re/RemoveWindowsAI 在Windows 11的24H2更新中&#xff0c;微软引入…

作者头像 李华
网站建设 2026/2/7 17:41:23

Qwen轻量模型未来展望：边缘AI部署新范式

Qwen轻量模型未来展望&#xff1a;边缘AI部署新范式 1. 轻量级大模型的现实挑战与破局思路 在当前AI技术快速落地的过程中&#xff0c;一个核心矛盾日益凸显&#xff1a;用户希望获得强大、智能的交互体验&#xff0c;但实际运行环境却常常受限于算力、内存和部署复杂度。尤其…

作者头像 李华
网站建设 2026/2/10 5:37:32

Blog-AIAssistant：程序员专属的智能健康管理平台

Blog-AIAssistant&#xff1a;程序员专属的智能健康管理平台 【免费下载链接】Blog-AIAssistant 1.基于大模型的个人博客系统 2. 意在帮助压力巨大的程序员们时刻关注自己的身心家庭简况 3. 同时管理自己知识库 项目地址: https://gitcode.com/Guccang/Blog-AIAssistant …

作者头像 李华
网站建设 2026/2/8 17:18:41

Unsloth快速上手指南：3步完成Qwen模型微调

Unsloth快速上手指南&#xff1a;3步完成Qwen模型微调 你是否还在为大语言模型微调时显存占用高、训练速度慢而烦恼&#xff1f;Unsloth 可能正是你需要的解决方案。作为一个专注于提升 LLM 微调效率的开源框架&#xff0c;Unsloth 通过底层优化实现了训练速度翻倍、显存消耗降…

作者头像 李华
网站建设 2026/2/9 17:49:24

企业AI技能平台私有化部署：构建智能工作新生态

企业AI技能平台私有化部署&#xff1a;构建智能工作新生态 【免费下载链接】skills Public repository for Skills 项目地址: https://gitcode.com/GitHub_Trending/skills3/skills 在当前数字化转型浪潮中&#xff0c;企业面临着AI技术应用的重大挑战&#xff1a;如何在…

作者头像 李华