AdventOfCode 2023 Day 22

作者

Day 22: Sand Slabs

Part One

叠积木的游戏，输入并不是最终的形态，而是下落过程中的snapshot。需要计算出下落到终态情况下，哪些积木是不能抽出的。输入是一个积木的三维空间范围，分别是x/y/z三个方向的坐标。

1,0,1~1,2,1
0,0,2~2,0,2
0,2,3~2,2,3
0,0,4~0,2,4
2,0,5~2,2,5
0,1,6~2,1,6
1,1,8~1,1,9

终态计算

输入的三维坐标，xy方向是9*9范围内的起点、终点，可能是1 * 3或者3 * 1的方格，需要分拆为1*1的方格，从而方便判断积木之间的堆叠关系。z_order，就是某个坐标点(x,y)的垂直方向上的顺序。

WITH RECURSIVE seq AS (
  SELECT 0 as id 
  UNION ALL
  SELECT id + 1 as id
  FROM seq
), 
cube AS (
  SELECT _row, 
         split_part(start, ',', 1) :: integer as start_x, split_part(start, ',', 2) :: integer as start_y, split_part(start, ',', 3) :: integer as start_z, 
         split_part(finish, ',', 1) :: integer as finish_x, split_part(finish, ',', 2) :: integer as finish_y, split_part(finish, ',', 3) :: integer as finish_z
  FROM (
    SELECT row_number() over () as _row, split_part(line, '~', 1) as start, split_part(line, '~', 2) as finish
    FROM lance_input
  ) t
),
split_cube AS (
  SELECT _row, _x, _y, start_z, finish_z, row_number() over (partition by _x, _y order by start_z) as z_order
  FROM (
    SELECT _row, x.id as _x, y.id as _y, start_z, finish_z
    FROM cube, (select id from seq limit 10) x, (select id from seq limit 10) y
    WHERE start_x <= x.id and x.id <= finish_x
    AND start_y <= y.id and y.id <= finish_y
  ) t
)

接下来需要计算最终落地后，每个积木在“第几层”，从而计算出每个积木的最终起点高度。

比如这样的例子

CCC
BD
BE
AAA

第一层：A
第二层：B、E
第三层：D（因为C的下一层D还未出现）
第四层：C

CREATE OR REPLACE FUNCTION stack()
RETURNS VOID AS $$
DECLARE
    remain_cnt INTEGER;
BEGIN

    -- first level
    INSERT INTO RESULT
    SELECT _row, 1 as start_z, finish_z - start_z + 1 as finish_z, 1 as level
    FROM cube
    WHERE NOT EXISTS (select 1 FROM split_cube x where x._row = cube._row and x.z_order > 1);

    WHILE true LOOP

      SELECT COUNT(*) 
      FROM (
        SELECT _row, 
               split_part(start, ',', 1) :: integer as start_x, split_part(start, ',', 2) :: integer as start_y, split_part(start, ',', 3) :: integer as start_z, 
               split_part(finish, ',', 1) :: integer as finish_x, split_part(finish, ',', 2) :: integer as finish_y, split_part(finish, ',', 3) :: integer as finish_z
        FROM (
          SELECT row_number() over () as _row, split_part(line, '~', 1) as start, split_part(line, '~', 2) as finish
          FROM lance_input
        ) t
      ) s 
      WHERE s._row NOT IN (select _row from result) INTO remain_cnt;

      EXIT WHEN remain_cnt = 0;

      INSERT INTO result
      SELECT _row, pre_finish_z + 1 as start_z, pre_finish_z + height as finish_z, level + 1 as level
      FROM (
        SELECT x._row, x.finish_z - x.start_z + 1 as height, max(level) as level, max(z.finish_z) as pre_finish_z
        FROM split_cube x
        JOIN split_cube y
        ON x._x = y._x
        AND x._y = y._y
        AND x.z_order = y.z_order + 1
        LEFT JOIN result z 
        ON y._row = z._row
        WHERE x._row not in (select _row from result)
        GROUP BY x._row, x.finish_z - x.start_z + 1
        HAVING count(*) = COUNT(z._row)
      ) t;

    END LOOP;
END;
$$ LANGUAGE plpgsql;

这样就计算出了所有积木的终态，以及终态时的高度

postgres=# select * From result;
 _row | start_z | finish_z | level 
------+---------+----------+-------
   39 |       1 |        1 |     1
   75 |       1 |        1 |     1
   77 |       1 |        1 |     1
  195 |       1 |        3 |     1
  212 |       1 |        1 |     1
  222 |       1 |        4 |     1
  227 |       1 |        1 |     1

支撑柱查找

接下来，就是查询哪些积木是单独的支撑柱，从而确定这些积木是无法抽出的。

比如这样的例子
CCC
B
BD
AAA

虽然CCC下面有B和D两个积木，但是支撑柱只有B，D并未支撑

支撑柱的条件可以概括为：

  • split_cube中的z_order相邻
  • 下层level的finish_z和上层level的start_z相邻
  • 上层level的积木仅有一个下层level的积木支撑
SELECT distinct unnest(down_cubes)
FROM (
  SELECT t.up, array_agg(t.down) as down_cubes
  FROM (
    SELECT DISTINCT up._row as up, down._row as down
    FROM split_cube up
    JOIN split_cube down
    ON up._x = down._x
    AND up._y = down._y
    AND up.z_order = down.z_order + 1
  ) t
  JOIN result m
  ON t.up = m._row
  JOIN result n
  ON t.down = n._row
  WHERE n.finish_z + 1 = m.start_z
  GROUP BY t.up
  HAVING COUNT(*) = 1
) t;

上述SQL的结果，就是所有单独支撑柱的集合。排除掉这些支撑柱，剩下的就是可以抽出的。

Part Two

每个支撑柱都会导致chain reaction，计算每个支撑柱会导致多少积木的下落。

For each brick, determine how many other bricks would fall if that brick were disintegrated.
比如这样的例子
DDD
CE
BE
AAA
当抽出A的时候，B、C、E、D都会下落

DDD
CE
BE
AE
当抽出A的时候，仅有B、C都会下落

上下层关系

通过构建上下层关系，当下层积木被全部抽出后，上层积木就会下落，从而触发新一轮的下落。

up_down AS ( 
      SELECT t.up, array_agg(t.down) :: integer[] as down_cubes
      FROM (
        SELECT DISTINCT up._row as up, down._row as down
        FROM split_cube up
        JOIN split_cube down
        ON up._x = down._x
        AND up._y = down._y
        AND up.z_order = down.z_order + 1
      ) t
      JOIN result m
      ON t.up = m._row
      JOIN result n
      ON t.down = n._row
      WHERE n.finish_z + 1 = m.start_z
      GROUP BY t.up
    )

计算单个积木影响的其他积木

计算的起点，是积木本身。通过两个标记位来辅助计算，disintegrated代表积木是否被抽走，new代表是否是上一轮迭代新增的积木。如果没有new了，则代表没有新的可抽走的积木了，无需继续迭代了。

cube AS (
      SELECT _row, 
             case when _row = row_seq then true else false end as disintegrated, 
             case when _row = row_seq then true else false end as new, 
             1 as step
      FROM result

      UNION ALL

      SELECT *
      FROM (
        WITH cube_inner as (select * from cube)
        SELECT x._row, 
               case when y._row is not null then true else x.disintegrated end as disintegrated,
               case when not x.new and not disintegrated and y._row is not null then true else false end as new,
               x.step + 1 as step
        FROM cube_inner x
        LEFT JOIN (
          SELECT up as _row
          FROM up_down x, 
               (SELECT array_agg(_row) as all_cubes FROM cube_inner where disintegrated) y
          WHERE #(down_cubes - y.all_cubes) = 0
        ) y
        ON x._row = y._row
        WHERE exists (select _row from cube_inner where new)
      ) t
    )

最终SQL

CREATE OR REPLACE FUNCTION disintegrate(row_seq INTEGER)
RETURNS INTEGER AS $$
DECLARE
    disintegrated_cnt INTEGER;
BEGIN
    WITH RECURSIVE up_down AS ( 
      SELECT t.up, array_agg(t.down) :: integer[] as down_cubes
      FROM (
        SELECT DISTINCT up._row as up, down._row as down
        FROM split_cube up
        JOIN split_cube down
        ON up._x = down._x
        AND up._y = down._y
        AND up.z_order = down.z_order + 1
      ) t
      JOIN result m
      ON t.up = m._row
      JOIN result n
      ON t.down = n._row
      WHERE n.finish_z + 1 = m.start_z
      GROUP BY t.up
    ),
    cube AS (
      SELECT _row, 
             case when _row = row_seq then true else false end as disintegrated, 
             case when _row = row_seq then true else false end as new, 
             1 as step
      FROM result

      UNION ALL

      SELECT *
      FROM (
        WITH cube_inner as (select * from cube)
        SELECT x._row, 
               case when y._row is not null then true else x.disintegrated end as disintegrated,
               case when not x.new and not disintegrated and y._row is not null then true else false end as new,
               x.step + 1 as step
        FROM cube_inner x
        LEFT JOIN (
          SELECT up as _row
          FROM up_down x, 
               (SELECT array_agg(_row) as all_cubes FROM cube_inner where disintegrated) y
          WHERE #(down_cubes - y.all_cubes) = 0
        ) y
        ON x._row = y._row
        WHERE exists (select _row from cube_inner where new)
      ) t
    )
    SELECT count(distinct _row) FROM cube where disintegrated INTO disintegrated_cnt;
    RETURN disintegrated_cnt;
    
END;
$$ LANGUAGE plpgsql;

postgres=# select sum(disintegrate(_row) - 1)  from result;
  sum  
-------
 61045

发表评论