How to Solve Advent of Code 2022 Using Postgres - Day 13
Disclaimer
This article will contain spoilers both on how I solved 2022 Day 13's challenge "Distress Signal" using SQL, as well as general ideas on how to approach the problem. I recommend trying to solve it yourself first, using your favorite language. This article is delayed from the actual puzzle's release. Also note that my solutions are seldom going to be the "best" solutions - they were solved as quickly as possible, and these articles will show my first solutions, with some minor reformatting and cleaning up.
Hands on Tutorial
We've also loaded a tutorial for Day 13's challenge if you want to try it with a pre-loaded data set.
AOC Day 13
This puzzle was overall very straightforward. The tech we used this time:
file_fdwto slurp in our puzzle input file- The
lag()function to allow us to view the previous row as we parse the file - Using a sequence to do some counting
- The
regexp_replace()function to sneakily remove our double-digit numbers - The
overlay()function to modify our strings in place as we are parsing them
For this challenge, the goal was to put packets in order, in which each pair consisted of deeply nested arrays like so:
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[[1],4]
[9]
[[8,7,6]]
[[4,4],4,4]
[[4,4],4,4,4]
[7,7,7,7]
[7,7,7]
[]
[3]
[[[]]]
[[]]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]
As usual, we create a custom schema and use file_fdw to access the input file:
CREATE EXTENSION if not exists file_fdw;
CREATE SERVER if not exists aoc2022 FOREIGN DATA WRAPPER file_fdw;
DROP SCHEMA if exists aoc_signal CASCADE;
CREATE SCHEMA aoc_signal;
SET search_path = aoc_signal;
DROP FOREIGN TABLE if exists aoc_day13;
CREATE FOREIGN TABLE aoc_day13 (line text)
SERVER aoc2022 options(filename '/tmp/aoc2022.day13.input');
DROP SEQUENCE if exists aoc;
CREATE SEQUENCE aoc;
There are specific rules for determining the correct order based on the numeric values, how to handle arrays compared to non-arrays, etc. While I suspect a lot of solutions jumped to trying to parse the input as actual arrays or json objects and then evaluate them, I immediately saw this as a bit-by-bit type of challenge.
First, I verified some assumptions and made observations about the data:
- Almost everything was one character long, except for the number
10. So if we can change that 10 to something else, things get a lot simpler as we only need to parse a single character at a time. - The commas are then not needed at all, and can safely be ignored or removed.
- If we can walk through at the same "pace" for both packets, we do not need to worry about which nested array we are currently in.
We can slurp the pairs of packets to compare into a table, with each pair going
on a single row, thanks to nextval() for the line number, lag() to grab the
previous line, and a special WHERE clause to only grab the correct line so we
have two entries:
DROP TABLE if exists signal;
CREATE UNLOGGED TABLE signal(id int, r text, l text);
WITH x AS (SELECT line as l, lag(line) over() AS r FROM aoc_day13)
,y AS (SELECT nextval('aoc') AS id, * FROM x WHERE length(l) >1 AND length(r) > 1)
INSERT INTO signal SELECT * FROM y;
SELECT * FROM signal LIMIT 10;
id | r | l
----+-----------------------------+-----------------------------
2 | [1,1,5,1,1] | [1,1,3,1,1]
3 | [[1],4] | [[1],[2,3,4]]
4 | [[8,7,6]] | [9]
5 | [[4,4],4,4,4] | [[4,4],4,4]
6 | [7,7,7] | [7,7,7,7]
7 | [3] | []
8 | [[]] | [[[]]]
9 | [1,[2,[3,[4,[5,6,0]]]],8,9] | [1,[2,[3,[4,[5,6,7]]]],8,9]
(8 rows)
Now we need a function that walks through both sides, left and right, and compares them character by character:
CREATE or replace FUNCTION signal_sifter1()
returns int language plpgsql as $$
DECLARE
myrec record; lpos int; rpos int; myindex int = 0;
lval int; rval int; in_order bool; correctq int[];
BEGIN
-- Walk through each row and compare the left (l) packet with the right (r) one
FOR myrec in SELECT * FROM signal LOOP
rpos = 0; lpos = 0; myindex = myindex + 1;
-- We want single character numbers, so change 10 to a ':'
-- A colon is one greater than ascii(9)
myrec.l = regexp_replace(myrec.l, '10', ':', 'g');
myrec.r = regexp_replace(myrec.r, '10', ':', 'g');
LOOP
lpos = lpos + 1; rpos = rpos + 1;
-- If the right side ran out, wrong order, so break the loop and move on
IF rpos > length(myrec.r) THEN in_order = false; EXIT; END IF;
-- Left side ran out: right order
IF lpos > length(myrec.l) THEN in_order = true; EXIT; END IF;
-- Extract the ascii value of our current position in both strings
SELECT INTO lval ascii( substr(myrec.l,lpos,1) );
SELECT INTO rval ascii( substr(myrec.r,rpos,1) );
-- If things are equal (numbers,commas, or braces!), just move along
IF lval = rval THEN CONTINUE; END IF;
-- If boths sides are numbers from 0-10, one side will win
IF lval BETWEEN 48 and 58 AND rval BETWEEN 48 and 58 THEN
in_order = CASE WHEN lval > rval THEN false ELSE true END;
EXIT;
END IF;
-- left has ended, but right has not - ascii(93) is a ]
IF lval = 93 THEN in_order=true; EXIT; END IF;
-- right has ended, but left has not
IF rval = 93 THEN in_order=false; EXIT; END IF;
-- right has opened, but left is a number - ascii(91) is [
IF rval = 91 AND lval BETWEEN 48 and 58 THEN
-- transform in place and keep comparing
-- expand to an array: 9 becomes [9]
myrec.l = overlay(myrec.l placing '['||chr(lval)||']' from lpos for 1);
CONTINUE;
END IF;
-- left has opened, but right is a number
IF lval = 91 AND rval BETWEEN 48 and 58 THEN
myrec.r = overlay(myrec.r placing '['||chr(rval)||']' from rpos for 1);
CONTINUE;
END IF;
RAISE EXCEPTION 'Cannot handle this case!';
END LOOP; -- end each character
-- If the order was correct, add this location to a list
IF in_order THEN correctq = correctq || myindex; END IF;
END LOOP;
-- Sum all the winners up
lval = 0; rval = 0; -- Might as well re-use these vars
LOOP
lval = lval + 1;
-- Break out of the loop when nothing left in the queue
IF correctq[lval] IS NULL THEN EXIT; END IF;
rval = rval + correctq[lval];
END LOOP;
RETURN rval;
END;
$$;
Running it produces the correct answer:
SELECT signal_sifter1();
signal_sifter1
----------------
4734
Part Two called for sorting all the input packets, adding in two custom packets, and figuring out where they fall in the sorted output. Rather than worrying about actually sorting the entire list, we can simply see how many packets fall before or after each of the custom pairs:
CREATE or replace FUNCTION signal_sifter2()
returns int language plpgsql as $$
DECLARE
myrec record; lpos int; rpos int;
lval int; rval int; in_order bool;
oldstring text; newstring text;
before int = 1; after int = 2;
BEGIN
FOR myrec in SELECT * FROM signal LOOP
-- See signal_sifter1() for additional explanations
myrec.l = regexp_replace(myrec.l, '10', ':', 'g');
myrec.r = regexp_replace(myrec.r, '10', ':', 'g');
FOR oldstring IN values (myrec.l), (myrec.r) LOOP
FOR newstring IN values ('[[2]]'), ('[[6]]') LOOP
rpos = 0; lpos = 0;
LOOP
lpos = lpos + 1; rpos = rpos + 1;
IF lpos > length(oldstring) THEN in_order = true; EXIT; END IF;
IF lpos > length(newstring) THEN in_order = true; EXIT; END IF;
SELECT INTO lval ascii( substr(oldstring,lpos,1) );
SELECT INTO rval ascii( substr(newstring,rpos,1) );
IF lval = rval THEN CONTINUE; END IF;
IF lval BETWEEN 48 and 58 AND rval BETWEEN 48 and 58 THEN
in_order = CASE when lval > rval THEN false ELSE true END;
EXIT;
END IF;
IF lval = 93 THEN in_order=true; EXIT; END IF;
IF rval = 93 THEN in_order=false; EXIT; END IF;
IF rval = 91 AND lval BETWEEN 48 and 58 THEN
oldstring = overlay(oldstring placing '['||chr(lval)||']' from lpos for 1);
CONTINUE;
END IF;
IF lval = 91 AND rval BETWEEN 48 and 58 THEN
newstring = overlay(newstring placing '['||chr(rval)||']' from rpos for 1);
CONTINUE;
END IF;
RAISE EXCEPTION 'Cannot handle this case!';
END LOOP;
-- Count things up based on who we are
IF in_order THEN
IF newstring ~ '2' THEN before = before + 1; ELSE after = after + 1; END IF;
END IF;
END LOOP; -- end of newstring loop
END LOOP; -- end of olstring loop
END LOOP; -- end of each input line
RETURN before * after;
END;
$$;
Once again, running it gives us the correct answer quickly:
SELECT signal_sifter2();
signal_sifter2
----------------
21836
(1 row)
Stay tuned for more days solving Advent of Code using Postgres!
