MIME-Version: 1.0
References: <CAEDh4nzEm2e=yFnC3UWjMVknjMvHsSX0nVtYdVZJK9NAMMaKVg@mail.gmail.com>
In-Reply-To: <CAEDh4nzEm2e=yFnC3UWjMVknjMvHsSX0nVtYdVZJK9NAMMaKVg@mail.gmail.com>
From: Greg Sabino Mullane <htamfids@gmail.com>
Date: Mon, 15 Dec 2025 23:07:36 -0500
Message-ID: <CAKAnmm+vumTRt8WB0OLsy7cVbYqdPW1m1EEOT26MCFPUd0JcOg@mail.gmail.com>
Subject: Re: Advent of Code Day 8
To: Bernice Southey <bernice.southey@gmail.com>
Cc: pgsql-general@lists.postgresql.org
Content-Type: multipart/alternative; boundary="0000000000001bbe3e064609e0cb"
Archived-At: <https://www.postgresql.org/message-id/CAKAnmm%2BvumTRt8WB0OLsy7cVbYqdPW1m1EEOT26MCFPUd0JcOg%40mail.gmail.com>
Precedence: bulk

--0000000000001bbe3e064609e0cb
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

> 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 =3D 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 =3D 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 =3D 0;
  loops int =3D 0;
  circuit int[] =3D '{}';
  ccount int[];
  c1 int; c2 int;
  solution1 text =3D '?'; solution2 text =3D '?';
BEGIN

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

    loops =3D loops + 1;

    /* For the first part, sum up the three largest circuits */
    IF loops =3D 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 =3D circuit[k.box1]; c2 =3D 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 =3D cid + 1;
      circuit[k.box1] =3D cid;
      circuit[k.box2] =3D cid;
      ccount[cid] =3D 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] =3D c1;
      ccount[c1] =3D 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] =3D c2;
      ccount[c2] =3D 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 =3D 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] =3D c2 then
          circuit[x] =3D c1;
          ccount[c2] =3D ccount[c2] - 1;
          ccount[c1] =3D 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 =3D c2; end if;
    IF ccount[c1] =3D target THEN
      solution2 =3D k.xs;
      exit;
    END IF;

 END LOOP;

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

END
$$;

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

-- Best time: 126 ms

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

-- Same function as above

-- Best overall time: 451ms


On Mon, Dec 8, 2025 at 10:36=E2=80=AFAM Bernice Southey <bernice.southey@gm=
ail.com>
wrote:

> 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
>
>
>


Cheers,
Greg

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

--0000000000001bbe3e064609e0cb
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">&gt; Is anyone else doing AoC in postgres=
 this year?<br>&gt; <a href=3D"https://adventofcode.com/2025/day/8">https:/=
/adventofcode.com/2025/day/8</a><br><br>I am doing it, or at least chipping=
 away a little but on the weekends. This last weekend I got up to day 9. Mo=
st days I can solve with a single SQL statement. Day 8 was not one of those=
, so I fell back to plpgsql.<br><br>&gt; part 1 and 2 with a brute force lo=
op, but there must be better ways.<br><br>What&#39;s so wrong with brute fo=
rce? :) 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.<br><br>In case it helps, here is my solution:=
<br><br>/* Greg Sabino Mullane for AOC 2025 Day 8 &quot;Playground&quot; */=
<br><br>/* Assumes data file is in /tmp/aoc_2026_day8.input */<br><br>\pset=
 footer off<br>\set ON_ERROR_STOP on<br>\set QUIET on<br><br>SET client_min=
_messages =3D ERROR;<br><br>CREATE EXTENSION IF NOT EXISTS file_fdw SCHEMA =
public;<br><br>CREATE SERVER IF NOT EXISTS aoc2025 FOREIGN DATA WRAPPER fil=
e_fdw;<br><br>DROP SCHEMA IF EXISTS aoc_2025_8 CASCADE;<br><br>CREATE SCHEM=
A aoc_2025_8;<br><br>SET search_path =3D aoc_2025_8, public;<br><br>CREATE =
FOREIGN TABLE aoc_2025_day8 (line TEXT)<br>=C2=A0 SERVER aoc2025 OPTIONS (f=
ilename &#39;/tmp/aoc_2025_day8.input&#39;);<br><br>-----------------------=
----<br>-- AOC 2025 DAY 8 PART 1 --<br>---------------------------<br><br>\=
timing on<br><br>create unlogged table t (box1 smallint, box2 smallint, d b=
igint, xs bigint);<br><br>WITH <br>aoc AS (select row_number() over() AS ro=
w,<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 split_part(line,&#39;,&#39;,1)::int AS x,=
<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 split_part(line,&#39;,&#39;,2)::int AS y,<b=
r>=C2=A0 =C2=A0 =C2=A0 =C2=A0 split_part(line,&#39;,&#39;,3)::int AS z<br>=
=C2=A0 from aoc_2025_day8)<br>, dist as (select a1.row as box1, a2.row as b=
ox2, a1.x::bigint * a2.x::bigint AS xs,<br>=C2=A0 (pow(a2.x-a1.x,2) + pow(a=
2.y-a1.y,2) + pow(a2.z-a1.z,2)) as d<br>=C2=A0 from aoc a1 join aoc a2 on (=
a1.row &lt; a2.row)<br>)<br>insert into t select box1, box2, d, xs from dis=
t;<br><br>-- Best time: 289ms<br><br>CREATE FUNCTION connect_em(target int)=
 returns text<br>LANGUAGE plpgsql<br>AS $$<br><br>DECLARE<br>=C2=A0 k recor=
d;<br>=C2=A0 cid int =3D 0;<br>=C2=A0 loops int =3D 0;<br>=C2=A0 circuit in=
t[] =3D &#39;{}&#39;;<br>=C2=A0 ccount int[];<br>=C2=A0 c1 int; c2 int;<br>=
=C2=A0 solution1 text =3D &#39;?&#39;; solution2 text =3D &#39;?&#39;;<br>B=
EGIN<br><br>=C2=A0 /* Walk through each pair of boxes, closest ones first *=
/<br>=C2=A0 FOR k IN select * from t order by d asc LOOP<br><br>=C2=A0 =C2=
=A0 loops =3D loops + 1;<br><br>=C2=A0 =C2=A0 /* For the first part, sum up=
 the three largest circuits */<br>=C2=A0 =C2=A0 IF loops =3D target then<br=
>=C2=A0 =C2=A0 =C2=A0 SELECT INTO solution1 exp(sum(ln(q)))::int AS a FROM =
(select q FROM (SELECT unnest(ccount) q) order by q desc limit 3);<br>=C2=
=A0 =C2=A0 END IF;<br><br>=C2=A0 =C2=A0 c1 =3D circuit[k.box1]; c2 =3D circ=
uit[k.box2];<br><br>=C2=A0 =C2=A0 /* If neither box is part of an existing =
circuit, assign them to a new one */<br>=C2=A0 =C2=A0 IF c1 IS NULL and c2 =
IS NULL THEN<br>=C2=A0 =C2=A0 =C2=A0 cid =3D cid + 1;<br>=C2=A0 =C2=A0 =C2=
=A0 circuit[k.box1] =3D cid;<br>=C2=A0 =C2=A0 =C2=A0 circuit[k.box2] =3D ci=
d;<br>=C2=A0 =C2=A0 =C2=A0 ccount[cid] =3D 2;<br>=C2=A0 =C2=A0 =C2=A0 raise=
 debug &#39; =C2=A0Created circuit #% with boxes % and %&#39;, cid, k.box1,=
 k.box2;<br>=C2=A0 =C2=A0 =C2=A0 continue;<br>=C2=A0 =C2=A0 END IF;<br><br>=
=C2=A0 =C2=A0 /* If only box1 is part of an existing circuit, add box2 */<b=
r>=C2=A0 =C2=A0 IF c1 IS NOT NULL and c2 IS NULL THEN<br>=C2=A0 =C2=A0 =C2=
=A0 circuit[k.box2] =3D c1;<br>=C2=A0 =C2=A0 =C2=A0 ccount[c1] =3D ccount[c=
1] + 1;<br>=C2=A0 =C2=A0 =C2=A0 raise debug &#39; =C2=A0Moved second box % =
to circuit #%, used by box %&#39;, k.box2, c1, k.box1;<br>=C2=A0 =C2=A0 END=
 IF;<br><br>=C2=A0 =C2=A0 /* If only box2 is part of an existing circuit, a=
dd box1 */<br>=C2=A0 =C2=A0 IF c1 IS NULL and c2 IS NOT NULL THEN<br>=C2=A0=
 =C2=A0 =C2=A0 circuit[k.box1] =3D c2;<br>=C2=A0 =C2=A0 =C2=A0 ccount[c2] =
=3D ccount[c2] + 1;<br>=C2=A0 =C2=A0 =C2=A0 raise debug &#39; =C2=A0Moved f=
irst box % to circuit #% , used by box %&#39;, k.box1, c2, k.box2;<br>=C2=
=A0 =C2=A0 END IF;<br><br>=C2=A0 =C2=A0 /* Both boxes are already part of a=
 circuit, so merge or ignore */<br>=C2=A0 =C2=A0 IF c1 IS NOT NULL and c2 I=
S NOT NULL THEN<br>=C2=A0 =C2=A0 =C2=A0 IF c1 =3D c2 THEN<br>=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 raise debug &#39; =C2=A0Skip, as both boxes already belong to=
 the same circuit&#39;;<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 continue;<br>=C2=A0 =
=C2=A0 =C2=A0 END IF;<br><br>=C2=A0 =C2=A0 =C2=A0 /* Move anything in the o=
ld circuit to the new one */<br>=C2=A0 =C2=A0 =C2=A0 for x in array_lower(c=
ircuit,1) .. array_upper(circuit,1) loop<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 if =
circuit[x] =3D c2 then<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 circuit[x] =3D=
 c1;<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ccount[c2] =3D ccount[c2] - 1;<b=
r>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ccount[c1] =3D ccount[c1] + 1;<br>=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 end if;<br>=C2=A0 =C2=A0 =C2=A0 end loop;<br><br>=
=C2=A0 =C2=A0 =C2=A0 raise debug &#39; =C2=A0Merge box % circuit #% (now at=
 %) into box % circuit #% (now at %)&#39;,<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 k=
.box2, c2, ccount[c2], k.box1, c1, ccount[c1];<br>=C2=A0 =C2=A0 END IF;<br>=
<br>=C2=A0 =C2=A0 /* We avoided using CONTINUE above just to make this chec=
k */<br>=C2=A0 =C2=A0 if c1 is null then c1 =3D c2; end if;<br>=C2=A0 =C2=
=A0 IF ccount[c1] =3D target THEN<br>=C2=A0 =C2=A0 =C2=A0 solution2 =3D k.x=
s;<br>=C2=A0 =C2=A0 =C2=A0 exit;<br>=C2=A0 =C2=A0 END IF;<br><br>=C2=A0END =
LOOP;<br><br>RETURN format(&#39;Solution 1: %s =C2=A0Solution 2: %s&#39;, s=
olution1, solution2);<br><br>END<br>$$;<br><br>-- SET client_min_messages =
=3D DEBUG1;<br>SELECT connect_em(1000);<br><br>-- Best time: 126 ms<br><br>=
---------------------------<br>-- AOC 2025 DAY 8 PART 2 --<br>-------------=
--------------<br><br>-- Same function as above<br><br>-- Best overall time=
: 451ms<br><br></div><br><div class=3D"gmail_quote gmail_quote_container"><=
div dir=3D"ltr" class=3D"gmail_attr">On Mon, Dec 8, 2025 at 10:36=E2=80=AFA=
M Bernice Southey &lt;<a href=3D"mailto:bernice.southey@gmail.com">bernice.=
southey@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex">Hi,<br>
<br>
Is anyone else doing AoC in postgres this year? I&#39;ve solved today&#39;s=
<br>
part 1 and 2 with a brute force loop, but there must be better ways.<br>
If anyone found something clever in postgres, please give me a big<br>
hint.<br>
<a href=3D"https://adventofcode.com/2025/day/8" rel=3D"noreferrer" target=
=3D"_blank">https://adventofcode.com/2025/day/8</a><br>
<br>
Thanks, Bernice<br>
<br>
<br>
</blockquote></div><div><br clear=3D"all"></div><div><br></div><br><div dir=
=3D"ltr" class=3D"gmail_signature"><div dir=3D"ltr"><div>Cheers,</div><div>=
Greg</div><div><br></div><div>--</div><div>Crunchy Data - <a href=3D"https:=
//www.crunchydata.com" target=3D"_blank">https://www.crunchydata.com</a></d=
iv><div>Enterprise Postgres Software Products &amp; Tech Support</div><div>=
<br></div></div></div></div>

--0000000000001bbe3e064609e0cb--