How to Solve Advent of Code 2022 Using Postgres - Day 5
Spoiler Alert!
This article will contain spoilers both on how I solved 2022 Day 5's challenge "Supply Stacks" 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 5's challenge if you want to try it with a pre-loaded data set.
AOC Day 5
This challenge was a fun one, in which I actually used SQL to make some animation to represent what happened during the challenge: stacks of crates getting moved around by a crane. To do this, some of the Postgres features used were:
- file_fdw, a built-in foreign data wrapper for Postgres
- Multiple PL/pgSQL functions to move the crates, and draw the output
- The
generate_series()
function to help populate empty rows - The upsert feature (aka
ON CONFLICT...
) - A "backwards" sequence
The input file looked like this:
[D]
[N] [C]
[Z] [M] [P]
1 2 3
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
Basically, this is a simple grid consisting of rows and columns, plus directions on how to move things around. The first challenge is to take that text file and turn it into a table which we will name cargotable
. As before, we are going to use file_fdw to help read things in. The input is too complex to do anything except read in the entire line at once:
CREATE EXTENSION if not exists file_fdw;
CREATE SERVER if not exists aoc2022 foreign data wrapper file_fdw;
DROP FOREIGN TABLE if exists aoc_day5;
CREATE FOREIGN TABLE aoc_day5 (line text)
SERVER aoc2022 options(filename '/tmp/aoc2022.day5.input', delimiter ',');
SELECT * FROM aoc_day5 LIMIT 10;
line
--------------------
[D]
[N] [C]
[Z] [M] [P]
1 2 3
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
Each number in the ASCII art above represents a stack (the y axis), and the other direction (the x axis) represents the height of the stack. A single letter indicates what is at each position, so we create this table:
DROP TABLE if exists cargotable cascade;
CREATE TABLE cargotable (
stack smallint,
height smallint,
cargo char
);
CREATE UNIQUE INDEX cargoslot ON cargotable(stack,height);
To start our conversion, we need to pick out every line that has a left bracket in it, then assign a height to it. Because the file is read from "top to bottom", but the heights make visual sense as "bottom to top", we use a sequence to assign the height, but tell it to count backwards:
DROP SEQUENCE if exists aoc;
CREATE SEQUENCE aoc start with 3 increment by -1 maxvalue 3;
SELECT nextval('aoc') AS height, line FROM aoc_day5 WHERE line ~ '\[';
height | line
--------+-------------
3 | [D]
2 | [N] [C]
1 | [Z] [M] [P]
Now we can populate our new table. We also want to fill in any gaps so we create a bunch of empty slots as well by using the generate_series()
function along with an upsert to ignore rows that already exist:
WITH setup AS (SELECT setval('aoc',3,false))
,x AS (SELECT nextval('aoc') as height, line from aoc_day5, setup where line ~ '\[')
,z as (
SELECT height, stack, substring(line from ((stack*4)-2) for 1) as cargo
FROM x, generate_series(1,3) stack)
INSERT INTO cargotable select stack,height,cargo FROM z;
INSERT INTO cargotable(stack,height,cargo)
SELECT xstack, xheight, '' FROM generate_series(1,3) xstack, generate_series(1,5) xheight
ON CONFLICT DO NOTHING;
The problem has some ASCII art - so why can't we generate some as well?! Let's make a function to transform the items inside the table into a graphical view of the stacks and what they contain:
CREATE or replace FUNCTION showcargo() -- version 1
returns void language plpgsql AS $$
DECLARE
maxstack int; mycargo char; myrow text = '';
BEGIN
SELECT INTO maxstack max(stack) FROM cargotable;
FOR h in REVERSE (SELECT max(height) from cargotable)..1 LOOP
myrow = format('%s height %s%s | ',
myrow, case when h < 10 then ' ' else '' end, h);
FOR s IN 1..maxstack LOOP
SELECT INTO mycargo cargo from cargotable where height=h and stack=s;
myrow = myrow || case when mycargo ~ '[A-Z]'
then '['||mycargo||'] ' else ' ' END;
END LOOP;
myrow = myrow || chr(10);
END LOOP;
myrow = myrow || ' +';
FOR x in 1..maxstack LOOP myrow = myrow || '----'; END LOOP;
myrow = myrow || chr(10) || ' stack: ';
FOR x in 1..maxstack LOOP myrow = myrow || ' '||x; END LOOP;
RAISE WARNING '%', chr(10)||myrow;
RETURN;
END;
$$;
Most of the function should be self-explanatory. We force a new line by adding the CHR(10)
. We are not doing traditional output, but using a RAISE WARNING
to spit out the images, which will help us more later on. Let's see the output:
SELECT showcargo();
WARNING:
height 5 |
height 4 |
height 3 | [D]
height 2 | [N] [C]
height 1 | [Z] [M] [P]
=============
stack: 1 2 3
Next we need a way to move the crates around. Moving a crate just means emptying out the current location (i.e. a stack, height combination) and writing the cargo into a new location. So a couple of updates, based on the direction we are moving. A job for a simple PL/pgSQL function. This one takes four arguments: the stack and height of the thing to be moved, the direction to move it, and how many times to move it.
CREATE OR REPLACE FUNCTION movecargo --version 1
(mystack int, myheight int, dir text, amount int)
returns void language plpgsql AS $$
DECLARE
mycargo char;
BEGIN
SELECT INTO mycargo cargo FROM cargotable WHERE stack=mystack AND height=myheight;
WHILE amount>0 LOOP
UPDATE cargotable SET cargo='' WHERE stack=mystack and height=myheight;
IF dir = 'up' THEN myheight = myheight + 1; END IF;
IF dir = 'left' THEN mystack = mystack - 1; END IF;
IF dir = 'down' THEN myheight = myheight - 1; END IF;
IF dir = 'right' THEN mystack = mystack + 1; END IF;
UPDATE cargotable SET cargo=mycargo WHERE stack=mystack AND height=myheight;
PERFORM showcargo();
amount = amount - 1;
END LOOP;
RETURN;
END;
$$;
We also have it call the showcargo
function after each move. When a command has no place to put the results in PL/pgSQL, you replace the SELECT
with PERFORM
. So moving the letter N
up two slots would look like this:
SELECT movecargo(1,2,'up',2);
WARNING:
height 5 |
height 4 |
height 3 | [N] [D]
height 2 | [C]
height 1 | [Z] [M] [P]
================
stack: 1 2 3 4
WARNING:
height 5 |
height 4 | [N]
height 3 | [D]
height 2 | [C]
height 1 | [Z] [M] [P]
================
stack: 1 2 3 4
Lower it down again (not shown): SELECT movecargo(1,4,'down',2);
Next we will need a function to translate our move 3 from 1 to 2
input to actual calls to the movecargo()
function. Simply warping things to our new location would be cheating, so let's make sure we pick each crate up to a proper height, slide it over, and then lower it into place. This is not just ASCII art, this is going to be ASCII animation! Let's modify our showcargo
function to have it take two more arguments, so we can highlight the current 'active' crate:
CREATE or replace FUNCTION showcargo(mystack int, myheight int) --version 2
returns void language plpgsql AS $$
DECLARE
mycargo char; h int; myrow text = ''; maxstack int;
BEGIN
PERFORM pg_sleep(0.4);
SELECT INTO maxstack max(stack) FROM cargotable;
FOR h in REVERSE (SELECT max(height) from cargotable)..1 LOOP
myrow = format('%s height %s%s | ', myrow, case when h<10 then ' ' ELSE '' END, h);
for s IN 1..maxstack LOOP
SELECT INTO mycargo cargo from cargotable where height=h and stack=s;
myrow = myrow || CASE WHEN mycargo ~ '[A-Z]'
THEN (CASE WHEN h=myheight AND s=mystack
THEN '>'||mycargo||'< '
ELSE '['||mycargo||'] ' END
)
ELSE ' 'END;
END LOOP;
myrow = myrow || chr(10);
END LOOP;
myrow = myrow || ' ';
FOR x in 1..maxstack loop myrow = myrow || '===='; end loop;
myrow = myrow || chr(10) || ' stack: ';
FOR x in 1..maxstack loop myrow = myrow || ' '||x; end loop;
RAISE WARNING '% %', E'\033c', chr(10)||myrow;
RETURN;
END;
$$;
We made three changes to this function:
- There is a sleep at the very top, so that multiple quick calls to this function are slowed down just a tiny bit. We put it at the top of the function to make it easy to find and tweak.
- The current cargo (passed as an arguments) changes from
[X]
to>X<
- We store all of our changes into a single string, then output it via a RAISE WARNING at the end. The
\033c
is a special escape code that should perform a clear screen on most terminals. This also has the side effect of hiding theWARNING:
that would otherwise show up.
We also need to make a minor change to our movecargo
function and have it use the new two-argument version of the showcargo
function:
CREATE OR REPLACE FUNCTION movecargo --version 2
(mystack int, myheight int, dir text, amount int)
returns void language plpgsql AS $$
DECLARE
mycargo char;
BEGIN
SELECT INTO mycargo cargo FROM cargotable WHERE stack=mystack AND height=myheight;
WHILE amount>0 LOOP
UPDATE cargotable SET cargo='' WHERE stack=mystack and height=myheight;
IF dir = 'up' THEN myheight = myheight + 1; END IF;
IF dir = 'left' THEN mystack = mystack - 1; END IF;
IF dir = 'down' THEN myheight = myheight - 1; END IF;
IF dir = 'right' THEN mystack = mystack + 1; END IF;
UPDATE cargotable SET cargo=mycargo WHERE stack=mystack AND height=myheight;
PERFORM showcargo(mystack, myheight);
amount = amount - 1;
END LOOP;
RETURN;
END;
$$;
Finally, it is time for our cratemover
function, which will make repeated calls to movecargo
:
CREATE OR REPLACE FUNCTION cratemover(xfrom int, xto int, repeat int) --version 1
returns void language plpgsql AS $$
DECLARE
currstack int; currheight int; maxheight int; newheight int; content text;
BEGIN
perform pg_sleep(0.3);
FOR x in 1..repeat LOOP
currstack = xfrom;
-- Find the maximum height from current to target stack
SELECT INTO maxheight COALESCE(MAX(height),0)+2 FROM cargotable WHERE length(cargo)=1
AND (CASE WHEN xto < xfrom THEN stack>=xto AND stack<=xfrom
ELSE stack<=xto AND stack>=xfrom END);
-- Find the height and name of the top item in the source stack
SELECT INTO currheight MAX(height) FROM cargotable WHERE stack=xfrom AND length(cargo)=1;
SELECT INTO content cargo FROM cargotable WHERE stack=xfrom AND height=currheight;
-- Find where to put on the target stack (which may be empty)
SELECT INTO newheight COALESCE(MAX(height),0)+1 FROM cargotable WHERE stack=xto AND length(cargo)=1;
-- Raise it up a safe distance
PERFORM movecargo(currstack, currheight, 'up', maxheight-currheight);
currheight = maxheight;
-- Slide it to the correct stack
IF xto < xfrom THEN PERFORM movecargo(currstack, currheight, 'left', currstack - xto);
ELSE PERFORM movecargo(currstack, currheight, 'right', xto - currstack);
END IF;
currstack = xto;
-- Lower it down, then redraw without the cargo highlighted
PERFORM movecargo(currstack, currheight, 'down', currheight - newheight);
PERFORM showcargo(0,0);
END LOOP;
RETURN;
END;
$$;
Now we can run it against the test data and see the result!
WITH directions AS (
SELECT substring(line FROM 'move (.+?) ')::int AS move,
substring(line FROM 'from (.+?) ')::int AS source,
substring(line FROM 'to (.+)')::int AS dest
FROM aoc_day5
WHERE line ~ 'move'
)
SELECT cratemover(source, dest, move) FROM directions;
The solution to the problem calls for all the top crates in order:
WITH x AS (SELECT stack, max(height) from cargotable where length(cargo)=1 group by 1 order by 1)
SELECT c.cargo from cargotable c, x where c.stack=x.stack and c.height=x.max order by c.stack;
cargo
-------
C
M
Z
(3 rows)
The real input is a lot larger (9 stacks, and 500 directional commands), so it did require a little bit of adjusting:
TRUNCATE table cargotable;
-- Changed to "8" and "9":
WITH setup AS (SELECT setval('aoc',8,false))
,x AS (SELECT nextval('aoc') as height, line from aoc_day5, setup where line ~ '\[')
,z as (
SELECT height, stack, substring(line from ((stack*4)-2) for 1) as cargo
FROM x, generate_series(1,9) stack)
INSERT INTO cargotable select stack,height,cargo FROM z;
-- Changed "9" and "100":
INSERT INTO cargotable(stack,height,cargo)
SELECT xstack, xheight, '' FROM generate_series(1,9) xstack, generate_series(1,100) xheight
ON CONFLICT DO NOTHING;
You will also need to adjust the showcargo
function if you want the SQL command to finish by sundown. You can simply add a RETURN;
right after the BEGIN, or you can slow things down a lot by changing the sleep to PERFORM sleep(0);
Here is what it looks like with the sleep reduced, running against the actual data:
The final output for part 1:
cargo
-------
C
F
F
H
V
V
H
N
C
(9 rows)
For part two of the challenge, the crane was revealed to be not a CrateMover 9000 but a CrateMover 9001! This means that rather than picking up crates one at a time, it can lift any number of crates at once and move them to a new stack. Thus, the order of the crates is not flipped, but remains the same. As it was getting late, I did not animate this, just did a quick solution by making a function that moved them one at a time, but starting at the bottom of the current group, thus achieving the same effect as moving the whole block at once.
CREATE OR REPLACE FUNCTION cratemover9001(xfrom int, xto int, repeat int)
returns void language plpgsql AS $$
DECLARE
currstack int; currheight int; maxheight int; newheight int; content text;
BEGIN
FOR X IN 1..repeat LOOP
currstack = xfrom;
-- Find the height and name of the item we are moving
SELECT INTO currheight height FROM cargotable WHERE stack=xfrom and length(cargo)=1
ORDER BY height DESC LIMIT 1 OFFSET repeat-X;
SELECT INTO content cargo FROM cargotable WHERE stack=xfrom and height=currheight;
SELECT INTO newheight COALESCE(MAX(height),0)+1 FROM cargotable WHERE stack=xto AND length(cargo)=1;
-- Set it into place
UPDATE cargotable SET cargo='' WHERE stack=currstack AND height=currheight;
UPDATE cargotable SET cargo=content WHERE stack=xto AND height=newheight;
END LOOP;
RETURN;
END;
$$;
To get the final solution, we reset our table, and run the directions against our new table:
TRUNCATE table cargotable;
WITH setup AS (SELECT setval('aoc',8,false))
,x AS (SELECT nextval('aoc') as height, line from aoc_day5, setup where line ~ '\[')
,z as (
SELECT height, stack, substring(line from ((stack*4)-2) for 1) as cargo
FROM x, generate_series(1,9) stack)
INSERT INTO cargotable select stack,height,cargo FROM z;
INSERT INTO cargotable(stack,height,cargo)
SELECT xstack, xheight, '' FROM generate_series(1,9) xstack, generate_series(1,100) xheight
ON CONFLICT DO NOTHING;
WITH directions AS (
SELECT substring(line FROM 'move (.+?) ')::int AS move,
substring(line FROM 'from (.+?) ')::int AS source,
substring(line FROM 'to (.+)')::int AS dest
FROM aoc_day5
WHERE line ~ 'move'
)
SELECT cratemover9001(source, dest, move) FROM directions;
WITH x AS (SELECT stack, max(height) from cargotable where length(cargo)=1 group by 1 order by 1)
SELECT c.cargo from cargotable c, x where c.stack=x.stack and c.height=x.max order by c.stack;
cargo
-------
F
S
Z
W
B
P
T
B
G
(9 rows)
Done! That one took a lot to explain, so expect a short break before we tackle Day 6. :)