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

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

Avatar for Greg Sabino Mullane

Greg Sabino Mullane

9 min read

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.