AdventOfCode 2023 Day 18 – 天枢星的博客

Part One

一步步挖坑，算出最后坑有多大
R 6 (#70c710) D 5 (#0dc571) L 2 (#5713f0) D 2 (#d2c081) R 2 (#59c680)

和 Day 10 的例子很接近，同样是求多边形内部面积。现在只要将当前的输入，转换为Day 10的输入即可。

边界计算

trench AS (
  SELECT CASE WHEN x.direction = 'D' THEN 1 + y.id ELSE 1 END as _row,
         CASE WHEN x.direction = 'R' THEN 1 + y.id ELSE 1 END as _col,
         CASE WHEN x.direction = 'D' THEN 1 + x.len ELSE 1 END as current_row,
         CASE WHEN x.direction = 'R' THEN 1 + x.len ELSE 1 END as current_col,
         1 as seq
  FROM origin x, (SELECT id FROM seq LIMIT 100) y
  WHERE _row = 1
  AND x.len >= y.id

  UNION ALL

  SELECT CASE WHEN x.direction = 'D' THEN z.current_row + y.id WHEN x.direction = 'U' THEN z.current_row - y.id ELSE z.current_row END as _row,
         CASE WHEN x.direction = 'R' THEN z.current_col + y.id WHEN x.direction = 'L' THEN z.current_col - y.id ELSE z.current_col END as _col,
         CASE WHEN x.direction = 'D' THEN z.current_row + x.len WHEN x.direction = 'U' THEN z.current_row - x.len ELSE z.current_row END as current_row,
         CASE WHEN x.direction = 'R' THEN z.current_col + x.len WHEN x.direction = 'L' THEN z.current_col - x.len ELSE z.current_col END as current_col,
         z.seq as seq
  FROM origin x, 
      (SELECT id FROM seq LIMIT 100) y, 
      (SELECT seq + 1 as seq, current_row, current_col FROM trench LIMIT 1) z
  WHERE _row = z.seq
  AND x.len >= y.id
)

这里有个陷阱，起点并不是(1,1)，因此计算出来的ROW和COL可能是负数，需要校准下。

trans_trench AS (
  SELECT _row - (select min(_row) from trench) + 1 as _row, 
         _col - (select min(_col) from trench) + 1 as _col, 
         seq
  FROM trench
)

转换迷宫

将之前的输入，转换为 Day 12 的输入。将转角处修改为LJF7，将其他的边修改为-｜

replaced_trench AS (
  SELECT _row, _col,
         CASE WHEN neighbors = 'LR' THEN '-'
              WHEN neighbors = 'DU' THEN '|'
              WHEN neighbors = 'DL' THEN '7'
              WHEN neighbors = 'LU' THEN 'J'
              WHEN neighbors = 'RU' THEN 'L'
              WHEN neighbors = 'DR' THEN 'F'
         END as pos
  FROM (
    SELECT _row, _col, string_agg(neighbor, '' ORDER BY neighbor) as neighbors
    FROM (
      SELECT a._row, a._col, 
             case when a._row = b._row AND a._col = b._col + 1 THEN 'L'
                  when a._row = b._row AND a._col = b._col - 1 THEN 'R'
                  when a._row = b._row + 1 AND a._col = b._col THEN 'U'
                  when a._row = b._row - 1 AND a._col = b._col THEN 'D'
             end as neighbor
      FROM trans_trench a
      JOIN trans_trench b
      ON a._row = b._row AND a._col = b._col + 1
      OR a._row = b._row AND a._col = b._col - 1
      OR a._row = b._row + 1 AND a._col = b._col
      OR a._row = b._row - 1 AND a._col = b._col
    ) t
    GROUP BY _row, _col
  ) s
), 
maze AS (
  SELECT x._row, y._col, coalesce(trench.pos, '.') as pos
  FROM (SELECT id as _row FROM seq LIMIT (SELECT max(_row) from replaced_trench)) x 
  JOIN (SELECT id as _col FROM seq LIMIT (SELECT max(_col) from replaced_trench)) y
  ON 1 = 1
  LEFT JOIN replaced_trench trench 
  ON x._row = trench._row
  AND y._col = trench._col
)

后续计算

后续的处理同 Day 10 的处理，处理后的记录如下图所示

rows AS (
  SELECT _row, replace(replace(replace(replace(replace(formatted_row, '-', ''), 'LJ', ''), 'F7', ''), 'L7', '|'), 'FJ', '|') as replaced_row
  FROM (
    SELECT m._row, string_agg(m.pos, '' order by m._col) as formatted_row
    FROM maze m
    group by m._row
  ) t
)
SELECT COUNT(*) + (SELECT COUNT(*) FROM trench)
FROM (
  SELECT substring(x.replaced_row, 1, y.id - 1) as left_str
  FROM rows x, (select id from seq limit (select max(length(replaced_row)) from rows)) y
  WHERE substring(x.replaced_row, y.id, 1) = '.' and y.id > 1
) t
WHERE (length(left_str) - length(replace(left_str, '|', ''))) % 2 = 1;

Part Two

第二关，长度变成超大数字，规则未变。
#70c710 = R 461937 #0dc571 = D 56407 #5713f0 = R 356671 #d2c081 = D 863240

由于长度变成超大数字，使用第一关的方法就不太可行了，计算量会非常巨大。因此需要换个思路，第一关是判断某个点是不是在坑内，然后求出所有点的总和。可以将总体的面积分割多多个长方形，每个长方形内找一个点来判断是不是内部，如果是则整个长方形都在内部，直接求长方形面积即可。

分割为长方形

如上图所示，将多变形按照经纬线进行切割，切割为若干个长方形。每个长方形只要内部找一个点来判断是否为内部即可。

先计算出所有长方形的左上顶点

WITH RECURSIVE origin AS (
  SELECT _row, 
         CASE WHEN substring(line, 7, 1) = '0' THEN 'R'
              WHEN substring(line, 7, 1) = '1' THEN 'D'
              WHEN substring(line, 7, 1) = '2' THEN 'L'
              WHEN substring(line, 7, 1) = '3' THEN 'U'
         END as direction, 
         ('x'||lpad(substring(line, 2, 5),16,'0'))::bit(64)::bigint as len
  FROM (
    SELECT row_number() over () as _row, (regexp_match(line, '\((.*)\)'))[1] as line
    FROM lance_input
  ) t
),
trench AS (
  SELECT 1 :: BIGINT as start_row,
         1 :: BIGINT as start_col,
         CASE WHEN x.direction = 'D' THEN 1 + x.len ELSE 1 END as end_row,
         CASE WHEN x.direction = 'R' THEN 1 + x.len ELSE 1 END as end_col,
         1 as seq,
         CASE WHEN x.direction IN ('D', 'U') THEN '|' ELSE '-' END as border
  FROM origin x
  WHERE _row = 1

  UNION ALL

  SELECT y.end_row as start_row,
         y.end_col as start_col,
         CASE WHEN x.direction = 'D' THEN y.end_row + x.len WHEN x.direction = 'U' THEN y.end_row - x.len ELSE y.end_row END as end_row,
         CASE WHEN x.direction = 'R' THEN y.end_col + x.len WHEN x.direction = 'L' THEN y.end_col - x.len ELSE y.end_col END as end_col,
         y.seq as seq,
         CASE WHEN x.direction IN ('D', 'U') THEN '|' ELSE '-' END as border
  FROM origin x, 
      (SELECT seq + 1 as seq, end_row, end_col FROM trench) y
  WHERE _row = y.seq
),
vertex_row AS (
  SELECT _row, lead(_row) over (order by _row) as next_row
  FROM (
    SELECT start_row as _row FROM trench
    UNION
    SELECT end_row as _row FROM trench
  ) t
),
vertex_col AS (
  SELECT _col, lead(_col) over (order by _col) as next_col
  FROM (
    SELECT start_col as _col FROM trench
    UNION
    SELECT end_col as _col FROM trench
  ) t
),
vertex AS (
  SELECT _row, _col, next_row, next_col
  FROM vertex_row, vertex_col
  WHERE next_row IS NOT NULL
  AND next_col IS NOT NULL
)

  _row  |  _col  | next_row | next_col 
--------+--------+----------+----------
      1 |      1 |    56408 |     5412
      1 |   5412 |    56408 |   461938
      1 | 461938 |    56408 |   497057
      1 | 497057 |    56408 |   609067
      1 | 609067 |    56408 |   818609
      1 | 818609 |    56408 |  1186329

然后，在一个长方形找一个点来判断是否为内部，为了简单起见，直接用(r+1, c+1)这个点来判断。

vertex_calculate AS (
  SELECT x._row, x._col, x.next_row, x.next_col
  FROM vertex x, trench y
  WHERE least(y.start_row, y.end_row) < x._row + 1 AND greatest(y.start_row, y.end_row) > x._row + 1
  AND y.start_col < x._col + 1
  AND y.border = '|'
  GROUP BY x._row, x._col, x.next_row, x.next_col
  HAVING COUNT(*) % 2 = 1
)

面积计算

因为多边形的边也是计算面积的，而多个长方形又是相邻的，直接长方形面积相加会导致结果变大。因此，面积这块需要考虑不要重复计算。

在面积计算的时候，可以将长方形分为三部分。

首先是非相邻的内部面积，即灰色面积部分， (length – 2) * (height – 2)。
其次是相邻的边，去掉顶点，即黄色面积部分，(length – 2) * N，需要去重。
最后是长方形的顶点，即蓝色面积部分，1 * N，需要去重。

interior_size AS (
  SELECT SUM((next_row - _row - 1) * (next_col - _col - 1)) as size
  FROM vertex_calculate
),
edge_size AS (
  SELECT SUM(len) as size
  FROM (
    SELECT _row || ',' || _col || '-' || _row || ',' || next_col as edge, next_col - _col - 1 as len
    FROM vertex_calculate
    UNION
    SELECT _row || ',' || _col || '-' || next_row || ',' || _col as edge, next_row - _row - 1 as len
    FROM vertex_calculate
    UNION
    SELECT next_row || ',' || _col || '-' || next_row || ',' || next_col as edge, next_col - _col - 1 as len
    FROM vertex_calculate
    UNION
    SELECT _row || ',' || next_col || '-' || next_row || ',' || next_col as edge, next_row - _row - 1 as len
    FROM vertex_calculate
  ) t
),
vertex_size AS (
  SELECT COUNT(*) as size
  FROM (
    SELECT _row || ',' || _col as vertex
    FROM vertex_calculate
    UNION
    SELECT _row || ',' || next_col as vertex
    FROM vertex_calculate
    UNION
    SELECT next_row || ',' || _col as vertex
    FROM vertex_calculate
    UNION
    SELECT next_row || ',' || next_col as vertex
    FROM vertex_calculate
  ) t
)

postgres-# SELECT * from interior_size,edge_size,vertex_size;
      size      |    size    | size  
----------------+------------+-------
 52882789128868 | 2595796528 | 30486
(1 row)