Introducing Crunchy Data Warehouse: A next-generation Postgres-native data warehouse. Crunchy Data Warehouse Learn more

Advent of Code

How to Solve Advent of Code 2022 Using Postgres - Day 5

Avatar for Greg Sabino Mullane

Greg Sabino Mullane

13 min read

cargotable_moving

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:

  1. 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.
  2. The current cargo (passed as an arguments) changes from [X] to >X<
  3. 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 the WARNING: 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;

cargotable_moving

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. :)

Related Articles