AdventOfCode 2024 Day 23

Part One

根据电脑两两连接的信息,类似a<->b, c<->b,推断出三个电脑互相连接的场景

首先拆分出两两相连的情况,为了方便计算,强行让左侧小于右侧,再通过自关联求出三个电脑互联的场景

with origin AS (
    SELECT least(split_part(line, '-', 1), split_part(line, '-', 2)) as l, 
           greatest(split_part(line, '-', 1), split_part(line, '-', 2)) as r
    FROM lance_input
)
SELECT count(*)
FROM (
    SELECT distinct a.l, a.r, c.r
    FROM origin a
    JOIN origin b
    ON a.r = b.l
    JOIN origin c
    ON a.l = c.l
    AND b.r = c.r
    WHERE left(a.l, 1) = 't' 
    OR left(a.r, 1) = 't' 
    OR left(c.r, 1) = 't'
) t;

Part Two

一个LAN中可能不止三台电脑,求出一个LAN中最多的电脑组合

那么如何确定一个LAN中每台电脑都互联呢?上一题中3台电脑就需要关联3次,来确保每台都互联。电脑越多,需要关联的次数越多,计算量太大。

目前已知的条件,可以看作是有很多2台电脑的LAN,2台电脑LAN组成3台的时候,比如{a,c}与{c,f},只需要确保a和f互联,同理可推导出两个N-1的LAN,组成N的LAN,只需要校验a1与bn的互联即可。

{a1, xx, xx, xx, xx, xx}
    {xx, xx, xx, xx, xx, bn}          

{a1, xx, xx, xx, xx, xx, bn}
with recursive origin AS (
    SELECT least(split_part(line, '-', 1), split_part(line, '-', 2)) as l, 
           greatest(split_part(line, '-', 1), split_part(line, '-', 2)) as r
    FROM lance_input
), all_paths AS (
    SELECT l, r, array[l, r] as path
    FROM origin

    UNION ALL

    SELECT *
    FROM (
        WITH all_paths_inner AS (select * from all_paths)
        SELECT a.l, c.r, a.path || c.r as path
        FROM all_paths_inner a
        JOIN all_paths_inner b
        ON a.path[2:] = b.path[1:array_length(b.path,1) - 1]
        JOIN origin c
        ON a.l = c.l
        AND b.r = c.r
    ) t
) 
SELECT * FROM all_paths; 
 cu | wb | {cu,iv,ll,oh,oi,oj,qu,qw,uu,vb,vx,wb}
 gy | xx | {gy,jw,jx,kb,lo,mu,pa,pk,ty,vr,xo,xx}
 gy | xx | {gy,jx,kb,lo,mu,no,pa,pk,ty,vr,xo,xx}
 ix | xm | {ix,jy,ls,ly,or,ow,pf,qq,qy,rk,ue,xm}
 ix | xm | {ix,jy,ls,ly,or,ow,pf,qq,rk,ue,xe,xm}
 ch | zk | {ch,cz,di,gb,ht,ku,lu,tw,vf,vt,wo,xz,zk}
(247547 rows)

发表评论