news 2026/4/28 20:07:25

利用DeepSeek辅助翻译clickhouse SQL为DuckDB 格式求解Advent of Code 2025第10题 电子工厂 第二部分

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
利用DeepSeek辅助翻译clickhouse SQL为DuckDB 格式求解Advent of Code 2025第10题 电子工厂 第二部分

首先把clickhouse 解题 SQL发给DeepSeek，

用中文解读附件clickhouse格式sql的解题逻辑，特别是part2的逻辑

它给出了以下解读。

看了这个ClickHouse SQL，这是解决Advent of Code（AOC）第10天的题目，主要涉及按钮组合和状态转换的优化问题。让我详细解读逻辑：

整体问题结构

题目包含两部分：

  1. Part 1：找到最少按钮次数，使LED灯（用0/1表示）变成目标图案
  2. Part 2：扩展问题，考虑不同的"电压"目标，需要计算最小总成本

Part 1 逻辑（暴力枚举）

-- 核心思路：枚举所有按钮组合（2^n种可能）-- 每个按钮影响特定位置，按下改变对应位置的状态（XOR运算）-- 找到与目标图案完全匹配且按钮次数最少的结果
  1. 解析输入：将’#‘转为1，’.'转为0
  2. 枚举组合：对n个按钮，生成0到2^n-1的所有位掩码
  3. 计算效果：对每个组合，计算每个位置被按下的按钮数之和，取模2（XOR）
  4. 匹配目标：筛选出resulting_diagram = target_diagram的组合
  5. 找最小：按bitCount(combination_id)排序，取最小值

Part 2 核心逻辑（难点）

这是问题的核心创新点，采用了递归折半算法：

1. 预计算所有按钮组合的"模式"

-- 为每个按钮组合计算：-- effect_pattern: 每个位置被按下的次数（整数，不只是0/1）-- parity_pattern: 每个位置的奇偶性（模2的结果）-- pattern_cost: 该组合的按钮次数

2. 按奇偶性分组模式

-- 将effect_pattern按parity_pattern分组-- 相同奇偶约束的模式放在一起，便于后续查找

3.关键算法：递归折半

-- 初始：current_goal = target_joltages（目标电压值）-- 递归步骤：-- 1. 根据current_goal的奇偶性选择合适的模式组（parity_pattern必须匹配）-- 2. 应用一个模式：current_goal = current_goal - effect_pattern-- 3. 折半：current_goal = intDiv(current_goal, 2)-- 4. 累计成本：cost += pattern_cost * (2^depth)

算法原理理解：

这实际上是一个基于二进制的动态规划：

  • 为什么要匹配奇偶性？
    因为(current - pattern) / 2必须是整数，所以current和pattern在每个位置必须同奇偶

  • 为什么除以2？
    每次递归将问题规模减半，从二进制角度看：

    • 每个位置的电压值看成二进制数
    • 奇偶性 = 最低位
    • 除以2 = 右移一位（去掉已处理的最低位）

  • 成本计算为什么是pattern_cost * 2^depth？
    假设最优解中某个模式需要在第d层（深度）使用k次

    • 在第d层用1次 → 成本 = pattern_cost
    • 在第d-1层用1次 → 相当于第d层用2次 → 成本 = pattern_cost * 2
    • 以此类推：成本 = pattern_cost × 2^depth

4. 终止条件

-- 当current_goal全为0时停止-- 从所有路径中找最小accumulated_cost

算法复杂度分析

  • Part 1：O(2^n × m)，n=按钮数，m=位置数（暴力搜索）
  • Part 2：O(2^n + L × P × D)，其中：
    • 2^n是预计算模式
    • L是递归深度（≤100）
    • P是模式数量
    • D是目标维度

实际应用思路

这个Part 2的算法很巧妙：

  1. 将多位置问题分解为独立但又相互关联的子问题
  2. 利用二进制表示和奇偶性约束大幅减少搜索空间
  3. 通过"除以2"操作将指数问题转化为线性递归
  4. 动态规划思想：从最低位开始逐位解决

这是一个典型的状态压缩+二进制优化的竞赛题目解法，展示了如何将看似复杂的组合优化问题转化为高效的数学计算问题。

看来他理解得不错，继续提示

利用下面已有的部分duckdb sql,将上述clickhouse sql计算part2的逻辑翻译为duckdb sql，不做别的

基于已有的DuckDB SQL结构和Part 2的逻辑，我翻译出以下完整代码：

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)),dAS(SELECTrn,b1a,array_agg(b2a)a,b3aFROMbGROUPBYall),-- PART 2: 预计算按钮组合模式button_combination_patternsAS(SELECTrnaspuzzle_id,aasbutton_effects,b3aastarget_joltages,cardinality(a)asnum_buttons,cardinality(b3a)asnum_positions,combination_id,bit_count(combination_id)aspattern_cost,-- effect_pattern: 每个位置被按下的次数(SELECTlist_agg((SELECTcount(*)FROMunnest(a)aseffectWHEREbit_test(combination_id,index)ANDbit_test(effect,pos-1))ORDERBYpos)FROMgenerate_series(1,cardinality(b3a))aspos)::INT[]aseffect_pattern,-- parity_pattern: 每个位置的奇偶性 (模2)(SELECTlist_agg((SELECTcount(*)FROMunnest(a)aseffectWHEREbit_test(combination_id,index)ANDbit_test(effect,pos-1))%2ORDERBYpos)FROMgenerate_series(1,cardinality(b3a))aspos)::INT[]asparity_patternFROMdCROSSJOINgenerate_series(0,(1<<cardinality(a))-1)ascombination_idCROSSJOIN(SELECTgenerate_subscripts(a,1)-1asindex)asindexes),-- 按奇偶性分组模式patterns_grouped_by_parityAS(SELECTpuzzle_id,button_effects,num_buttons,num_positions,parity_pattern,list_agg((effect_pattern,pattern_cost))asavailable_patternsFROMbutton_combination_patternsGROUPBYpuzzle_id,button_effects,num_buttons,num_positions,parity_pattern),-- 递归折半算法recursive_halving_solverAS(-- 基础情况: 从目标电压开始SELECTpuzzle_id,button_effects,num_buttons,num_positions,target_joltagesascurrent_goal,0::BIGINTasaccumulated_cost,0asrecursion_depthFROMdJOINbutton_combination_patternsUSING(puzzle_id)GROUPBYpuzzle_id,button_effects,num_buttons,num_positions,target_joltagesUNIONALL-- 递归情况: 应用模式，减去，折半，继续SELECTDISTINCTsolver.puzzle_id,solver.button_effects,solver.num_buttons,solver.num_positions,(SELECTlist_agg((solver.current_goal[pos]-pattern_tuple[1][pos])/2ORDERBYpos)FROMgenerate_series(1,solver.num_positions)aspos)::INT[]ascurrent_goal,solver.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_agg(solver.current_goal[pos]%2ORDERBYpos)FROMgenerate_series(1,solver.num_positions)aspos)CROSSJOINunnest(patterns.available_patterns)aspattern_tupleWHEREsolver.recursion_depth<100ANDEXISTS(SELECT1FROMunnest(solver.current_goal)asvalWHEREval!=0)-- 确保模式不会超出当前目标ANDNOTEXISTS(SELECT1FROMgenerate_series(1,solver.num_positions)asposWHEREpattern_tuple[1][pos]>solver.current_goal[pos])),-- Part 2 最小成本解决方案part2_minimum_solutionsAS(SELECTpuzzle_id,min(accumulated_cost)asminimum_costFROMrecursive_halving_solverWHERENOTEXISTS(SELECT1FROMunnest(current_goal)asvalWHEREval!=0)GROUPBYpuzzle_id)-- 输出Part 2结果SELECT'Part 2'aspart,sum(minimum_cost)assolutionFROMpart2_minimum_solutions;

关键翻译要点：

  1. 数据类型转换：ClickHouse的UInt32转为DuckDB的INT，UInt64转为BIGINT

  2. 数组操作：

    • arrayMap→ 使用list_agg配合子查询
    • arrayReduce→ 使用count(*)或sum()
    • arrayAll→ 使用NOT EXISTS或EXISTS

  3. 位运算：

    • bitTest→bit_test
    • bitCount→bit_count
    • pow(2, n)→(1 << n)

  4. 递归结构：

    • 保持相同的递归折半算法逻辑
    • 使用DuckDB的RECURSIVE CTE语法

  5. 模式匹配：

    • 奇偶性约束通过current_goal % 2计算
    • 模式选择基于奇偶性匹配

  6. 成本计算：

    • pattern_cost * 2^depth转为pattern_tuple[2] * (1 << depth)

这个翻译保持了原ClickHouse SQL的逻辑完整性，只进行了必要的语法转换。

但以上SQL有错误，主要是以下方面

  1. duckdb没有list_agg函数，应该用list函数代替
  2. duckdb没有bit_test函数，应该用位运算代替
  3. duckdb没有cardinality函数，应该用length函数代替
  4. DuckDB中FROM generate_series(1, solver.num_positions) as pos的写法会把pos当作一个结构，而不是表的列，需要改成... as t(pos)
  5. button_combination_patterns子查询中的indexes应该放到相关子查询，而非主查询
  6. recursive_halving_solver子查询将递归部分的求min改成了DISTINCT, 造成中间结果过多。

我将以上部分都修改后，求解成功。

memory D.read2510p2a.sql┌─────────┬──────────┐ │ part │ solution │ │varchar│ int128 │ ├─────────┼──────────┤ │ Part2│19810│ └─────────┴──────────┘ RunTime(s):real142.785user348.915288sys73.074016

比同样机器上执行原始ClickHouse SQL慢了36秒。

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/18 19:48:01

Android横向刷新神器SmartRefreshHorizontal：告别垂直刷新局限

Android横向刷新神器SmartRefreshHorizontal&#xff1a;告别垂直刷新局限 【免费下载链接】SmartRefreshHorizontal 横向刷新、水平刷新、RefreshLayout、OverScroll&#xff0c;Horizontal&#xff0c;基于SmartRefreshLayout的水平智能刷新 项目地址: https://gitcode.co…

作者头像 李华
网站建设 2026/4/18 21:36:23

通义千问3-14B快速部署：Docker镜像开箱即用教程

通义千问3-14B快速部署&#xff1a;Docker镜像开箱即用教程 1. 为什么选择 Qwen3-14B&#xff1f; 你有没有遇到过这种情况&#xff1a;想要一个推理能力强的大模型&#xff0c;但显卡只有单张 RTX 4090&#xff1f;想跑长文本处理任务&#xff0c;却发现大多数开源模型撑不住…

作者头像 李华
网站建设 2026/4/25 16:21:44

2024年3月GESP真题及题解(C++七级): 俄罗斯方块

2024年3月GESP真题及题解(C七级): 俄罗斯方块 题目描述 小杨同学用不同种类的俄罗斯方块填满了一个大小为 n m n \times m nm 的网格图。 网格图由 n m n \times m nm 个带颜色方块构成。小杨同学现在将这个网格图交给了你&#xff0c;请你计算出网格图中俄罗斯方块的种类…

作者头像 李华
网站建设 2026/4/22 4:36:48

ZooKeeper数据迁移实战手册：3种方案保障集群零停机切换

ZooKeeper数据迁移实战手册&#xff1a;3种方案保障集群零停机切换 【免费下载链接】zookeeper Apache ZooKeeper 项目地址: https://gitcode.com/gh_mirrors/zo/zookeeper Apache ZooKeeper作为分布式系统的核心协调服务&#xff0c;承载着配置管理、服务发现和分布式锁…

作者头像 李华
网站建设 2026/4/27 1:42:37

Qwen3-4B-Instruct医疗问答系统案例：专业术语理解部署教程

Qwen3-4B-Instruct医疗问答系统案例&#xff1a;专业术语理解部署教程 1. 医疗场景下的AI语言模型新选择 你有没有遇到过这样的情况&#xff1a;患者拿着检查报告来问“低密度脂蛋白偏高是什么意思”&#xff0c;而你需要花时间解释一堆医学术语&#xff1f;如果有一个AI助手…

作者头像 李华
网站建设 2026/4/27 14:21:08

FSMN VAD支持哪些格式？MP3/WAV/FLAC全兼容实测

FSMN VAD支持哪些格式&#xff1f;MP3/WAV/FLAC全兼容实测 1. 引言&#xff1a;语音检测也能这么简单&#xff1f; 你有没有遇到过这样的问题&#xff1a;一堆会议录音、电话访谈或者课堂音频&#xff0c;想从中提取出真正有人说话的片段&#xff0c;但手动剪辑太费时间&…

作者头像 李华