Advent of Code - Day 5

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:

Multiple plpgsql 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.


SELECT * FROM aoc_day5;


        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()
  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 plpgsql 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
  (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 plpgsql, 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)
  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 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
  (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)
  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;
     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);
   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;
   SELECT INTO newheight COALESCE(MAX(height),0)+1 FROM cargotable WHERE stack=xto AND length(cargo)=1;
   PERFORM movecargo(currstack, currheight, 'up', maxheight-currheight);
   currheight = maxheight;
   IF xto < xfrom THEN PERFORM movecargo(currstack, currheight, 'left', currstack - xto);
   ELSE                PERFORM movecargo(currstack, currheight, 'right', xto - currstack);
   END IF;
   currstack = xto;
   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! For this, I did psql -f cargo.sql where cargo.sql contains:


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)

Done! That one took a lot to explain, so expect a short break before we tackle Day 6. :)

Loading terminal...