Обсуждение: Advent of Code Day 8

> Is anyone else doing AoC in postgres this year?
> https://adventofcode.com/2025/day/8

I am doing it, or at least chipping away a little but on the weekends. This last weekend I got up to day 9. Most days I can solve with a single SQL statement. Day 8 was not one of those, so I fell back to plpgsql.

> part 1 and 2 with a brute force loop, but there must be better ways.

What's so wrong with brute force? :) Day 8 seemed pretty straightforward: split into x,y,z coordinates, calculate distances, then walk through in distance order and create / merge groups (circuits) as you go.

In case it helps, here is my solution:

/* Greg Sabino Mullane for AOC 2025 Day 8 "Playground" */

/* Assumes data file is in /tmp/aoc_2026_day8.input */

\pset footer off
\set ON_ERROR_STOP on
\set QUIET on

SET client_min_messages = ERROR;

CREATE EXTENSION IF NOT EXISTS file_fdw SCHEMA public;

CREATE SERVER IF NOT EXISTS aoc2025 FOREIGN DATA WRAPPER file_fdw;

DROP SCHEMA IF EXISTS aoc_2025_8 CASCADE;

CREATE SCHEMA aoc_2025_8;

SET search_path = aoc_2025_8, public;

CREATE FOREIGN TABLE aoc_2025_day8 (line TEXT)
  SERVER aoc2025 OPTIONS (filename '/tmp/aoc_2025_day8.input');

---------------------------
-- AOC 2025 DAY 8 PART 1 --
---------------------------

\timing on

create unlogged table t (box1 smallint, box2 smallint, d bigint, xs bigint);

WITH
aoc AS (select row_number() over() AS row,
        split_part(line,',',1)::int AS x,
        split_part(line,',',2)::int AS y,
        split_part(line,',',3)::int AS z
  from aoc_2025_day8)
, dist as (select a1.row as box1, a2.row as box2, a1.x::bigint * a2.x::bigint AS xs,
  (pow(a2.x-a1.x,2) + pow(a2.y-a1.y,2) + pow(a2.z-a1.z,2)) as d
  from aoc a1 join aoc a2 on (a1.row < a2.row)
)
insert into t select box1, box2, d, xs from dist;

-- Best time: 289ms

CREATE FUNCTION connect_em(target int) returns text
LANGUAGE plpgsql
AS $$

DECLARE
  k record;
  cid int = 0;
  loops int = 0;
  circuit int[] = '{}';
  ccount int[];
  c1 int; c2 int;
  solution1 text = '?'; solution2 text = '?';
BEGIN

  /* Walk through each pair of boxes, closest ones first */
  FOR k IN select * from t order by d asc LOOP

    loops = loops + 1;

    /* For the first part, sum up the three largest circuits */
    IF loops = target then
      SELECT INTO solution1 exp(sum(ln(q)))::int AS a FROM (select q FROM (SELECT unnest(ccount) q) order by q desc limit 3);
    END IF;

    c1 = circuit[k.box1]; c2 = circuit[k.box2];

    /* If neither box is part of an existing circuit, assign them to a new one */
    IF c1 IS NULL and c2 IS NULL THEN
      cid = cid + 1;
      circuit[k.box1] = cid;
      circuit[k.box2] = cid;
      ccount[cid] = 2;
      raise debug '  Created circuit #% with boxes % and %', cid, k.box1, k.box2;
      continue;
    END IF;

    /* If only box1 is part of an existing circuit, add box2 */
    IF c1 IS NOT NULL and c2 IS NULL THEN
      circuit[k.box2] = c1;
      ccount[c1] = ccount[c1] + 1;
      raise debug '  Moved second box % to circuit #%, used by box %', k.box2, c1, k.box1;
    END IF;

    /* If only box2 is part of an existing circuit, add box1 */
    IF c1 IS NULL and c2 IS NOT NULL THEN
      circuit[k.box1] = c2;
      ccount[c2] = ccount[c2] + 1;
      raise debug '  Moved first box % to circuit #% , used by box %', k.box1, c2, k.box2;
    END IF;

    /* Both boxes are already part of a circuit, so merge or ignore */
    IF c1 IS NOT NULL and c2 IS NOT NULL THEN
      IF c1 = c2 THEN
        raise debug '  Skip, as both boxes already belong to the same circuit';
        continue;
      END IF;

      /* Move anything in the old circuit to the new one */
      for x in array_lower(circuit,1) .. array_upper(circuit,1) loop
        if circuit[x] = c2 then
          circuit[x] = c1;
          ccount[c2] = ccount[c2] - 1;
          ccount[c1] = ccount[c1] + 1;
        end if;
      end loop;

      raise debug '  Merge box % circuit #% (now at %) into box % circuit #% (now at %)',
        k.box2, c2, ccount[c2], k.box1, c1, ccount[c1];
    END IF;

    /* We avoided using CONTINUE above just to make this check */
    if c1 is null then c1 = c2; end if;
    IF ccount[c1] = target THEN
      solution2 = k.xs;
      exit;
    END IF;

 END LOOP;

RETURN format('Solution 1: %s  Solution 2: %s', solution1, solution2);

END
$$;

-- SET client_min_messages = DEBUG1;
SELECT connect_em(1000);

-- Best time: 126 ms

---------------------------
-- AOC 2025 DAY 8 PART 2 --
---------------------------

-- Same function as above

-- Best overall time: 451ms

On Tue, Dec 16, 2025 at 7:59 AM Bernice Southey <bernice.southey@gmail.com> wrote: