Fun with PostgreSQL Puzzles: Moving Objects...

Solving Advent of Code 2022 using Postgres - Day 17

aoc_tetris6

(Yes, this image was generated completely by SQL statements!)

Hands on Tutorial

We've also loaded a tutorial for Day 17's challenge if you want to try it with a pre-loaded data set.

This article will contain spoilers both on how I solved 2022 Day 17's challenge "Pyroclastic Flow" 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.

Pyroclastic Flow

Another puzzle featuring elephants! (❤️ ❤️ ❤️). This time, the elephants are involved in a suspiciously familiar game involving falling rocks of various shapes. The rocks get blown by jets as they fall, and the goal is to figure out the height of the final tower of rocks after a certain number of them have fallen.

The litany of SQL/Postgres/other items used to solves this puzzle include:

🦛 Making sequences act as global variables.

🦛 The file_fdw extension, to read text files in from the system.

🦛 Various Unicode characters to enhance our graphics game.

🦛 Functions in plpgsql especially for looping and organization.

🦛 The jsonb_array_elements_text() function to allow a quick navigation to critical information.

🦛 Unlogged tables and unlogged sequences to speed things up.

🦛 The point data type, stored in arrays for easy access.

🦛 The very handy string_agg function, for creating a "checksum" of a bunch of row information.

Following the link to Day 17 will give a lot more details about the challenge, you may want to read that first. We have an input file that looks like this:

>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>

Part One

The first part of the challenge asks us how high the tower of rocks will be after 2022 rocks have fallen. For this challenge, I decided to store the position of the rocks inside a simple table, indicating the X and Y coordinates (as "row" and "col"), and a "val" column to indicate what is at that position (either part of a rock, or just air). There are more efficient ways to do it, such as a bitstring per row, but part of the fun is animating it, and for that we need to know what type of rock is at each point. First, some usual setup steps:

CREATE EXTENSION if not exists file_fdw;

CREATE SERVER if not exists aoc2022 foreign data wrapper file_fdw;

DROP SCHEMA if exists aoc_falling_rocks CASCADE;
CREATE SCHEMA aoc_falling_rocks;
SET search_path = aoc_falling_rocks;

CREATE FOREIGN TABLE aoc_day17 (line text)
  SERVER aoc2022 options(filename '/tmp/aoc2022.day17.input');

Here is our simple unlogged table:

CREATE UNLOGGED TABLE chamber (col int, row int, val char);
CREATE UNIQUE INDEX onerow ON chamber(col,row);

The unique index is there to support an ON CONFLICT DO NOTHING clause later on, as a lazy way to insert rows into the table without worrying about if something is already there or not.

We need to create some unlogged sequences, which will track some global information about the current rock's position, its type, and the total rocks used:

CREATE UNLOGGED SEQUENCE aoc_rock;
CREATE UNLOGGED SEQUENCE aoc_row;
CREATE UNLOGGED SEQUENCE aoc_col;
CREATE UNLOGGED SEQUENCE aoc_total MINVALUE 0;
-- or if on Postgres 14 or older:
CREATE SEQUENCE aoc_rock;
CREATE SEQUENCE aoc_row;
CREATE SEQUENCE aoc_col;
CREATE SEQUENCE aoc_total MINVALUE 0;

Because sequences start at 1, we force aoc_total to accept 0 with MINVALUE 0.

Rather than one big ugly function, we'll break things into separate tasks.

Adding a new rock

In this function, we figure out where a new rock will go and update the chamber table to add it in:

CREATE or replace FUNCTION addrock()
  /* Adds a new rock to the "top" of the chamber */
  returns void language plpgsql AS $$
DECLARE
  current_floor INT; new_rock_number INT; mypoint POINT;

  /* Postgres has support for points, so use those to describe our rocks */
  rockpaths POINT[][] = ARRAY[
    [(0,0),(1,0),(2,0),(3,0)], /* HLINE      */
    [(0,1),(1,1),(2,1),(1,2)], /* CIRCLE 1,0 */
    [(1,0),(2,0),(2,1),(2,2)], /* ANGLE 0,0  */
    [(0,0),(0,1),(0,2),(0,3)], /* VLINE      */
    [(0,0),(0,1),(1,0),(1,1)]  /* BOX        */
  ];

BEGIN
  /* Find the current "floor" as the spot where no blocks appear */
  SELECT INTO current_floor row FROM chamber WHERE val <> '-' ORDER BY row desc LIMIT 1;

  /* Grab the next rock from our queue of five */
  new_rock_number = CASE WHEN 6=nextval('aoc_rock')
    THEN setval('aoc_rock',1) /* Store as a "global" var! */
    ELSE currval('aoc_rock') END;

 /* We need a fast table, which we update a lot
    Therefore, every so often, we rebuild the entire thing
    as a subset of the important "top" rows */
  IF 0 = currval('aoc_total') % 40 THEN
    RAISE LOG 'Creating new table at %', current_floor;
    CREATE UNLOGGED TABLE newchamber AS select * from chamber where row > current_floor - 100;
    DROP TABLE chamber;
    CREATE UNIQUE INDEX newonerow ON newchamber(col,row);
    ALTER TABLE newchamber RENAME TO chamber;
  END IF;

  /* Add seven empty rows to hold the new rock and space above it */
  INSERT INTO chamber(row,col,val)
    SELECT zrow,zcol, '-'
    FROM generate_series(current_floor,current_floor+7) AS zrow,
         generate_series(1,7) AS zcol
    ON CONFLICT(row,col) DO NOTHING;

  /* Add the new rock to the top */
  FOR x IN 1..4 LOOP
    /* All rocks have at least four sections */
    mypoint = rockpaths[new_rock_number][x];
    UPDATE chamber SET val = new_rock_number WHERE row = current_floor+4+mypoint[1] AND col=3+mypoint[0];
  END LOOP;

  /* Some rock shapes need a special tweak */
  IF new_rock_number = 2 THEN UPDATE chamber SET val=new_rock_number
      WHERE row=current_floor+4 AND col=4; END IF;
  IF new_rock_number = 3 THEN UPDATE chamber SET val=new_rock_number
    WHERE row=current_floor+4 AND col=3; END IF;

  /* Set the new positions and increment total rocks served */
  PERFORM setval('aoc_row', current_floor+4);
  PERFORM setval('aoc_col', 3);
  PERFORM nextval('aoc_total');

  RETURN;
END;
$$;

Moving an existing rock

This function will attempt to shift a rock in one of three directions.

CREATE or replace FUNCTION blowrock (dir TEXT)
  returns bool language plpgsql AS $fn$
  /* Attempts to move the current rock */
  /* Returns true if moved, false if blocked */
DECLARE
  mycol INT; myrow INT; myrock INT; mypoint POINT; y POINT;
  newcol INT; newrow INT;
  checker TEXT; oppochecker TEXT;
  colwarp INT; rowwarp INT;

  rockpaths POINT[][] = ARRAY[
    [(0,0),(0,0),(1,0),(2,0),(3,0)], /* HLINE  */
    [(1,0),(0,1),(1,1),(2,1),(1,2)], /* CIRCLE */
    [(0,0),(1,0),(2,0),(2,1),(2,2)], /* ANGLE  */
    [(0,0),(0,0),(0,1),(0,2),(0,3)], /* VLINE  */
    [(0,0),(0,0),(0,1),(1,0),(1,1)]  /* BOX    */
  ];

  shapeinfo JSONB = '{
    "leftedge": {
      "1": ["0,0"],
      "2": ["1,0","0,1","1,2"],
      "3": ["0,0","2,1","2,2"],
      "4": ["0,0","0,1","0,2","0,3"],
      "5": ["0,0","0,1"]
    },
    "rightedge": {
      "1": ["3,0"],
      "2": ["1,0","2,1","1,2"],
      "3": ["2,0","2,1","2,2"],
      "4": ["0,0","0,1","0,2","0,3"] ,
      "5": ["1,0","1,1"]
    },
    "downedge": {
      "1": ["0,0","1,0","2,0","3,0"],
      "2": ["0,1","1,0","2,1"],
      "3": ["0,0","1,0","2,0"],
      "4": ["0,0"],
      "5": ["0,0","1,0"]
    },
    "upedge": {
      "1": ["0,0","1,0","2,0","3,0"],
      "2": ["0,1","1,2","2,1"],
      "3": ["0,0","1,0","2,2"],
      "4": ["0,3"],
      "5": ["0,1","1,1"]
    }
}';

BEGIN

  /* Grab the coords and number of the current rock */
  SELECT INTO mycol,myrow,myrock
    currval('aoc_col'), currval('aoc_row'), currval('aoc_rock');

  /* If going left or right (i.e. not down), check if we have hit the side walls */
  IF dir <> 'v' THEN
    FOR x in 1..5 LOOP
      mypoint = rockpaths[myrock][x];
      newcol = mycol + mypoint[0] + (CASE WHEN dir='<' THEN -1 WHEN dir='>' THEN +1 ELSE 0 END);
      IF newcol < 1 OR newcol > 7 THEN RETURN false; END IF;
    END LOOP;
  END IF;

  /* Check if the edge in new direction is clear */
  checker = CASE WHEN dir='<' THEN 'leftedge' WHEN dir='>' THEN 'rightedge' ELSE 'downedge' END;
  oppochecker = CASE WHEN dir='<' THEN 'rightedge' WHEN dir='>' THEN 'leftedge' ELSE 'upedge' END;
  colwarp = CASE WHEN dir='<' THEN -1 WHEN dir='>' THEN +1 ELSE 0 END;
  rowwarp = CASE WHEN dir='v' THEN -1 ELSE 0 END;

  /* For each place we are about to move, verify it does not already have a rock */
  FOR y IN SELECT jsonb_array_elements_text(shapeinfo->checker->myrock::text) LOOP
    PERFORM 1 FROM chamber WHERE col = mycol+y[0]+colwarp AND row=myrow+y[1]+rowwarp AND val = '-';
    IF NOT FOUND THEN RETURN false; END IF;
  END LOOP;

  /* Clear, so remove the opposite edge */
  FOR y IN SELECT jsonb_array_elements_text(shapeinfo->oppochecker->myrock::text) LOOP
    UPDATE chamber SET val = '-' WHERE col = mycol+y[0] AND row=myrow+y[1];
  END LOOP;

  /* Add in the new edge */
  FOR y IN SELECT jsonb_array_elements_text(shapeinfo->checker->myrock::text) LOOP
    UPDATE chamber SET val = myrock WHERE col = mycol+y[0]+colwarp AND row=myrow+y[1]+rowwarp;
  END LOOP;

  /* Set the new information for our current rock */
  IF dir = '<' THEN PERFORM setval('aoc_col', mycol-1); END IF;
  IF dir = '>' THEN PERFORM setval('aoc_col', mycol+1); END IF;
  IF dir = 'v' THEN PERFORM setval('aoc_row', myrow-1); END IF;

  RETURN true;

END;
$fn$;

Drawing the chamber

While not needed to solve the puzzle, here is a function that draws the current chamber. By calling it over and over, we can animate what is happening. Not only does it look cool, but it is very helpful when debugging. Note that this only draws the bottom of the chamber, but that's easy enough to change.

CREATE or replace FUNCTION drawrock (asciionly bool default true)
  returns void language plpgsql AS $$
DECLARE
  myval TEXT; v TEXT; mycolor TEXT = '';
  myoutput TEXT = ''; myfloor TEXT;
BEGIN
  FOR r IN REVERSE 25 .. 1 LOOP
    /* Write the left wall with Unicode 2502 "light vertical" */
    myval = format('%s%s%s',
      E'\x1b[38;5;173m',
      CASE WHEN asciionly THEN '|' ELSE U&'\2502' END,
      E'\033[0m');

    /* Write each column in turn */
    FOR c IN 1..7 LOOP
      SELECT INTO v val FROM chamber WHERE row=r AND col=c;
      /* Set the color based on the type of block
         However, do not set if the color is already in place */
      IF v = '1' AND mycolor <> 'cyan' THEN
        myval = myval || FORMAT('%s%s',
          CASE WHEN mycolor <> '' THEN E'\033[0m' ELSE '' END, E'\x1b[38;5;51m');
        mycolor = 'cyan';
      ELSIF v = '2' AND mycolor <> 'red' THEN
        myval = myval || FORMAT('%s%s',
          CASE WHEN mycolor <> '' THEN E'\033[0m' ELSE '' END, E'\x1b[38;5;196m');
        mycolor = 'red';
      ELSIF v = '3' AND mycolor <> 'blue' THEN
        myval = myval || FORMAT('%s%s',
          CASE WHEN mycolor <> '' THEN E'\033[0m' ELSE '' END, E'\x1b[38;5;21m');
        mycolor = 'blue';
      ELSIF v = '4' AND mycolor <> 'orange' THEN
        myval = myval || FORMAT('%s%s',
          CASE WHEN mycolor <> '' THEN E'\033[0m' ELSE '' END, E'\x1b[38;5;214m');
        mycolor = 'orange';
      ELSIF v = '5' AND mycolor <> 'yellow' THEN
        myval = myval || FORMAT('%s%s',
          CASE WHEN mycolor <> '' THEN E'\033[0m' ELSE '' END, E'\x1b[38;5;227m');
        mycolor = 'yellow';
      ELSIF v = '-' AND mycolor <> '' THEN
        myval = myval || E'\033[0m';
        mycolor = '';
      END IF;

      /* We have a color, now add a Unicode 2588 "full block"  or a space */
      myval = myval || CASE WHEN v <> '-'  THEN
        CASE WHEN asciionly THEN '*' ELSE U&'\2588' END ELSE ' ' END;
    END LOOP;

    /* Turn off the color at the end of the row */
    IF mycolor <> '' THEN myval = myval || E'\033[0m'; mycolor = ''; END IF;

    /* Add the row to our final output string */
    myoutput = format('%s %s        %s %s%s%s%s',
      myoutput, chr(10), ' ', myval, E'\x1b[38;5;173m',
      CASE WHEN asciionly THEN '|' ELSE U&'\2502' END,
      E'\033[0m');
  END LOOP;

  /* Create the floor with Unicode 2580 "upper half block" */
  myfloor = format('%s         %s %s%s',
    chr(10), E'\x1b[38;5;206m',
    repeat(CASE WHEN asciionly THEN '=' ELSE U&'\2580' END, 9),
    E'\033[0m');

  /* Clear the screen, write the content, and finally the floor */
  RAISE NOTICE '% % %', E'\033c', myoutput, myfloor;

  RETURN;
END;
$$;

Shall We Play A Game?

Now that our supporting functions are in place, we can write a function to solve the puzzle, by walking through our input file (via the foreign table aoc_day17), moving the rocks in the direction indicated, and adding a new rock once the existing one cannot move any further.

CREATE or replace FUNCTION insertcoin (stopat INT, drawit INT, sleepy FLOAT)
  returns void language plpgsql AS $$
DECLARE
  nextmove CHAR; x INT = 0; myresult BOOL; mytotal INT;
BEGIN
  /* Just in case, reset everything */
  TRUNCATE TABLE chamber;
  INSERT INTO chamber select q,0,'*' from generate_series(1,27) q;
  PERFORM setval('aoc_row', 1);
  PERFORM setval('aoc_col', 1);
  PERFORM setval('aoc_rock', 1, false);
  PERFORM setval('aoc_total', 0);

  /* Need to start off with one rock already in place */
  PERFORM addrock();

  LOOP
    SELECT INTO nextmove substring(line from x for 1) FROM aoc_day17;
    /* If we hit the end of the file, start over again */
    IF nextmove = '' THEN x=1; CONTINUE; END IF;
    x = x + 1;

    /* Move left or right, ignore the result */
    PERFORM blowrock(nextmove);

    /* Move downward, add a new rock if we are blocked */
    SELECT INTO myresult blowrock('v');
    IF NOT myresult THEN
      SELECT INTO mytotal currval('aoc_total');
      IF mytotal = stopat THEN EXIT; END IF;
      PERFORM addrock();
    END IF;

    /* Optionally create some pretty graphics */
    IF drawit > 0 THEN
      PERFORM drawrock(CASE WHEN drawit > 1 THEN true ELSE false END);
      PERFORM pg_sleep(sleepy);
    END IF;
    /* Every 100 actions, slightly speed things up */
    IF 0 = x%100 then sleepy = sleepy - 0.05; END IF;
  END LOOP;

  RAISE NOTICE 'Total rocks dropped is %', currval('aoc_total');
  RAISE NOTICE 'Total height is %', MAX(row) FROM chamber WHERE val IN ('1','2','3','4','5');

  RETURN;
END;
$$;

Voila! Running it with a 1 as the second argument will produce the graphic seen at the top of this post. If you are on an older terminal that does not support Unicode, use an argument of 2 instead for more basic ASCII art:

SELECT insertcoin(15, 1, 0.4);

To get the answer quicker, we can run without any drawing:

SELECT insertcoin(2022, 0, 0);

Both the test data and the real data took around 20 seconds to run. Here is the output for the test data above:

NOTICE:  Total rocks dropped is 2022
NOTICE:  Total height is 3068

Part Two

For part two is ... well, let's copy the puzzle description verbatim:

The elephants are not impressed by your simulation.
They demand to know how tall the tower will be after 1000000000000
rocks have stopped! Only then will they feel confident enough
to proceed through the cave.

One trillion rocks! That is a very big number! So big it should be obvious that our original approach is not going to work. Indeed, some quick math shows it would take over 300 years to finish. We need a shortcut! We can assume that because we are iterating over the same characters in the input set over and over, there will eventually be a repeating cycle. So our new solution is to devise a way to detect that cycle, skip ahead as close to 1,000,000,000,000 rocks as we can, and get our final answer of how high the rocks are, and make those elephants happy. Here is the function for that:

CREATE or replace FUNCTION trillion_rocks()
  returns void language plpgsql AS $$
DECLARE
  nextmove CHAR; myresult BOOL; x INT = 0; goodx INT;
  target_rocks BIGINT = 1000000000000;
  current_rocks BIGINT;
  firstheight BIGINT; firstrock INT;
  fingerprint TEXT; finger_size INT = 25;
  rockrate INT; heightrate INT;
  rock_check_point INT = 800;
  trillion BIGINT = 1000000000000;
  secondrock BIGINT; secondheight BIGINT;
  current_height BIGINT = 0;
BEGIN
  /* Just in case, reset everything */
  TRUNCATE TABLE chamber;
  INSERT INTO chamber select q,0,'*' from generate_series(1,27) q;
  PERFORM setval('aoc_row', 1);
  PERFORM setval('aoc_col', 1);
  PERFORM setval('aoc_rock', 1, false);
  PERFORM setval('aoc_total', 0);

  /* Need to start off with one rock already in place */
  PERFORM addrock();

  LOOP
    SELECT INTO nextmove substring(line from x for 1) from aoc_day17;
    /* If we hit the end of the file, start over again */
    IF nextmove = '' THEN x=1; CONTINUE; END IF;
    x = x + 1;

    /* Move left or right, ignore the result */
    PERFORM blowrock(nextmove);

    /* Move downward, add a new rock if we are blocked */
    SELECT INTO myresult blowrock('v');
    IF NOT myresult THEN

      /* For the end of part two, we simply have to reach our target goal of 10^12 rocks */
      IF currval('aoc_total') = target_rocks THEN
        /* We store bottom of the rock, so the actual height is more */
        RAISE NOTICE 'Final height is %', current_height + 1 + (currval('aoc_row') - secondheight);
        RETURN;
      END IF;

      PERFORM addrock();

    END IF;

    /* If we already found the fingerprint, just move on */
    IF current_rocks IS NOT NULL THEN CONTINUE; END IF;

    /* Create the fingerprint if we have reached a specific point */
    IF fingerprint IS NULL
       AND currval('aoc_total') = rock_check_point
       AND currval('aoc_rock')=5
    THEN
      /* aoc_row is bottom of the latest rock, aoc_total is number rocks released */
      SELECT INTO firstheight, firstrock currval('aoc_row'), currval('aoc_total');
      SELECT INTO fingerprint x::text || '+' || string_agg(val,'' order by row, col)
        FROM chamber WHERE row > firstheight - finger_size;
      /* Store the exact point in the file this appeared */
      goodx = x;
      RAISE LOG 'Fingerprint: %',  fingerprint;
      CONTINUE;
    END IF;

    /* Each time we hit the same place in the file, check the fingerprint */
    IF x=goodx THEN
      PERFORM 1 FROM (
        SELECT x::text || '+' || string_agg(val,'' order by row, col) AS f FROM chamber
        WHERE row > currval('aoc_row') - finger_size
        ) x
        WHERE f = fingerprint;

      IF found THEN
        /* How many rocks have we dropped at this point? */
        secondrock = currval('aoc_total');
        /* How many rocks are created each loop? */
        rockrate = secondrock - firstrock;
        /* How high is bottom of the current rock? */
        secondheight = currval('aoc_row');
        /* How much height do we gain each loop? */
        heightrate = secondheight - firstheight;

        /* How many more rocks do we need in total to reach our goal? */
        trillion = trillion - secondrock;

        /* Warp ahead and store the number of rocks to get us there */
        current_rocks = secondrock + ((trillion / rockrate) * rockrate);
        PERFORM setval('aoc_total', current_rocks);

        /* Also store our new height */
        current_height = secondheight + ((trillion / rockrate) * heightrate);
        RAISE LOG 'Set current rocks to % and height to %',
          current_rocks, current_height;

      END IF;
    END IF;
  END LOOP;

  RAISE NOTICE '  end: Total rocks dropped is %', currval('aoc_total');
  RAISE NOTICE '  end: Total height is %', MAX(row) FROM chamber WHERE val IN ('1','2','3','4','5');

  RETURN;
END;
$$;

Some of this warrants a little explanation. The idea is that once we reach a certain spot, we want to capture exactly what the top of the pile of rocks looks like. We do that by joining in all the values across all columns for a few rows, via the SQL:

SELECT INTO fingerprint x::text || '+' || string_agg(val,'' order by row, col)
  FROM chamber WHERE row > firstheight - finger_size;

This ends up with a unique string that looks like this:

4754--222--33324---43-4---43-4---4--4---4--55-----55----1111-----2---
--222--3332-11113---3333-----355----355------2-----222----42-----4---
---4------4-------------------------55-----55-----------------

Then we keep scanning until we find that exact fingerprint again - which means that we have entered into a repeating loop, and can thus figure out how high the pile gets for every X rocks that fall. As we want 1 trillion rocks, we get as close as we can to a trillion, and record how many rocks and the total height obtained:

  /* How many more rocks do we need in total to reach our goal? */
  trillion = trillion - secondrock;

  /* Warp ahead and store the number of rocks to get us there */
  current_rocks = secondrock + ((trillion / rockrate) * rockrate);
  PERFORM setval('aoc_total', current_rocks);

  /* Also store our new height */
  current_height = secondheight + ((trillion / rockrate) * heightrate);
  RAISE LOG 'Set current rocks to % and height to %',
  current_rocks, current_height;

Finally, we can check if we have reached our target rock number, each time a rock settles down. When we reach it, we do some quick math to bring things up to a trillion, and output the final height.

  /* For the end of part two, we simply have to reach our target goal of 10^12 rocks */
  IF currval('aoc_total') = target_rocks THEN
    /* We store bottom of the rock, so the actual height is more */
    RAISE NOTICE 'Final height is %', current_height + 1 + (currval('aoc_row') - secondheight);
    RETURN;
  END IF;

This whole process takes about 11 seconds - much better than the original 300 year estimate! Here is what the final result looks like:

SELECT trillion_rocks();

NOTICE:  Final height is 1514285714288

This was a fun one - and if you are of a certain age, you might have some certain music playing in your head as you watch the animation at the top of this post!

Latest Articles

Fun with PostgreSQL Puzzles: Moving Objects with Arrays, Sequences, and Aggregates