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

Disclaimer

This article will contain spoilers both on how I solved 2022 Day 13's challenge "Distress Signal" 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 13's challenge if you want to try it with a pre-loaded data set.

AOC Day 13

This puzzle was overall very straightforward. The tech we used this time:

• file_fdw to slurp in our puzzle input file
• The lag() function to allow us to view the previous row as we parse the file
• Using a sequence to do some counting
• The regexp_replace() function to sneakily remove our double-digit numbers
• The overlay() function to modify our strings in place as we are parsing them

For this challenge, the goal was to put packets in order, in which each pair consisted of deeply nested arrays like so:

[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

As usual, we create a custom schema and use file_fdw to access the input file:

CREATE EXTENSION if not exists file_fdw;

CREATE SERVER if not exists aoc2022 FOREIGN DATA WRAPPER file_fdw;

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

DROP FOREIGN TABLE if exists aoc_day13;

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

DROP SEQUENCE if exists aoc;
CREATE SEQUENCE aoc;

There are specific rules for determining the correct order based on the numeric values, how to handle arrays compared to non-arrays, etc. While I suspect a lot of solutions jumped to trying to parse the input as actual arrays or json objects and then evaluate them, I immediately saw this as a bit-by-bit type of challenge.

First, I verified some assumptions and made observations about the data:

• Almost everything was one character long, except for the number 10. So if we can change that 10 to something else, things get a lot simpler as we only need to parse a single character at a time.
• The commas are then not needed at all, and can safely be ignored or removed.
• If we can walk through at the same "pace" for both packets, we do not need to worry about which nested array we are currently in.

We can slurp the pairs of packets to compare into a table, with each pair going on a single row, thanks to nextval() for the line number, lag() to grab the previous line, and a special WHERE clause to only grab the correct line so we have two entries:

DROP TABLE if exists signal;
CREATE UNLOGGED TABLE signal(id int, r text, l text);

WITH x AS (SELECT line as l, lag(line) over() AS r FROM aoc_day13)
,y AS (SELECT nextval('aoc') AS id, * FROM x WHERE length(l) >1 AND length(r) > 1)
INSERT INTO signal SELECT * FROM y;

SELECT * FROM signal LIMIT 10;

 id |              r              |              l
----+-----------------------------+-----------------------------
  2 | [1,1,5,1,1]                 | [1,1,3,1,1]
  3 | [[1],4]                     | [[1],[2,3,4]]
  4 | [[8,7,6]]                   | [9]
  5 | [[4,4],4,4,4]               | [[4,4],4,4]
  6 | [7,7,7]                     | [7,7,7,7]
  7 | [3]                         | []
  8 | [[]]                        | [[[]]]
  9 | [1,[2,[3,[4,[5,6,0]]]],8,9] | [1,[2,[3,[4,[5,6,7]]]],8,9]
(8 rows)

Now we need a function that walks through both sides, left and right, and compares them character by character:

CREATE or replace FUNCTION signal_sifter1()
  returns int language plpgsql as $$
DECLARE
 myrec record; lpos int; rpos int; myindex int = 0;
 lval int; rval int; in_order bool; correctq int[];
BEGIN
  -- Walk through each row and compare the left (l) packet with the right (r) one
  FOR myrec in SELECT * FROM signal LOOP
    rpos = 0; lpos = 0; myindex = myindex + 1;
    -- We want single character numbers, so change 10 to a ':'
    -- A colon is one greater than ascii(9)
    myrec.l = regexp_replace(myrec.l, '10', ':', 'g');
    myrec.r = regexp_replace(myrec.r, '10', ':', 'g');
    LOOP
      lpos = lpos + 1; rpos = rpos + 1;

      -- If the right side ran out, wrong order, so break the loop and move on
      IF rpos > length(myrec.r) THEN in_order = false; EXIT; END IF;
      -- Left side ran out: right order
      IF lpos > length(myrec.l) THEN in_order = true; EXIT; END IF;

      -- Extract the ascii value of our current position in both strings
      SELECT INTO lval ascii( substr(myrec.l,lpos,1) );
      SELECT INTO rval ascii( substr(myrec.r,rpos,1) );

      -- If things are equal (numbers,commas, or braces!), just move along
      IF lval = rval THEN CONTINUE; END IF;

      -- If boths sides are numbers from 0-10, one side will win
      IF lval BETWEEN 48 and 58 AND rval BETWEEN 48 and 58 THEN
        in_order = CASE WHEN lval > rval THEN false ELSE true END;
        EXIT;
      END IF;

      -- left has ended, but right has not - ascii(93) is a ]
      IF lval = 93 THEN in_order=true; EXIT; END IF;
      -- right has ended, but left has not
      IF rval = 93 THEN in_order=false; EXIT; END IF;

      -- right has opened, but left is a number - ascii(91) is [
      IF rval = 91 AND lval BETWEEN 48 and 58 THEN
        -- transform in place and keep comparing
        -- expand to an array: 9 becomes [9]
        myrec.l = overlay(myrec.l placing '['||chr(lval)||']' from lpos for 1);
        CONTINUE;
      END IF;

      -- left has opened, but right is a number
      IF lval = 91 AND rval BETWEEN 48 and 58 THEN
        myrec.r = overlay(myrec.r placing '['||chr(rval)||']' from rpos for 1);
        CONTINUE;
      END IF;

      RAISE EXCEPTION 'Cannot handle this case!';

    END LOOP; -- end each character

    -- If the order was correct, add this location to a list
    IF in_order THEN correctq = correctq || myindex; END IF;
  END LOOP;

  -- Sum all the winners up
  lval = 0; rval = 0; -- Might as well re-use these vars
  LOOP
    lval = lval + 1;
    -- Break out of the loop when nothing left in the queue
    IF correctq[lval] IS NULL THEN EXIT; END IF;
    rval = rval + correctq[lval];
  END LOOP;

  RETURN rval;

END;
$$;

Running it produces the correct answer:

SELECT signal_sifter1();

signal_sifter1
----------------
           4734

Part Two called for sorting all the input packets, adding in two custom packets, and figuring out where they fall in the sorted output. Rather than worrying about actually sorting the entire list, we can simply see how many packets fall before or after each of the custom pairs:

CREATE or replace FUNCTION signal_sifter2()
  returns int language plpgsql as $$
DECLARE
  myrec record; lpos int; rpos int;
  lval int; rval int; in_order bool;
  oldstring text; newstring text;
  before int = 1; after int = 2;
BEGIN
  FOR myrec in SELECT * FROM signal LOOP
    -- See signal_sifter1() for additional explanations
    myrec.l = regexp_replace(myrec.l, '10', ':', 'g');
    myrec.r = regexp_replace(myrec.r, '10', ':', 'g');

    FOR oldstring IN values (myrec.l), (myrec.r) LOOP
    FOR newstring IN values ('[[2]]'), ('[[6]]') LOOP
      rpos = 0; lpos = 0;
      LOOP
        lpos = lpos + 1; rpos = rpos + 1;
        IF lpos > length(oldstring) THEN in_order = true; EXIT; END IF;
        IF lpos > length(newstring) THEN in_order = true; EXIT; END IF;

        SELECT INTO lval ascii( substr(oldstring,lpos,1) );
        SELECT INTO rval ascii( substr(newstring,rpos,1) );
        IF lval = rval THEN CONTINUE; END IF;

        IF lval BETWEEN 48 and 58 AND rval BETWEEN 48 and 58 THEN
          in_order = CASE when lval > rval THEN false ELSE true END;
          EXIT;
        END IF;

        IF lval = 93 THEN in_order=true;  EXIT; END IF;
        IF rval = 93 THEN in_order=false; EXIT; END IF;

        IF rval = 91 AND lval BETWEEN 48 and 58 THEN
          oldstring = overlay(oldstring placing '['||chr(lval)||']' from lpos for 1);
          CONTINUE;
        END IF;
        IF lval = 91 AND rval BETWEEN 48 and 58 THEN
          newstring = overlay(newstring placing '['||chr(rval)||']' from rpos for 1);
          CONTINUE;
        END IF;

        RAISE EXCEPTION 'Cannot handle this case!';

      END LOOP;

      -- Count things up based on who we are
      IF in_order THEN
        IF newstring ~ '2' THEN before = before + 1; ELSE after = after + 1; END IF;
     END IF;

       END LOOP; -- end of newstring loop
  END LOOP; -- end of olstring loop
  END LOOP; -- end of each input line

  RETURN before * after;

END;
$$;

Once again, running it gives us the correct answer quickly:

SELECT signal_sifter2();
 signal_sifter2
----------------
          21836
(1 row)

Stay tuned for more days solving Advent of Code using Postgres!