Advent of Code - Day 10

AOC Day 10

Today's challenge was a fairly simple one, solved with the help of a few items:

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 cannotuse a delimiter option in our foreign table declaration.



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 pixele 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();

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.

Loading terminal...