public inbox for [email protected]help / color / mirror / Atom feed
Advent of Code Day 8 5+ messages / 2 participants [nested] [flat]
* Advent of Code Day 8 @ 2025-12-08 15:35 Bernice Southey <[email protected]> 2025-12-16 04:07 ` Re: Advent of Code Day 8 Greg Sabino Mullane <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Bernice Southey @ 2025-12-08 15:35 UTC (permalink / raw) To: [email protected] 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 ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Advent of Code Day 8 2025-12-08 15:35 Advent of Code Day 8 Bernice Southey <[email protected]> @ 2025-12-16 04:07 ` Greg Sabino Mullane <[email protected]> 2025-12-16 12:59 ` Re: Advent of Code Day 8 Bernice Southey <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Greg Sabino Mullane @ 2025-12-16 04:07 UTC (permalink / raw) To: Bernice Southey <[email protected]>; +Cc: [email protected] > 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 <[email protected]> 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 ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Advent of Code Day 8 2025-12-08 15:35 Advent of Code Day 8 Bernice Southey <[email protected]> 2025-12-16 04:07 ` Re: Advent of Code Day 8 Greg Sabino Mullane <[email protected]> @ 2025-12-16 12:59 ` Bernice Southey <[email protected]> 2025-12-16 14:25 ` Re: Advent of Code Day 8 Greg Sabino Mullane <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Bernice Southey @ 2025-12-16 12:59 UTC (permalink / raw) To: Greg Sabino Mullane <[email protected]>; +Cc: [email protected] Greg Sabino Mullane <[email protected]> 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 ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Advent of Code Day 8 2025-12-08 15:35 Advent of Code Day 8 Bernice Southey <[email protected]> 2025-12-16 04:07 ` Re: Advent of Code Day 8 Greg Sabino Mullane <[email protected]> 2025-12-16 12:59 ` Re: Advent of Code Day 8 Bernice Southey <[email protected]> @ 2025-12-16 14:25 ` Greg Sabino Mullane <[email protected]> 2025-12-16 16:19 ` Re: Advent of Code Day 8 Bernice Southey <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Greg Sabino Mullane @ 2025-12-16 14:25 UTC (permalink / raw) To: Bernice Southey <[email protected]>; +Cc: [email protected] On Tue, Dec 16, 2025 at 7:59 AM Bernice Southey <[email protected]> wrote: > Greg Sabino Mullane <[email protected]> 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 ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Advent of Code Day 8 2025-12-08 15:35 Advent of Code Day 8 Bernice Southey <[email protected]> 2025-12-16 04:07 ` Re: Advent of Code Day 8 Greg Sabino Mullane <[email protected]> 2025-12-16 12:59 ` Re: Advent of Code Day 8 Bernice Southey <[email protected]> 2025-12-16 14:25 ` Re: Advent of Code Day 8 Greg Sabino Mullane <[email protected]> @ 2025-12-16 16:19 ` Bernice Southey <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Bernice Southey @ 2025-12-16 16:19 UTC (permalink / raw) To: Greg Sabino Mullane <[email protected]>; +Cc: [email protected] Greg Sabino Mullane <[email protected]> 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. ^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2025-12-16 16:19 UTC | newest] Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2025-12-08 15:35 Advent of Code Day 8 Bernice Southey <[email protected]> 2025-12-16 04:07 ` Greg Sabino Mullane <[email protected]> 2025-12-16 12:59 ` Bernice Southey <[email protected]> 2025-12-16 14:25 ` Greg Sabino Mullane <[email protected]> 2025-12-16 16:19 ` Bernice Southey <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox