Thread

1. Advent of Code Day 8

   Bernice Southey <bernice.southey@gmail.com> — 2025-12-08T15:35:38Z

   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
   
   
   
   

2. Re: Advent of Code Day 8

   Greg Sabino Mullane <htamfids@gmail.com> — 2025-12-16T04:07:36Z

   > 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 Mon, Dec 8, 2025 at 10:36 AM Bernice Southey <bernice.southey@gmail.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
   

3. Re: Advent of Code Day 8

   Bernice Southey <bernice.southey@gmail.com> — 2025-12-16T12:59:02Z

   Greg Sabino Mullane <htamfids@gmail.com> 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
   
   
   
   

4. Re: Advent of Code Day 8

   Greg Sabino Mullane <htamfids@gmail.com> — 2025-12-16T14:25:36Z

   On Tue, Dec 16, 2025 at 7:59 AM Bernice Southey <bernice.southey@gmail.com>
   wrote:
   
   > Greg Sabino Mullane <htamfids@gmail.com> wrote:
   > > What's so wrong with brute force? :)
   > 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. :)
   
   
   > 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, 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
   
   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_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
   

5. Re: Advent of Code Day 8

   Bernice Southey <bernice.southey@gmail.com> — 2025-12-16T16:19:21Z

   Greg Sabino Mullane <htamfids@gmail.com> 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.
   
   
   
   

6. Re: Advent of Code Day 8

   Bernice Southey <bernice.southey@gmail.com> — 2025-12-17T17:39:59Z

   It's slow at 20 seconds, but I'm pleased I finally found a good enough
   way to use tables for day 8. Afterall, the reason I tried AoC in
   postgres is because I really like table logic. By swapping out two
   temp tables and doing insert only, I can avoid the update MVCC bloat
   that wrecked my previous attempt. It was very educational watching the
   loop speed degrade to a crawl after a thousand update runs, even
   though the table never got bigger than 1000 rows.
   
   I copied the input into d8(t text).
   
   create temp table w1(c int, b text);
   create temp table w2(c int, b text);
   
   do $$
   declare r record;
   begin
   --loop through the connections in closest order
   for r in (with j as (
       select row_number() over () r, t,
           split_part(t, ',', 1)::int8 x,
           split_part(t, ',', 2)::int8 y,
           split_part(t, ',', 3)::int8 z
       from d8)
       select row_number() over(
           order by (j.x-j1.x)^2 + (j.y-j1.y)^2 + (j.z-j1.z)^2) i,
           j.t b1, j1.t b2, j.x * j1.x s from j, j j1 where j1.r > j.r) loop
   
       --add the two boxes from the current connection
       insert into w1 values (r.i, r.b1), (r.i, r.b2);
   
       --connect all the boxes in the circuits of these two boxes
       insert into w1 select r.i, w3.b
       from w1 join w2 on w1.b = w2.b join w2 w3 on w2.c = w3.c;
   
       --keep all the existing boxes with their current circuits
       insert into w1 select * from w2;
   
       truncate w2;
       --get the latest circuit per box
       insert into w2 select distinct on (b) * from w1 order by b, c desc;
       truncate w1;
   
       --the circuit is complete when all the boxes are in the current circuit
       if (select count(*) from w2 where c = r.i) = 1000 then
           raise notice '%', r.s;
           exit;
       end if;
   end loop;
   end
   $$;