MIME-Version: 1.0
References: <CAEDh4nzEm2e=yFnC3UWjMVknjMvHsSX0nVtYdVZJK9NAMMaKVg@mail.gmail.com>
 <CAKAnmm+vumTRt8WB0OLsy7cVbYqdPW1m1EEOT26MCFPUd0JcOg@mail.gmail.com> <CAEDh4nxpTobNoV8=6hqJm3gP2i6-=RvD9R9d1zh=6VrOta3gSA@mail.gmail.com>
In-Reply-To: <CAEDh4nxpTobNoV8=6hqJm3gP2i6-=RvD9R9d1zh=6VrOta3gSA@mail.gmail.com>
From: Greg Sabino Mullane <htamfids@gmail.com>
Date: Tue, 16 Dec 2025 09:25:36 -0500
Message-ID: <CAKAnmmKe569wZRFAEmzpxHPJeVE340iP0Qf3G+sJMgf7HgedRQ@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="00000000000083b6810646128297"
Archived-At: <https://www.postgresql.org/message-id/CAKAnmmKe569wZRFAEmzpxHPJeVE340iP0Qf3G%2BsJMgf7HgedRQ%40mail.gmail.com>
Precedence: bulk

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

On Tue, Dec 16, 2025 at 7:59=E2=80=AFAM Bernice Southey <bernice.southey@gm=
ail.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 abou=
t
> 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 =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_7 CASCADE;

CREATE SCHEMA aoc_2025_7;

SET search_path =3D 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=3Doff%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) =3D '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) =3D '^' 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

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

<div dir=3D"ltr"><div dir=3D"ltr">On Tue, Dec 16, 2025 at 7:59=E2=80=AFAM B=
ernice Southey &lt;<a href=3D"mailto:bernice.southey@gmail.com">bernice.sou=
they@gmail.com</a>&gt; wrote:</div><div class=3D"gmail_quote gmail_quote_co=
ntainer"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex">Greg Sabino Mull=
ane &lt;<a href=3D"mailto:htamfids@gmail.com" target=3D"_blank">htamfids@gm=
ail.com</a>&gt; wrote:<br>
&gt; What&#39;s so wrong with brute force? :)<br>
Yeah, a few more days of AoC changed my mind.<br></blockquote><div><br></di=
v><div>Doing things in SQL and/or plpgsql=C2=A0definitely presents a lot of=
 challenges, especially in comparison to a &quot;regular&quot; 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 tri=
cks and shortcuts. There are some cases where Postgres has the advantage wh=
en you can use things like range types, but for the most part, it&#39;s pai=
n. :)</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"marg=
in:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1e=
x">Good luck with day 10 part 2. That&#39;s the only one I gave up on after=
 discovering everyone was using solvers, or rolling their own. It&#39;s by<=
br>
far the hardest, but one person found a brilliant way...don&#39;t forget ab=
out part 1.<br></blockquote><div><br></div><div>Thanks, I hope to get to th=
at one soon. As I said, I&#39;m trying to solve them in a single statement.=
 Recursive CTEs, CASE, and creative use of JSON can get you a long way. Her=
e&#39;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:</div=
><div><font face=3D"monospace"><br></font></div><div><font face=3D"monospac=
e"><br>/* Greg Sabino Mullane for AOC 2025 Day 7 &quot;Laboratories&quot; *=
/<br><br>/* Assumes data file is in /tmp/aoc_2026_day7.input */<br><br>\pse=
t footer off<br>\set ON_ERROR_STOP on<br><br>SET client_min_messages =3D ER=
ROR;<br><br>CREATE EXTENSION IF NOT EXISTS file_fdw SCHEMA public;<br><br>C=
REATE SERVER IF NOT EXISTS aoc2025 FOREIGN DATA WRAPPER file_fdw;<br><br>DR=
OP SCHEMA IF EXISTS aoc_2025_7 CASCADE;<br><br>CREATE SCHEMA aoc_2025_7;<br=
><br>SET search_path =3D aoc_2025_7, public;<br><br>CREATE FOREIGN TABLE ao=
c_2025_day7 (line TEXT)<br>=C2=A0 SERVER aoc2025 OPTIONS (filename &#39;/tm=
p/aoc_2025_day7.input&#39;);<br><br>---------------------------<br>-- AOC 2=
025 DAY 7 PART 1 --<br>---------------------------<br><br>\timing on<br><br=
>WITH RECURSIVE<br>dims AS (SELECT length(line) AS len FROM aoc_2025_day7 L=
IMIT 1)<br>,aoc AS (SELECT string_agg(replace(line, &#39;.&#39;,&#39;o&#39;=
),&#39;&#39;) as line FROM aoc_2025_day7)<br>,start AS (SELECT regexp_repla=
ce(line, &#39;S(.{&#39;||len-1||&#39;}).&#39;, &#39;S\1B&#39;) AS line FROM=
 aoc, dims)<br>, rec AS (<br>=C2=A0 SELECT (select len FROM dims) AS xlen, =
line FROM start<br>=C2=A0 UNION<br>=C2=A0 SELECT xlen,<br>regexp_replace(<b=
r>=C2=A0regexp_replace(line<br>=C2=A0 ,&#39;B(.{&#39;||xlen-1||&#39;})o&#39=
;, &#39;B\1B&#39;, &#39;g&#39;)=C2=A0 =C2=A0 =C2=A0 =C2=A0/* extend the bea=
m */<br>=C2=A0 ,&#39;B(.{&#39;||xlen-2||&#39;})(?:o\^o|B\^o|o\^B)&#39;, =
9;B\1B^B&#39;, &#39;g&#39;)=C2=A0 /* split the beam */<br>=C2=A0 /* We need=
 that tri-state check because if we overwrite existing B^B, we won&#39;t do=
 a nearby one! */<br>=C2=A0AS line<br>FROM rec<br>)<br>,rec2 AS (SELECT row=
_number() over() AS r, line from rec)<br>, winner AS (SELECT len, line FROM=
 rec2, dims ORDER BY r DESC LIMIT 1)<br>SELECT sum(regexp_count(right(line,=
 -xx), &#39;^B.{&#39;||len-1||&#39;}\^&#39;)) FROM winner, <br>=C2=A0 gener=
ate_series(1, (select length(line) from winner)) xx;<br><br>-- Best time: 3=
976 ms<br><br>---------------------------<br>-- AOC 2025 DAY 7 PART 2 --<br=
>---------------------------<br><br>WITH RECURSIVE<br><br>=C2=A0dims AS (SE=
LECT length(line) AS len FROM aoc_2025_day7 LIMIT 1)<br>,aoc =C2=A0AS (SELE=
CT string_agg(line,&#39;&#39;) as line FROM aoc_2025_day7)<br>,rec =C2=A0AS=
 (<br>SELECT 0 AS off, line, 0 AS col, &#39;{}&#39;::jsonb AS score FROM ao=
c<br>UNION<br>SELECT off+1, line, CASE WHEN 0=3Doff%len THEN len ELSE off%l=
en END,<br><br>=C2=A0 score || <br>=C2=A0 CASE<br>=C2=A0 =C2=A0 /* If our c=
urrent item item is the start, mark that column with a score of 1 */<br>=C2=
=A0 =C2=A0 WHEN substring(line from off for 1) =3D &#39;S&#39; THEN jsonb_b=
uild_object(&#39;c&#39;||1+col, 1)<br><br>=C2=A0 =C2=A0 /* If our current i=
tem is a splitter, change score of the two new beams */<br>=C2=A0 =C2=A0 WH=
EN substring(line from off for 1) =3D &#39;^&#39; THEN jsonb_build_object(<=
br><br>=C2=A0 =C2=A0 =C2=A0 /* Set the score for the left beam (existing le=
ft + middle) */<br>=C2=A0 =C2=A0 =C2=A0 &#39;c&#39;||col, <br>=C2=A0 =C2=A0=
 =C2=A0 =C2=A0 COALESCE( (score -&gt; (&#39;c&#39;||col)::text)::bigint, 0)=
<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 + (score -&gt; (&#39;c&#39;||col+1)::text):=
:bigint<br><br>=C2=A0 =C2=A0 =C2=A0 /* Set the score for the right beam (ex=
isting right + middle) */<br>=C2=A0 =C2=A0 =C2=A0 ,&#39;c&#39;||col+2, <br>=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 COALESCE( (score -&gt; (&#39;c&#39;||col+2)::te=
xt)::bigint, 0)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 + (score -&gt; (&#39;c&#39;|=
|col+1)::text)::bigint<br><br>=C2=A0 =C2=A0 =C2=A0 /* Reset the score to ze=
ro for this column, as we split! */<br>=C2=A0 =C2=A0 =C2=A0 ,&#39;c&#39;||c=
ol+1, 0<br>=C2=A0 <br>=C2=A0 =C2=A0 ) /* end of jsonb_build_object */<br><b=
r>=C2=A0 ELSE &#39;{}&#39;::jsonb END<br><br>FROM rec, dims<br>WHERE off &l=
t; (select length(line) from aoc)<br>)<br>,lastscore AS (SELECT score FROM =
rec ORDER BY off DESC LIMIT 1)<br>,lastvals AS (SELECT (jsonb_each(score)).=
value::bigint AS jval FROM lastscore)<br>SELECT SUM(jval) FROM lastvals;<br=
>=C2=A0 =C2=A0 =C2=A0 <br>-- Best time: 3428 ms<br><br></font></div></div><=
/div>

--00000000000083b6810646128297--