AdventOfCode 2023 Day 8

作者

Day 8: Haunted Wasteland

Part One

根据第一行的方向，从AAA路由到ZZZ

RL
AAA = (BBB, CCC)
BBB = (DDD, EEE)

第一部分比较简单，简单的从AAA持续路由下去，直到ZZZ终止。

WITH recursive rule AS (
  SELECT line 
  FROM lance_input
  LIMIT 1
), 
origin AS (
  SELECT key, substring(lr, 2, 3) as l, substring(lr, 7, 3) as r
    FROM (
    SELECT line, trim(split_part(line, ' = ', 1)) as key, trim(split_part(line, ' = ', 2)) as lr
    FROM lance_input
    OFFSET 2
  ) t
), 
path AS (
  SELECT key, case when direction = 'L' then l when direction = 'R' then r end as next_key, 1 as step, direction
  FROM (
    SELECT key, l, r, substring(line, 1, 1) as direction
    FROM origin, rule
    WHERE key = 'AAA'
    LIMIT 1
  ) t

  UNION ALL

  SELECT key, case when substring(line, idx, 1) = 'L' then l when substring(line, idx, 1) = 'R' then r end as next_key, step + 1 as step, substring(line, idx, 1)
  FROM (
    SELECT x.key, x.l, x.r, y.step % length(line)  + 1 as idx, line, step
    FROM origin x
    JOIN path y
    ON x.key = y.next_key
    AND y.next_key != 'ZZZ'
    JOIN rule
    ON 1 = 1
  ) t
)
SELECT * FROM PATH;

Part Two

从多个A结尾的起点，路由到每个终点都是Z结尾

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)

Multiple Origins

起点是多条记录，迭代的终止条件，就是所有的key都是Z结尾。这里需要使用到sum over的开窗函数

WITH p AS (
      SELECT *, sum(1) over () as total, 
                sum(CASE WHEN next_key like '%Z' THEN 1 ELSE 0 END) over () as zcnt 
      FROM PATH
)

完整SQL如下所示：

WITH recursive rule AS (
  SELECT line 
  FROM lance_input
  LIMIT 1
), 
origin AS (
  SELECT key, substring(lr, 2, 3) as l, substring(lr, 7, 3) as r
    FROM (
    SELECT line, trim(split_part(line, ' = ', 1)) as key, trim(split_part(line, ' = ', 2)) as lr
    FROM lance_input
    OFFSET 2
  ) t
), 
path AS (
  SELECT key, case when direction = 'L' then l when direction = 'R' then r end as next_key, 1 as step, direction
  FROM (
    SELECT key, l, r, substring(line, 1, 1) as direction
    FROM origin, rule
    WHERE key like '%A'
  ) t

  UNION ALL

  SELECT key, case when substring(line, idx, 1) = 'L' then l when substring(line, idx, 1) = 'R' then r end as next_key, step + 1 as step, substring(line, idx, 1)
  FROM (
    WITH p AS (
      SELECT *, sum(1) over () as total, sum(CASE WHEN next_key like '%Z' THEN 1 ELSE 0 END) over () as zcnt 
      FROM PATH
    )
    SELECT x.key, x.l, x.r, y.step % length(line)  + 1 as idx, line, step
    FROM origin x
    JOIN p y
    ON x.key = y.next_key
    AND y.total != y.zcnt
    JOIN rule
    ON 1 = 1
  ) t
)
SELECT * FROM PATH;

 key | next_key | step | direction 
-----+----------+------+-----------
 11A | 11B      |    1 | L
 22A | 22B      |    1 | L
 11B | 11Z      |    2 | R
 22B | 22C      |    2 | R
 11Z | 11B      |    3 | L
 22C | 22Z      |    3 | L
 11B | 11Z      |    4 | R
 22Z | 22B      |    4 | R
 11Z | 11B      |    5 | L
 22B | 22C      |    5 | L
 11B | 11Z      |    6 | R
 22C | 22Z      |    6 | R
(12 rows)

Endless Iterations

但是在真正运行的时候，运行了很长时间都没有结果。运行了千万都还没有结束。

postgres-# SELECT * FROM PATH limit 1 offset 10000000;
 key | next_key |  step   | direction 
-----+----------+---------+-----------
 GLV | MDV      | 1666667 | L
(1 row)

那就以其中一个A为起点，看看中途到底是否经历过Z

AAA起点的记录

 key | next_key | step  | direction 
-----+----------+-------+-----------
 PLJ | ZZZ      | 20221 | R
 PLJ | ZZZ      | 40442 | R
 PLJ | ZZZ      | 60663 | R
 PLJ | ZZZ      | 80884 | R
(4 rows)

HCA起点的记录

 key | next_key | step  | direction 
-----+----------+-------+-----------
 MJM | MTZ      | 18559 | R
 MJM | MTZ      | 37118 | R
 MJM | MTZ      | 55677 | R
 MJM | MTZ      | 74236 | R
 MJM | MTZ      | 92795 | R
(5 rows)

明显看出，A开头的Z结尾，形成了一个循环，看来输入是故意这么设计的。Steps以L开始，R结尾。第一步A的mapping和最后Z的mapping恰好相反，从而在下一个循环中保证后续Steps是相同的。

Steps的总长度是277，而20221、18559这些恰好是277的倍数。

AAA = (QXT, CDL)
ZZZ = (CDL, QXT)

HCA = (LJP, GVX)
MTZ = (GVX, LJP)

LCM(Least Common Multiple)

那只要求出每个A的循环Steps长度的最小公倍数，在那一步的时候，所有的下一步都是Z结尾。

postgres-# SELECT next_key,step, step / 277 from (SELECT * FROM PATH limit 1000000) t where next_key like '%Z' order by 2;
 next_key |  step  | ?column? 
----------+--------+----------
 FPZ      |  13019 |       47
 MLZ      |  14681 |       53
 DPZ      |  16897 |       61
 MTZ      |  18559 |       67
 CPZ      |  19667 |       71
 ZZZ      |  20221 |       73

47 * 53 * 61 * 67 * 71 * 73 * 277

发表评论