DeepSeek对利用DuckDB求解Advent of Code 2021第9题“烟雾盆地”第二部分SQL的分析

这是DBatUTuebingen发布的。
源地址：https://github.com/DBatUTuebingen/Advent_of_Code

Advent of Code 2021 第9天

烟雾盆地

输入解析和低点计算放在共享文件smoke-basin.sql中（通过.read引入），两部分都会用到。

第一部分

用法：

$ duckdb < smoke-basin-part1.sql ┌────────────┐ │ risk level │ │ int128 │ ├────────────┤ │ 526 │ └────────────┘ 运行时间（秒）：实际 0.000 用户 0.000190 系统 0.000082

第二部分

递归CTEflows本质上计算了二维洞穴网格上的连通分量（分量由高度为9的网格点分隔）。

关键优化：仅从第一部分找到的低点开始搜索连通分量（而不是从所有网格点开始）。参见递归CTEflows的初始查询q₀中cave和lowpoints的半连接。

用法：

在我的Mac Book Pro M2上大约需要30秒。

$ duckdb < smoke-basin-part2.sql ┌─────────┐ │ sizes │ │ int32 │ ├─────────┤ │ 1123524 │ └─────────┘ 运行时间（秒）：实际 30.636 用户 23.693674 系统 6.924345

-- AoC 2021, Day 9 (Part 2)-- AoC 输入文件DROPMACROIFEXISTSinput;CREATEMACRO input()AS'input.txt';-- 引入共享的SQL文件，包含高度图解析和低点计算.readsmoke-basin.sql-- 开启计时器，并设置单线程运行（确保结果确定性）.timeronSETthreads=1;WITHRECURSIVE-- 1. 为每个网格点分配一个唯一的盆地编号（basin），初始为行号cave(x,y,height,basin)AS(SELECTh.x,h.y,h.height,ROW_NUMBER()OVER()ASbasinFROMheightmapASh),-- 2. 递归CTE：模拟水流扩散，确定每个点属于哪个盆地flows(x,y,basin)AS(-- 初始查询：仅从低点开始扩散（优化关键）SELECTc.x,c.y,c.basinFROMcaveASc SEMIJOINlowpointsASlpON(c.y,c.x)=(lp.y,lp.x)UNIONALL-- 递归部分：从已访问点向四个相邻点扩散SELECTc.x,c.y,LEAST(f.basin,c.basin)ASbasinFROMflowsASf,caveAScWHERE(c.x,c.y)IN((f.x+1,f.y),(f.x-1,f.y),(f.x,f.y+1),(f.x,f.y-1))ANDc.height<9-- 只扩散到高度小于9的点（高度9为边界）),-- 3. 确定每个点的最终盆地编号（取扩散过程中遇到的最小编号）basins(x,y,basin)AS(SELECTf.x,f.y,MIN(f.basin)ASbasinFROMflowsASfGROUPBYf.y,f.x)-- 4. 计算前三大盆地大小的乘积SELECTPRODUCT(b.size)::intASsizesFROM(SELECTCOUNT(*)ASsizeFROMbasinsASbGROUPBYb.basin-- 按盆地分组统计大小ORDERBYsizeDESC-- 按大小降序排序LIMIT3)ASb;-- 取最大的三个盆地

SQL代码分析注释

1. caveCTE：

   • 为每个网格点(x, y)分配一个唯一的初始盆地编号basin（使用ROW_NUMBER()）。
   • 这为后续的盆地合并提供了初始标识。

2. flows递归CTE：

   • 初始查询：只从低点（lowpoints）开始扩散，这是性能优化的关键，避免从所有点开始搜索。
   • 递归查询：从已访问点向四个方向（上、下、左、右）扩散，但只扩散到高度< 9的点（因为高度9是盆地边界）。
   • LEAST(f.basin, c.basin)：在扩散过程中，始终保留遇到的最小盆地编号，确保同一盆地的所有点最终有相同编号。

3. basinsCTE：

   • 对flows的结果按点(x, y)分组，取最小的basin编号作为该点的最终盆地归属。

4. 最终查询：

   • 统计每个盆地的大小（点数）。
   • 按大小降序排序，取前三大的盆地。
   • 使用PRODUCT()函数计算这三个大小的乘积。
   • 结果转换为int类型输出。

算法思路总结

该SQL通过递归CTE实现了基于低点的洪水填充算法（Flood Fill）：

• 从每个低点开始，向四周扩散直到遇到高度9的边界。
• 扩散过程中合并盆地编号，确保同一盆地使用最小编号。
• 最后统计各盆地大小，计算最大三个的乘积。

优化点在于仅从低点开始扩散，避免了从所有点开始的不必要计算，大幅提升了性能。