AdventOfCode 2022 Day 18

作者

— Day 18: Boiling Boulders —

Part One

输入若干个立方体，计算这些立方体的表面积。

2,2,2
1,2,2
3,2,2

比较简单，只需要计算每个方块有多少个相邻即可

WITH origin AS (
  SELECT row_number() over () as rn, 
         split_part(line, ',', 1) :: INTEGER as x, 
         split_part(line, ',', 2) :: INTEGER as y, 
         split_part(line, ',', 3) :: INTEGER as z 
  FROM lance_input
)
SELECT (select COUNT(*) from origin) * 6 - sum(cnt)
FROM (
  SELECT m.rn, count(*) as cnt
  FROM origin m, origin n
  WHERE m.rn != n.rn
  AND ((m.x = n.x AND m.y = n.y AND abs(m.z - n.z) = 1) 
  OR (m.x = n.x AND m.z = n.z AND abs(m.y - n.y) = 1) 
  OR (m.y = n.y AND m.z = n.z AND abs(m.x - n.x) = 1))
  GROUP BY m.rn
) t

Part Two

方块内部有空气，空气接触的表面积需要剔除掉。

寻找内部空气

首先，输入只给了lava的方块，并没有给出空气的坐标。那么从全部坐标中，去除掉lava，剩余的均是空气

air AS (
  SELECT row_number() over () as seq, m.x, m.y, m.z
  FROM (
    SELECT x.rn as x, y.rn as y, z.rn as z
    FROM (select generate_series(0, (select max(x) from origin)) as rn) x, 
         (select generate_series(0, (select max(y) from origin)) as rn) y, 
         (select generate_series(0, (select max(z) from origin)) as rn) z
  ) m 
  LEFT JOIN origin n
  ON m.x = n.x 
  AND m.y = n.y
  AND m.z = n.z
  WHERE n.rn is null
)

既然判断一个空气是否在内部，那么上下左右前后6个方向上均有lava，可以判定空气属于内部

lava_air_mapping AS (
  SELECT m.rn as lava_seq, n.x, n.y, n.z, n.seq as air_seq,
         CASE WHEN m.y = n.y AND m.z = n.z AND m.x < n.x THEN 'L'
              WHEN m.y = n.y AND m.z = n.z AND m.x > n.x THEN 'R'
              WHEN m.x = n.x AND m.z = n.z AND m.y < n.y THEN 'D'
              WHEN m.x = n.x AND m.z = n.z AND m.y > n.y THEN 'U'
              WHEN m.x = n.x AND m.y = n.y AND m.z < n.z THEN 'F'
              WHEN m.x = n.x AND m.y = n.y AND m.z > n.z THEN 'B'
          END as pos
  FROM origin m, air n
), inner_air AS (
  SELECT air_seq, x, y, z
  FROM lava_air_mapping
  GROUP BY air_seq, x, y, z
  HAVING COUNT(distinct pos) = 6
)

找出与之相邻的面积数即可

WITH origin AS (
  SELECT row_number() over () as rn, 
         split_part(line, ',', 1) :: INTEGER as x, 
         split_part(line, ',', 2) :: INTEGER as y, 
         split_part(line, ',', 3) :: INTEGER as z 
  FROM lance_input
), air AS (
  SELECT row_number() over () as seq, m.x, m.y, m.z
  FROM (
    SELECT x.rn as x, y.rn as y, z.rn as z
    FROM (select generate_series(0, (select max(x) from origin)) as rn) x, 
         (select generate_series(0, (select max(y) from origin)) as rn) y, 
         (select generate_series(0, (select max(z) from origin)) as rn) z
  ) m 
  LEFT JOIN origin n
  ON m.x = n.x 
  AND m.y = n.y
  AND m.z = n.z
  WHERE n.rn is null
), lava_air_mapping AS (
  SELECT m.rn as lava_seq, n.x, n.y, n.z, n.seq as air_seq,
         CASE WHEN m.y = n.y AND m.z = n.z AND m.x < n.x THEN 'L'
              WHEN m.y = n.y AND m.z = n.z AND m.x > n.x THEN 'R'
              WHEN m.x = n.x AND m.z = n.z AND m.y < n.y THEN 'D'
              WHEN m.x = n.x AND m.z = n.z AND m.y > n.y THEN 'U'
              WHEN m.x = n.x AND m.y = n.y AND m.z < n.z THEN 'F'
              WHEN m.x = n.x AND m.y = n.y AND m.z > n.z THEN 'B'
          END as pos
  FROM origin m, air n
), inner_air AS (
  SELECT air_seq, x, y, z
  FROM lava_air_mapping
  GROUP BY air_seq, x, y, z
  HAVING COUNT(distinct pos) = 6
) 
SELECT COUNT(*)
FROM origin m 
JOIN inner_air n
ON ((m.x = n.x AND m.y = n.y AND abs(m.z - n.z) = 1) 
OR (m.x = n.x AND m.z = n.z AND abs(m.y - n.y) = 1) 
OR (m.y = n.y AND m.z = n.z AND abs(m.x - n.x) = 1))

可是，计算出来的接触面积明显偏大，应该是计算内部空气偏多了。很多不是内部的空气并计入了内部，因此之前的判断，6个方向上均有lava即为内部，这个判断很不准确。

寻找外部空气

那么换种思路，从外部空气着手，与之相邻的空气也是外部，计算出所有的外部，剩余的即为内部。

从最外缘着手，边界的空气肯定属于外部

  SELECT array_agg(seq) as arr, 0 as size
  FROM (
    SELECT seq
    FROM air
    WHERE x IN (0, (select max(x) from origin))
    OR y IN (0, (select max(y) from origin))
    OR z IN (0, (select max(z) from origin))
  ) t

后续的迭代，寻找与之相邻的空气方块，终止条件就是没有发现更新的空气节点了

   WITH new_outer_seq AS (
      SELECT z.seq
      FROM outer_seq x
      JOIN air y
      ON x.seq = y.seq
      JOIN air z
      ON ((y.x = z.x AND y.y = z.y AND abs(y.z - z.z) = 1) 
      OR (y.x = z.x AND y.z = z.z AND abs(y.y - z.y) = 1) 
      OR (y.y = z.y AND y.z = z.z AND abs(y.x - z.x) = 1))
      LEFT JOIN outer_seq o
      ON z.seq = o.seq
      WHERE o.seq IS NULL
    )

完整SQL为

WITH RECURSIVE origin AS (
  SELECT row_number() over () as rn, 
         split_part(line, ',', 1) :: INTEGER as x, 
         split_part(line, ',', 2) :: INTEGER as y, 
         split_part(line, ',', 3) :: INTEGER as z 
  FROM lance_input
), air AS (
  SELECT row_number() over () as seq, m.x, m.y, m.z
  FROM (
    SELECT x.rn as x, y.rn as y, z.rn as z
    FROM (select generate_series(0, (select max(x) from origin)) as rn) x, 
         (select generate_series(0, (select max(y) from origin)) as rn) y, 
         (select generate_series(0, (select max(z) from origin)) as rn) z
  ) m 
  LEFT JOIN origin n
  ON m.x = n.x 
  AND m.y = n.y
  AND m.z = n.z
  WHERE n.rn is null
), outer_air AS (
  SELECT array_agg(seq) as arr, 0 as size
  FROM (
    SELECT seq
    FROM air
    WHERE x IN (0, (select max(x) from origin))
    OR y IN (0, (select max(y) from origin))
    OR z IN (0, (select max(z) from origin))
  ) t

  UNION ALL

  SELECT arr, #arr as size
  FROM (
    WITH outer_seq AS (
      SELECT unnest(arr) as seq
      FROM outer_air
    ), new_outer_seq AS (
      SELECT z.seq
      FROM outer_seq x
      JOIN air y
      ON x.seq = y.seq
      JOIN air z
      ON ((y.x = z.x AND y.y = z.y AND abs(y.z - z.z) = 1) 
      OR (y.x = z.x AND y.z = z.z AND abs(y.y - z.y) = 1) 
      OR (y.y = z.y AND y.z = z.z AND abs(y.x - z.x) = 1))
      LEFT JOIN outer_seq o
      ON z.seq = o.seq
      WHERE o.seq IS NULL
    )
    SELECT array_agg(seq) :: INTEGER[] as arr
    FROM (
      SELECT seq FROM outer_seq
      UNION 
      SELECT seq FROM new_outer_seq
    ) t
    WHERE exists (select * from new_outer_seq)
  ) t
  WHERE #arr is not null
)
SELECT COUNT(*)
FROM origin m 
JOIN (
  SELECT m.seq, x, y, z
  FROM air m
  LEFT JOIN (SELECT unnest(arr) as seq from (select arr from outer_air order by size desc limit 1) n) n
  ON m.seq = n.seq
  WHERE n.seq IS NULL
) n
ON ((m.x = n.x AND m.y = n.y AND abs(m.z - n.z) = 1) 
OR (m.x = n.x AND m.z = n.z AND abs(m.y - n.y) = 1) 
OR (m.y = n.y AND m.z = n.z AND abs(m.x - n.x) = 1))

内部计算错误的原因

根据两种办法，发现有6个方块被错误地计算为内部。以(9, 20, 11)举例来说，其相邻的方块如下

x轴的lava
  rn  | x  | y  | z  
------+----+----+----
  478 |  7 | 20 | 11
 1381 | 10 | 20 | 11
  985 | 11 | 20 | 11
 1070 | 12 | 20 | 11
 1728 | 13 | 20 | 11

y轴的lava
  rn  | x | y  | z  
------+---+----+----
 1074 | 9 |  1 | 11
  640 | 9 |  2 | 11
  825 | 9 | 17 | 11
  691 | 9 | 18 | 11
  323 | 9 | 19 | 11
  837 | 9 | 21 | 11  

z轴的lava
  rn  | x | y  | z  
------+---+----+----
  744 | 9 | 20 | 10
 1005 | 9 | 20 | 12

问题就出在y轴，按照point in polygon的算法，y轴向上穿越一条边，向下穿越了两条边，因此并不算内部。

发表评论