Re: Advent of Code Day 8 - Mailing list pgsql-general
| From | Greg Sabino Mullane |
|---|---|
| Subject | Re: Advent of Code Day 8 |
| Date | |
| Msg-id | CAKAnmmKe569wZRFAEmzpxHPJeVE340iP0Qf3G+sJMgf7HgedRQ@mail.gmail.com Whole thread Raw |
| In response to | Re: Advent of Code Day 8 (Bernice Southey <bernice.southey@gmail.com>) |
| Responses |
Re: Advent of Code Day 8
|
| List | pgsql-general |
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
pgsql-general by date: