AdventOfCode 2023 Day 25

作者

Day 25: Snowverload

Part One

一个巨大的连通图，断掉其中三个edge，从而分裂为两个独立的图。

jqt: rhn xhk nvd
rsh: frs pzl lsr
xhk: hfx

一开始确实没有头绪，搜索了相关的资料，发现此类问题是一个k-edge-connected graph的问题，一般会使用Karger’s algorithm来计算这个图的min_cut，这个图的min_cnt应该是3。

上图描述了算法的基本步骤

  • 从图中随机选择一个edge
  • 将这条边去除，边的两个顶点合并
  • 重复这个过程，直到图中只剩下2个顶点，顶点之间的边就是min_cnt
  • 由于是随机选择edge，有概率最终剩下的边多于min_cut

首先构建两张表，一个是顶点之间的mapping关系表，一个是顶点表，存储合并的其他顶点

DROP TABLE mapping;
CREATE TABLE mapping AS
WITH origin AS (
  SELECT split_part(line, ': ', 1) as l, unnest(regexp_split_to_array(split_part(line, ': ', 2), ' ')) as r
  FROM lance_input
), mapping AS (
  SELECT l, r
  FROM origin
  UNION ALL
  SELECT r, l
  FROM origin
)
SELECT * FROM mapping;

DROP TABLE vertex;
CREATE TABLE vertex AS
SELECT distinct l as node, ARRAY[]::varchar[] as merged_nodes
FROM mapping;

然后实现karger算法，直到只剩下两个顶点

CREATE OR REPLACE FUNCTION kargers()
RETURNS VOID AS $$
DECLARE
    random_left VARCHAR;
    random_right VARCHAR;
    vertex_cnt INTEGER;
BEGIN
    WHILE TRUE LOOP

      -- remain nodes
      SELECT COUNT(*) FROM vertex INTO vertex_cnt;

      EXIT WHEN vertex_cnt = 2;

      -- find a random edge from mapping
      SELECT l, r FROM mapping order by random() limit 1 INTO random_left, random_right;

      -- merge nodes
      UPDATE vertex SET merged_nodes = vertex.merged_nodes || t.merged_nodes || t.node
      FROM (SELECT node, merged_nodes FROM vertex WHERE node = random_right) t
      WHERE vertex.node = random_left;

      -- remove vertex
      DELETE FROM vertex WHERE node = random_right;

      -- remove edges between vertexes of random edge
      DELETE FROM mapping WHERE l IN (random_left, random_right) AND r IN (random_left, random_right);

      -- update edges
      UPDATE mapping SET r = random_left WHERE r = random_right;
      UPDATE mapping SET l = random_left WHERE l = random_right;


    END LOOP;
END;
$$ LANGUAGE plpgsql;

当算法成功的时候，mapping表应该是剩下三条边，且从顶点表中也可看出分成的两个图的顶点数量

postgres=# select * From mapping;
  l  |  r  
-----+-----
 rhn | rzs
 rhn | rzs
 rhn | rzs
 rzs | rhn
 rzs | rhn
 rzs | rhn
(6 rows)

postgres=# select * from vertex;
 node |           merged_nodes            
------+-----------------------------------
 rhn  | {hfx,jqt,ntq,xhk,bvb}
 rzs  | {frs,rsh,lhk,cmg,lsr,nvd,pzl,qnr}
(2 rows)

当算法未成功的时候，mapping表中多于三条边，且顶点表中的记录也不正确。

postgres=# select * from vertex;
 node |                     merged_nodes                      
------+-------------------------------------------------------
 jqt  | {}
 rhn  | {nvd,pzl,ntq,bvb,lsr,lhk,rsh,hfx,xhk,rzs,cmg,qnr,frs}
(2 rows)

postgres=# select * from mapping;
  l  |  r  
-----+-----
 jqt | rhn
 rhn | jqt
 jqt | rhn
 jqt | rhn
 jqt | rhn
 rhn | jqt
 rhn | jqt
 rhn | jqt
(8 rows)

Part Two

终于完成了所有25关

发表评论