How to Solve Advent of Code 2022 Using Postgres - Day 10
Spoiler Alert
This article will contain spoilers both on how I solved 2022 Day 10's challenge "Cathode-Ray Tube" 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 10's challenge if you want to try it with a pre-loaded data set.
AOC Day 10
Today's challenge was a fairly simple one, solved with the help of a few items:
- file_fdw, a built-in foreign data wrapper for Postgres
- Using sequences in unintended ways
- Some window functions using
OVER()
to control both the order and partitioning key
Given a simple data file, we had to keep track of the signal strength as it changed each line, with the further twist that the counting was not quite linear, as some lines moved things along more than others. The input file had 145 lines that looked like this:
noop
noop
addx 5
addx 21
addx -16
noop
addx 1
noop
noop
addx 4
addx 1
First, our usual setup so we can query a pseudo-table containing the items from the file. Because the "noop" lines have no space after the letter "p", we cannot use a delimiter option in our foreign table declaration.
CREATE EXTENSION if not exists file_fdw;
CREATE SERVER if not exists aoc2022 foreign data wrapper file_fdw;
DROP SCHEMA if exists crt CASCADE;
CREATE SCHEMA crt;
SET search_path = crt;
DROP FOREIGN TABLE if exists aoc_day10;
CREATE FOREIGN TABLE aoc_day10 (com text)
SERVER aoc2022 options(filename '/tmp/aoc2022.day10.input');
DROP SEQUENCE if exists aoc;
CREATE SEQUENCE if not exists aoc;
Our first step is to treat our "noop" and "addx" lines differently. If it's a "noop", we simply consider the signal to change by zero, otherwise, we read in the number with a careful call to substr
.
Normally, we use a single nextval
call to give a number to each row, but because the "addx" rows take two turns to complete, we add a second call in that case, so that we can keep track of "cycle" we are on. We don't want the nextval to actually return anything used, so we just multiply by zero to have it fire but not affect anything. We also use a separate CTE to ensure our sequence starts with 2, as the actual numbering in the "cycle" column becomes very important later on.
WITH setup AS (SELECT setval('aoc',2,false))
,x AS (SELECT * FROM setup, aoc_day10)
,y AS (SELECT com, nextval('aoc') AS cycle,
CASE WHEN com = 'noop'
THEN 0
ELSE nextval('aoc')*0 + substr(com,6)::int
END AS warp
FROM x)
SELECT * FROM y LIMIT 10;
com | cycle | warp
----------+-------+------
noop | 2 | 0
noop | 3 | 0
addx 5 | 4 | 5
addx 21 | 6 | 21
addx -16 | 8 | -16
noop | 10 | 0
addx 1 | 11 | 1
noop | 13 | 0
noop | 14 | 0
addx 4 | 15 | 4
(10 rows)
Next, we want to see how much our running count (which starts at 1) changes with every "addx" call. We do this by simply summing up the warp values over a very short window, making sure to keep the window in a specific order (based on the cycle, or basically the original input order).
WITH setup AS (SELECT setval('aoc',2,false))
,x AS (SELECT * FROM setup, aoc_day10)
,y AS (SELECT com, nextval('aoc') AS cycle, CASE WHEN com='noop' THEN 0
ELSE nextval('aoc')*0 + substr(com,6)::int END AS warp FROM x)
,z AS (
SELECT *, 1+sum(warp) over(order by cycle) AS newwarp
FROM y
)
SELECT * FROM z LIMIT 10;
com | cycle | warp | newwarp
----------+-------+------+---------
noop | 2 | 0 | 1
noop | 3 | 0 | 1
addx 5 | 4 | 5 | 6
addx 21 | 6 | 21 | 27
addx -16 | 8 | -16 | 11
noop | 10 | 0 | 11
addx 1 | 11 | 1 | 12
noop | 13 | 0 | 12
noop | 14 | 0 | 12
addx 4 | 15 | 4 | 16
(10 rows)
The challenge asks us to look at what the value is at a very specific interval. So we plug those intervals into a new CTE named checkpoints
. Because the cycle can skip forward, we may not have an exact match for those values (for example, in the output above, there is no cycle 12 listed). But we know that one of 12, 11, or 10 must exist, so we create a small window containing the checkpoint value and the two before it, then use max()
to make sure we grab the highest one. This gives us a list of the correct value at the cycle closest to the list we are consulting:
WITH setup AS (SELECT setval('aoc',2,false))
,x AS (SELECT * FROM setup, aoc_day10)
,y AS (SELECT com, nextval('aoc') AS cycle, CASE WHEN com='noop' THEN 0
ELSE nextval('aoc')*0 + substr(com,6)::int END AS warp FROM x)
,z AS (SELECT *, 1+sum(warp) over(order by cycle) AS newwarp FROM y)
,checkpoints (cp) AS (VALUES (20),(60),(100),(140),(180),(220))
,w AS (
SELECT distinct max(cycle) over(partition by cp) AS score, cp
FROM z, checkpoints
WHERE cycle = cp-1 OR cycle = cp-2
)
SELECT * FROM w ORDER BY 1;
score | cp
-------+-----
19 | 20
59 | 60
98 | 100
139 | 140
179 | 180
219 | 220
(6 rows)
The final solution wants us to combine all the values at the given checkpoints, so we simply join our w
table above with our earlier tables z
and get our final answer:
WITH setup AS (SELECT setval('aoc',2,false))
,x AS (SELECT * FROM setup, aoc_day10)
,y AS (SELECT com, nextval('aoc') AS cycle, CASE WHEN com='noop' THEN 0
ELSE nextval('aoc')*0 + substr(com,6)::int END AS warp FROM x)
,z AS (SELECT *, 1+sum(warp) over(order by cycle) AS newwarp FROM y)
,checkpoints (cp) AS (VALUES (20),(60),(100),(140),(180),(220))
,w AS (SELECT distinct max(cycle) over(partition by cp) AS score, cp FROM z, checkpoints
WHERE cycle = cp-1 OR cycle = cp-2)
SELECT sum(newwarp*cp) FROM z JOIN w ON (score=cycle);
sum
-------
17020
Part Two presents a rather convoluted scheme for turning these instructions into a small grid that will output something useful. It's based on a moving sprite, with the idea that pixel will be on or off as the sprite moves along, eventually creating a 40 x 6 pixel screen. We can use some of the same CTEs as above, but will add a new one named z2
that does a lot of work to transform things into a strictly monotonically increasing list of rows for which we determine if the pixel should be lit or not. The generate_series
plus the LEFT JOIN
ensures that we go from 1 to 250, adding in information from our CTE z
only if it exists. When it does, we pull the closest value we can for the matching number with a subselect on the z
CTE again.
WITH setup AS (SELECT setval('aoc',2,false))
,x AS (SELECT * FROM setup, aoc_day10)
,y AS (SELECT com, nextval('aoc') AS cycle, CASE WHEN com='noop' THEN 0
ELSE nextval('aoc')*0 + substr(com,6)::int END AS warp FROM x)
,z AS (SELECT *, 1+sum(warp) over(order by cycle) AS myx FROM y)
,z2 AS (
SELECT *, CASE WHEN myx IS NULL THEN CASE WHEN cc=1 THEN 1
ELSE (SELECT myx FROM z WHERE cycle < cc ORDER BY cycle DESC LIMIT 1) END
ELSE myx END AS better
FROM generate_series(0,250) cc
LEFT JOIN z on (cc = cycle)
)
SELECT * FROM z2 limit 10;
cc | com | cycle | warp | myx | better
----+----------+-------+------+-----+--------
0 | ☃ | ☃ | ☃ | ☃ | ☃
1 | ☃ | ☃ | ☃ | ☃ | 1
2 | noop | 2 | 0 | 1 | 1
3 | noop | 3 | 0 | 1 | 1
4 | addx 5 | 4 | 5 | 6 | 6
5 | ☃ | ☃ | ☃ | ☃ | 6
6 | addx 21 | 6 | 21 | 27 | 27
7 | ☃ | ☃ | ☃ | ☃ | 27
8 | addx -16 | 8 | -16 | 11 | 11
9 | ☃ | ☃ | ☃ | ☃ | 11
Finally, we run it again to import into a new table, and create a function to draw the contents of that table, splitting things every 40 entries.
DROP TABLE if exists crt_screen;
CREATE TABLE crt_screen (cc int, better int, diffy int);
WITH setup AS (SELECT setval('aoc',2,false))
,x AS (SELECT * FROM setup, aoc_day10)
,y AS (SELECT com, nextval('aoc') AS cycle, CASE WHEN com='noop' THEN 0
ELSE nextval('aoc')*0 + substr(com,6)::int END AS warp FROM x)
,z AS (SELECT *, 1+sum(warp) over(order by cycle) AS myx FROM y)
,z2 AS (
SELECT *, CASE WHEN myx IS NULL THEN CASE WHEN cc=1 THEN 1
ELSE (SELECT myx FROM z WHERE cycle < cc ORDER BY cycle DESC LIMIT 1) END
ELSE myx END AS better
FROM generate_series(0,250) cc
LEFT JOIN z on (cc = cycle)
)
INSERT INTO crt_screen
SELECT 1+cc, better, abs(cc - (40*(cc/40)) -better) AS diffy
FROM z2 ;
CREATE or replace FUNCTION drawscreen()
returns void language plpgsql as $$
DECLARE
mymsg text = ''; myrec record;
BEGIN
FOR myrec in SELECT cc, diffy FROM crt_screen ORDER BY cc LOOP
IF 0 = myrec.cc%40 THEN
RAISE NOTICE '%', mymsg;
mymsg = '';
ELSE
mymsg = mymsg || CASE WHEN myrec.diffy < 2 THEN '#' ELSE ' ' END;
END IF;
END LOOP;
RETURN;
END;
$$;
Look what happens when we run it!
SELECT drawscreen();
You get RLEZFLGE
.
NOTICE: ## # #### #### #### # ## ####
NOTICE: # # # # # # # # # #
NOTICE: # # # ### # ### # # ###
NOTICE: ### # # # # # # ## #
NOTICE: # # # # # # # # # #
NOTICE: # # #### #### #### # #### ### ####
That concludes the first ten days of Advent of Code using Postgres! After the Christmas break, I will try and pick this up again.
Related Articles
- Postgres Partitioning with a Default Partition
16 min read
- Iceberg ahead! Analyzing Shipping Data in Postgres
8 min read
- PostGIS Day 2024 Summary
8 min read
- Crunchy Data Warehouse: Postgres with Iceberg for High Performance Analytics
8 min read
- Loading the World! OpenStreetMap Import In Under 4 Hours
6 min read