Advent of Code - 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]

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 SEQUENCE if exists aoc;
CREATE SEQUENCE aoc;

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
 FOR myrec in SELECT * FROM signal LOOP
    rpos = 0; lpos = 0; myindex = myindex + 1;
    myrec.l = regexp_replace(myrec.l, '10', ':', 'g');
    myrec.r = regexp_replace(myrec.r, '10', ':', 'g');
    LOOP
      lpos = lpos + 1; rpos = rpos + 1;

      IF rpos > length(myrec.r) THEN in_order = false; EXIT; END IF;
      IF lpos > length(myrec.l) THEN in_order = true; EXIT; END IF;

      SELECT INTO lval ascii( substr(myrec.l,lpos,1) );
      SELECT INTO rval ascii( substr(myrec.r,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
        myrec.l = overlay(myrec.l placing '['||chr(lval)||']' from lpos for 1);
        CONTINUE;
      END IF;

      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;
    IF in_order THEN correctq = correctq || myindex; END IF;
  END LOOP;

  lval = 0; rval = 0;
LOOP
    lval = lval + 1;
    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
----------------
4863

Part Two called for sorting all the packets, then adding in a custom pair of items, and see where they fall in the sorted outout. 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
    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;

      IF in_order THEN
        IF newstring ~ '2' THEN before = before + 1; ELSE after = after + 1; END IF;
     END IF;

       END LOOP; 
  END LOOP;
  END LOOP;

  RETURN before * after;

END;
$$;

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


SELECT signal_sifter2();

 signal_sifter2
----------------
21942
(1 row)

Loading terminal...