AdventOfCode 2025 Day 11

作者

— Day 11: Reactor —

Part One

aaa: you hhh
you: bbb ccc
bbb: ddd eee
ccc: ddd eee fff
ddd: ggg
eee: out
fff: out
ggg: out
hhh: ccc fff iii
iii: out

根据上述的规划路径，找出you -> out的所有路径数

with recursive origin as (
    SELECT t.device, s.target
    FROM (
        SELECT split_part(line, ': ', 1) as device, 
               split_part(line, ': ', 2) as targets
        FROM lance_input
    ) t, regexp_split_to_table(targets, ' ') as s(target) 
), all_path as (
    SELECT device, target, array[device, target] as path
    FROM origin 
    WHERE device = 'you'

    UNION ALL

    SELECT a.device, b.target, path || b.target as path
    FROM all_path a
    JOIN origin b
    ON a.target = b.device
    AND b.target != ANY(path)
    AND a.target != 'out'
)
SELECT * from all_path;

Part Two

不仅要找出svr -> out的所有路径，还要求比如经过fft和dac两个节点

目标就是找出三段的路径数，svr -> fft -> dac -> out，相乘即可。

但是Part One的方式，计算量太大，无法计算出最终的结果。还是用递归函数的方式，并缓存所有节点之间的路径数。

用一张表，来保存所有节点之间的路径数。

create table device_path as 
with origin as (
    SELECT t.device, s.target, 1 :: bigint as path
    FROM (
        SELECT split_part(line, ': ', 1) as device, 
               split_part(line, ': ', 2) as targets
        FROM lance_input
    ) t, regexp_split_to_table(targets, ' ') as s(target) 
)
select * from origin;

create index idx_device_path on device_path(device, target);

再创建一个递归函数

CREATE OR REPLACE FUNCTION calculate_device_path(_source text, _target text)
RETURNS BIGINT AS $$
DECLARE
    _path bigint;
    _targets varchar[];
BEGIN
    -- find from cache
    _path := (select path from device_path where device = _source and target = _target);

    IF _path IS NULL THEN
        _targets := (
            SELECT array_agg(target) from device_path where device = _source and path > 0
        );

        IF _targets IS NULL THEN
            _path := 0;
        ELSE
            _path := 0;
            FOR i in 1..array_length(_targets, 1) LOOP
                _path := _path + calculate_device_path(_targets[i], _target);
            END LOOP;
        END IF;

        -- insert into cache
        INSERT INTO device_path values(_source, _target, _path);
    ELSE
        RETURN _path;
    END IF;

    RETURN _path;
END;
$$ LANGUAGE plpgsql;

发表评论