这是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代码分析注释
caveCTE：- 为每个网格点
(x, y)分配一个唯一的初始盆地编号basin（使用ROW_NUMBER()）。 - 这为后续的盆地合并提供了初始标识。
- 为每个网格点
flows递归CTE：- 初始查询：只从低点（
lowpoints）开始扩散，这是性能优化的关键，避免从所有点开始搜索。 - 递归查询：从已访问点向四个方向（上、下、左、右）扩散，但只扩散到高度
< 9的点（因为高度9是盆地边界）。 LEAST(f.basin, c.basin)：在扩散过程中，始终保留遇到的最小盆地编号，确保同一盆地的所有点最终有相同编号。
- 初始查询：只从低点（
basinsCTE：- 对
flows的结果按点(x, y)分组，取最小的basin编号作为该点的最终盆地归属。
- 对
最终查询：
- 统计每个盆地的大小（点数）。
- 按大小降序排序，取前三大的盆地。
- 使用
PRODUCT()函数计算这三个大小的乘积。 - 结果转换为
int类型输出。
算法思路总结
该SQL通过递归CTE实现了基于低点的洪水填充算法（Flood Fill）：
- 从每个低点开始，向四周扩散直到遇到高度9的边界。
- 扩散过程中合并盆地编号，确保同一盆地使用最小编号。
- 最后统计各盆地大小，计算最大三个的乘积。
优化点在于仅从低点开始扩散，避免了从所有点开始的不必要计算，大幅提升了性能。
