Subject: Advent of Code Day 8

From: Bernice Southey <[email-masked]>
Date: Mon, 8 Dec 2025 15:35:38 +0000

Hi,

Is anyone else doing AoC in postgres this year? I've solved today's
part 1 and 2 with a brute force loop, but there must be better ways.
If anyone found something clever in postgres, please give me a big
hint.
https://adventofcode.com/2025/day/8

Thanks, Bernice

---

From: Greg Sabino Mullane <[email-masked]>
Date: Mon, 15 Dec 2025 23:07:36 -0500

> Is anyone else doing AoC in postgres this year?

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

> https://adventofcode.com/2025/day/8

Cheers,
Greg

--
Crunchy Data - https://www.crunchydata.com
Enterprise Postgres Software Products & Tech Support

---

From: Bernice Southey <[email-masked]>
Date: Tue, 16 Dec 2025 12:59:02 +0000

Greg Sabino Mullane <[email-masked]> wrote:
> What's so wrong with brute force? :)
Yeah, a few more days of AoC changed my mind.

> In case it helps, here is my solution:
Thank you, this is very clever! I tried something similar, but with
updating the circuit in my table on every loop. It ran a couple of
minutes just to target the earliest possible full circuit for part 2.
This turned out to be the answer, but hardly satisfying. Your array
variables trick would never have occurred to me.

I found a couple of other interesting ideas on reddit. One used a
recursive function in a recursive cte, and another used hstore to
track unique boxes.

Good luck with day 10 part 2. That's the only one I gave up on after
discovering everyone was using solvers, or rolling their own. It's by
far the hardest, but one person found a brilliant way...don't forget
about part 1.

Thanks, Bernice

---

From: Greg Sabino Mullane <[email-masked]>
Date: Tue, 16 Dec 2025 09:25:36 -0500

> Yeah, a few more days of AoC changed my mind.

Doing things in SQL and/or plpgsql definitely presents a lot of challenges,
especially in comparison to a "regular" programming language. Oftentimes
the problems later in the month run the test data just fine, but the real
solution takes way, way too long without doing some tricks and shortcuts.
There are some cases where Postgres has the advantage when you can use
things like range types, but for the most part, it's pain. :)

> far the hardest, but one person found a brilliant way...don't forget about
> part 1.
>

Thanks, I hope to get to that one soon. As I said, I'm trying to solve them
in a single statement. Recursive CTEs, CASE, and creative use of JSON can
get you a long way. Here's my day 7, which runs slow compared to other
languages, but runs as a single SQL statement and no plpgsql, and I think
is a good solution:

/* Greg Sabino Mullane for AOC 2025 Day 7 "Laboratories" */

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

\pset footer off
\set ON_ERROR_STOP on

DROP SCHEMA IF EXISTS aoc_2025_7 CASCADE;

CREATE SCHEMA aoc_2025_7;

SET search_path = aoc_2025_7, public;

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

---------------------------
-- AOC 2025 DAY 7 PART 1 --
---------------------------

\timing on

WITH RECURSIVE
dims AS (SELECT length(line) AS len FROM aoc_2025_day7 LIMIT 1)
,aoc AS (SELECT string_agg(replace(line, '.','o'),'') as line FROM
aoc_2025_day7)
,start AS (SELECT regexp_replace(line, 'S(.{'||len-1||'}).', 'S\1B') AS
line FROM aoc, dims)
, rec AS (
  SELECT (select len FROM dims) AS xlen, line FROM start
  UNION
  SELECT xlen,
regexp_replace(
 regexp_replace(line
  ,'B(.{'||xlen-1||'})o', 'B\1B', 'g')       /* extend the beam */
  ,'B(.{'||xlen-2||'})(?:o\^o|B\^o|o\^B)', 'B\1B^B', 'g')  /* split the
beam */
  /* We need that tri-state check because if we overwrite existing B^B, we
won't do a nearby one! */
 AS line
FROM rec
)
,rec2 AS (SELECT row_number() over() AS r, line from rec)
, winner AS (SELECT len, line FROM rec2, dims ORDER BY r DESC LIMIT 1)
SELECT sum(regexp_count(right(line, -xx), '^B.{'||len-1||'}\^')) FROM
winner,
  generate_series(1, (select length(line) from winner)) xx;

-- Best time: 3976 ms

---------------------------
-- AOC 2025 DAY 7 PART 2 --
---------------------------

WITH RECURSIVE

 dims AS (SELECT length(line) AS len FROM aoc_2025_day7 LIMIT 1)
,aoc  AS (SELECT string_agg(line,'') as line FROM aoc_2025_day7)
,rec  AS (
SELECT 0 AS off, line, 0 AS col, '{}'::jsonb AS score FROM aoc
UNION
SELECT off+1, line, CASE WHEN 0=off%len THEN len ELSE off%len END,

  score ||
  CASE
    /* If our current item item is the start, mark that column with a score
of 1 */
    WHEN substring(line from off for 1) = 'S' THEN
jsonb_build_object('c'||1+col, 1)

    /* If our current item is a splitter, change score of the two new beams
*/
    WHEN substring(line from off for 1) = '^' THEN jsonb_build_object(

      /* Set the score for the left beam (existing left + middle) */
      'c'||col,
        COALESCE( (score -> ('c'||col)::text)::bigint, 0)
        + (score -> ('c'||col+1)::text)::bigint

      /* Set the score for the right beam (existing right + middle) */
      ,'c'||col+2,
        COALESCE( (score -> ('c'||col+2)::text)::bigint, 0)
        + (score -> ('c'||col+1)::text)::bigint

      /* Reset the score to zero for this column, as we split! */
      ,'c'||col+1, 0

    ) /* end of jsonb_build_object */

  ELSE '{}'::jsonb END

FROM rec, dims
WHERE off < (select length(line) from aoc)
)
,lastscore AS (SELECT score FROM rec ORDER BY off DESC LIMIT 1)
,lastvals AS (SELECT (jsonb_each(score)).value::bigint AS jval FROM
lastscore)
SELECT SUM(jval) FROM lastvals;

-- Best time: 3428 ms

---

From: Bernice Southey <[email-masked]>
Date: Tue, 16 Dec 2025 16:19:21 +0000

Greg Sabino Mullane <[email-masked]> wrote:
> As I said, I'm trying to solve them in a single statement. Recursive CTEs, CASE, and creative use of JSON can get you a long way. Here's my day 7, which runs slow compared to other languages, but runs as a single SQL statement and no plpgsql, and I think is a good solution:
This took some head scratching but is very clever. I see there are
plenty of tricks for working around the limitations of recursive CTEs.

 If you do ever get to 10, I'd be very curious to see your answer. I
used a recursive CTE for part 1, but cheated by limiting the recursion
to a fixed big enough number. I've been struggling with branch
pruning. I'm also interested in how you solve 11, if you use a
recursive CTE trick for part 2. The no aggregates drove me to a for
loop.

I was planning to check out your blog for 2022 if I ever caught up on
old AoCs, but 10 years is a bit steep. Now I'm thinking if I should
just read it for the tricks, and skip the puzzling.