AdventOfCode 2024 Day 5

作者

— Day 5: Print Queue —

Part One

第一部分提供数字的输出顺序，比如严格按照这里的先后顺序；第二部分提供了输出的数字列表，其中某些行顺序不正确。

75|13
53|13

75,47,61,53,29
97,61,53,29,13

分别解析出第一部分和第二部分的数据

with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), ordering_rule as (
    SELECT rn, split_part(line, '|', 1) :: INTEGER as l, split_part(line, '|', 2) :: INTEGER as r
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), updating_record as (
    SELECT rn, x.item :: INTEGER, x.idx
    FROM origin, regexp_split_to_table(line, ',') with ordinality as x(item, idx)
    WHERE rn > (select rn from origin where line is null)
)

然后简单地过滤掉次序对不上的记录，剩余的正确记录求出中间数字即可。

correct_order as (
    SELECT *
    FROM updating_record
    WHERE rn not in (
        SELECT b.rn
        FROM ordering_rule a
        JOIN updating_record b
        ON a.l = b.item
        JOIN updating_record c
        ON a.r = c.item
        WHERE b.rn = c.rn
        AND b.idx > c.idx
    )
)
SELECT sum(path[((#path) + 1) / 2])
FROM (
    SELECT array_agg(item) as path
    FROM correct_order
    GROUP BY rn
) t

Part Two

次序不对的数字组合，需要按照正确的次序排序

75,97,47,61,53 becomes 97,75,47,61,53.

61,13,29 becomes 61,29,13.

97,13,75,29,47 becomes 97,75,47,29,13

全局顺序

首先尝试将第一部分的顺序，进行递归查询后，求出全局的顺序，参见之前的blog。

但是发现这些数字之间形成了环，并没有起点。

with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), ordering_rule as (
    SELECT rn, split_part(line, '|', 1) :: INTEGER as l, split_part(line, '|', 2) :: INTEGER as r
    FROM origin
    WHERE rn < (select rn from origin where line is null)
)
SELECT l
FROM ordering_rule
WHERE l NOT IN (SELECT r FROM ordering_rule);

 l 
---
(0 rows)

组合内顺序

既然没有全局顺序，那么可以尝试下一个组合内的数字，这个必然会有先后顺序，否则无法给出最终结果。

下面的SQL说明，在这个组合中，37的上游都非组合内数字，可以作为这个组合的第一个数字

with recursive origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), ordering_rule as (
    SELECT rn, split_part(line, '|', 1) :: INTEGER as l, split_part(line, '|', 2) :: INTEGER as r
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), sub_ordering_rule as (
    SELECT *
    FROM ordering_rule
    WHERE r IN (81,74,28,18,98,82,55,29,53,86,24,65,37)
)
SELECT r
FROM sub_ordering_rule
GROUP BY r
HAVING NOT array_agg(l) && ARRAY[81,74,28,18,98,82,55,29,53,86,24,65,37];

 r  
----
 37
(1 row)

那么第二个数字，应该就是上游除了37，没有组合内的其他数字，因此29作为第二个数字。

SELECT r
FROM sub_ordering_rule
GROUP BY r
HAVING NOT array_agg(l) && ARRAY[81,74,28,18,98,82,55,29,53,86,24,65];

 r  
----
 29
 37
(2 rows)

最终SQL

with recursive origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), ordering_rule as (
    SELECT rn, split_part(line, '|', 1) :: INTEGER as l, split_part(line, '|', 2) :: INTEGER as r
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), updating_record as (
    SELECT rn, x.item :: INTEGER, x.idx
    FROM origin, regexp_split_to_table(line, ',') with ordinality as x(item, idx)
    WHERE rn > (select rn from origin where line is null)
), wrong_record as (
    SELECT *
    FROM updating_record
    WHERE rn in (
        SELECT b.rn
        FROM ordering_rule a
        JOIN updating_record b
        ON a.l = b.item
        JOIN updating_record c
        ON a.r = c.item
        WHERE b.rn = c.rn
        AND b.idx > c.idx
    )
), parent_agg as (
    SELECT b.rn, b.item, array_agg(a.item) as parent_items
    FROM wrong_record a
    JOIN wrong_record b
    ON a.rn = b.rn
    JOIN ordering_rule c
    ON a.item = c.l
    AND b.item = c.r
    GROUP by b.rn, b.item
), correct_order as (
    SELECT a.rn, array[a.item] as path
    FROM wrong_record a
    LEFT JOIN parent_agg b
    ON a.rn = b.rn
    AND a.item = b.item
    WHERE b.rn is null

    UNION ALL

    SELECT a.rn, path || b.item as path
    FROM correct_order a
    JOIN parent_agg b
    ON a.rn = b.rn
    AND a.path @> b.parent_items
    AND NOT b.item = ANY(path)
) 
SELECT sum(path[((#path) + 1) / 2])
FROM (
    SELECT rn, path, row_number() over(partition by rn order by #path desc) as rn
    FROM correct_order
) t
WHERE rn = 1

更简单的做法？

按照parent的个数排序，直接可以得出最终的顺序。

postgres(# ) select * From parent_agg where rn = 1273 order by #parent_items;
  rn  | item |                      parent_items                       
------+------+---------------------------------------------------------
 1273 |   51 | {13}
 1273 |   37 | {13,51}
 1273 |   36 | {37,13,51}
 1273 |   19 | {37,51,13,36}
 1273 |   29 | {13,19,51,36,37}
 1273 |   53 | {37,19,13,51,29,36}
 1273 |   12 | {29,13,19,36,37,53,51}
 1273 |   81 | {29,36,53,12,19,37,51,13}
 1273 |   86 | {19,29,81,53,37,12,13,51,36}
 1273 |   39 | {81,86,13,36,19,12,37,51,29,53}
 1273 |   65 | {39,13,19,36,53,81,12,86,37,51,29}
 1273 |   91 | {53,12,65,37,39,36,29,86,13,81,19,51}
 1273 |   82 | {36,13,37,12,39,65,53,86,29,51,81,19,91}
 1273 |   47 | {36,12,19,51,65,53,39,82,29,37,81,91,86,13}
 1273 |   98 | {19,36,47,53,86,82,91,81,12,39,29,65,51,13,37}
 1273 |   96 | {51,86,29,53,82,81,13,36,39,65,12,47,19,98,91,37}
 1273 |   24 | {53,86,81,19,13,29,36,91,82,39,65,37,98,12,47,96,51}
 1273 |   57 | {36,51,12,96,98,81,37,65,24,19,47,53,39,82,13,29,91,86}
(18 rows)

发表评论