Advent of Code - Day 11

This challenge involves a troop of monkeys who have stolen your items and are throwing them around to each other. For this challenge, some of the Postgres / SQL tech we used are:

file_fdw
Yet more non-standard use of sequences via setval and currval
String manipulation functions such as substring, replace, regexp_match, and regexp_substr
Window functions
A handy plpgsql function

The input file describes the attributes of each monkey. It's a very custom format, so we read the whole line as-is after our usual setup:


SELECT * FROM aoc_day11 LIMIT 10;

                     line
----------------------------------------------
 Monkey 0:
   Starting items: 52, 60, 85, 69, 75, 75
   Operation: new = old * 17
   Test: divisible by 13
     If true: throw to monkey 6
     If false: throw to monkey 7

 Monkey 1:
   Starting items: 96, 82, 61, 99, 82, 84, 85
   Operation: new = old + 8
(10 rows)

As we can see, the first challenge will be in transforming the attributes for each monkey in to a more manageable table format. We are going to use a sequence that changes when we see a "Monkey" line, and multiple CASE statements to transform the various lines into the raw information we need from each. We do this for every line, even though each line will only give us one of the attributes for the monkey.


CREATE SEQUENCE aoc MINVALUE 0;
WITH x AS (SELECT line FROM aoc_day11)
, y AS (SELECT case when line ~ 'Monkey' then
         setval('aoc',substring(line, '([0-9]+)')::int) else -1 end AS monkey
  ,currval('aoc') AS num
  ,case when line ~ 'Starting'  then substring(line, ': (.+)') else '' end AS items
  ,case when line ~ 'Operation' then substring(line, '= old (.+)') else '' end AS operation
  ,case when line ~ 'Test'      then substring(line, 'divisible by (\d+)')::int else 0 end AS test
  ,case when line ~ 'If true'   then substring(line, 'monkey (\d+)')::int else -1 end AS yesmonkey
  ,case when line ~ 'If false'  then substring(line, 'monkey (\d+)')::int else -1 end AS nomonkey
FROM x)
SELECT * FROM y LIMIT 10;

 monkey | num |           items            | operation | test | yesmonkey | nomonkey
--------+-----+----------------------------+-----------+------+-----------+----------
      0 |   0 |                            |           |    0 |        -1 |       -1
     -1 |   0 | 52, 60, 85, 69, 75, 75     |           |    0 |        -1 |       -1
     -1 |   0 |                            | * 17      |    0 |        -1 |       -1
     -1 |   0 |                            |           |   13 |        -1 |       -1
     -1 |   0 |                            |           |    0 |         6 |       -1
     -1 |   0 |                            |           |    0 |        -1 |        7
     -1 |   0 |                            |           |    0 |        -1 |       -1
      1 |   1 |                            |           |    0 |        -1 |       -1
     -1 |   1 | 96, 82, 61, 99, 82, 84, 85 |           |    0 |        -1 |       -1
     -1 |   1 |                            | + 8       |    0 |        -1 |       -1
(10 rows)

Now we need combine all those attributes into one row for each monkey. Sharp readers may have noted that the default values for our CASE statements are an empty string, 0, or -1. Why? Because this ensures that any "real" values are always greater than the defaults. Thus, we can sort the values and have the "real" ones come out higher than the default ones. We can use the MAX function to grab each attribute's value for each monkey. We also need to group it by monkey, so we use a DISTINCT num to ensure one monkey per row, and then use our MAX over a window. In this case, we need our window of rows we care about to span each numbered monkey, so we create our window as (PARTITION BY num). Note that rather than writing that after ever line (e.g. MAX(operation) OVER (PARTITION BY num)), we simply create a global window named w that each item in the SELECT clause can refer to.


WITH x AS (SELECT line FROM aoc_day11)
,y AS (SELECT case when line ~ 'Monkey' then
         setval('aoc',substring(line, '([0-9]+)')::int) else -1 end AS monkey
  ,currval('aoc') AS num
  ,case when line ~ 'Starting'  then substring(line, ': (.+)') else '' end AS items
  ,case when line ~ 'Operation' then substring(line, '= old (.+)') else '' end AS operation
  ,case when line ~ 'Test'      then substring(line, 'divisible by (\d+)')::int else 0 end AS test
  ,case when line ~ 'If true'   then substring(line, 'monkey (\d+)')::int else -1 end AS yesmonkey
  ,case when line ~ 'If false'  then substring(line, 'monkey (\d+)')::int else -1 end AS nomonkey
FROM x)
SELECT DISTINCT num
  ,REPLACE(max(items) OVER w ,',','') AS items
  ,max(test) OVER w
  ,max(operation) OVER w
  ,max(yesmonkey) OVER w
  ,max(nomonkey) OVER w
FROM y WINDOW w AS (partition by num) ORDER BY num;

The output looks nice: one line per monkey, and we have captured all the important information for each of the eight monkeys in the input file. We also replaced all the "items" commas with a space, to make things easier later on.

 num |          items          | max |  max  | max | max
-----+-------------------------+-----+-------+-----+-----
   0 | 52 60 85 69 75 75       |  13 | * 17  |   6 |   7
   1 | 96 82 61 99 82 84 85    |   7 | + 8   |   0 |   7
   2 | 95 79                   |  19 | + 6   |   5 |   3
   3 | 88 50 82 65 77          |   2 | * 19  |   4 |   1
   4 | 66 90 59 90 87 63 53 88 |   5 | + 7   |   1 |   0
   5 | 92 75 62                |   3 | * old |   3 |   4
   6 | 94 86 76 67             |  11 | + 1   |   5 |   2
   7 | 57                      |  17 | + 2   |   6 |   2
(8 rows)

While a recusive query is theoretically possible, there are only so many hours in a day, so we'll simply insert things into a table that we can manipulate with custom functions:


DROP TABLE IF EXISTS monkey;
CREATE TABLE monkey (
  num       INT,
  items     TEXT,
  test      INT,
  op        TEXT,
  yes       INT,
  no        INT,
  monkeysee INT
);

Now we can re-run our query, and change the SELECT to an INSERT:


WITH x AS (SELECT line FROM aoc_day11)
,y AS (SELECT case when line ~ 'Monkey' then
         setval('aoc',substring(line, '([0-9]+)')::int) else -1 end AS monkey
  ,currval('aoc') AS num
  ,case when line ~ 'Starting'  then substring(line, ': (.+)') else '' end AS items
  ,case when line ~ 'Operation' then substring(line, '= old (.+)') else '' end AS operation
  ,case when line ~ 'Test'      then substring(line, 'divisible by (\d+)')::int else 0 end AS test
  ,case when line ~ 'If true'   then substring(line, 'monkey (\d+)')::int else -1 end AS yesmonkey
  ,case when line ~ 'If false'  then substring(line, 'monkey (\d+)')::int else -1 end AS nomonkey
FROM x)
INSERT INTO monkey
  SELECT DISTINCT num
    ,REPLACE(max(items) OVER w ,',','') AS items
    ,max(test) OVER w
    ,max(operation) OVER w
    ,max(yesmonkey) OVER w
    ,max(nomonkey) OVER w
  FROM y WINDOW w AS (partition by num) ORDER BY num;

Finally, we are ready to create a function that will execute a given number of rounds, in which the monkeys throw items to each other, and then give a final value based on how many items the top two monkeys threw. Rather than walk through how the function works bit by bit, I used some heavy inline comments:


CREATE or replace FUNCTION monkey_business(maxrounds int)
returns void language plpgsql as $$
DECLARE
  maxmonkey int;
  myrec record;
  myops text[]; mytests int[]; myitems text[]; monkeysee int[]; myway int[]; hiway int[];
  thismonkey int = 0;
  current_item int;
  round int = 1;
  yesno bool;
  newmonkey int;
  x int; y int;
BEGIN

SELECT INTO maxmonkey MAX(num) FROM monkey;

FOR myrec IN SELECT * FROM monkey ORDER BY num LOOP
    myops[myrec.num] = myrec.op;
    mytests[myrec.num] = myrec.test;
    myitems[myrec.num] = myrec.items;
    myway[myrec.num] = myrec.yes;
    hiway[myrec.num] = myrec.no;
    monkeysee[myrec.num] = 0;
  END LOOP;

FOR x IN 1..1000000 LOOP
IF myitems[thismonkey] !~ '\d' THEN
      thismonkey = thismonkey + 1;
      IF thismonkey > maxmonkey THEN round = round + 1; thismonkey = 0; END IF;
      IF round > maxrounds THEN EXIT; END IF;
      CONTINUE;
    END IF;

    current_item = (regexp_match(myitems[thismonkey], '\d+'))[1];

    myitems[thismonkey] = regexp_replace(myitems[thismonkey], ' *\d+', '');

    monkeysee[thismonkey] = monkeysee[thismonkey] + 1;

IF myops[thismonkey] ~ '\* \d+' THEN
      current_item = current_item * (regexp_match(myops[thismonkey], '\d+'))[1]::int;
    ELSIF myops[thismonkey] ~ '\+ \d+' THEN
      current_item = current_item + (regexp_match(myops[thismonkey], '\d+'))[1]::int;
    ELSIF myops[thismonkey] ~ '\* old' THEN
      current_item = current_item * current_item;
    END IF;

    current_item = current_item / 3;

    yesno = 0 = current_item % mytests[thismonkey];
    newmonkey = CASE WHEN yesno THEN myway[thismonkey] ELSE hiway[thismonkey] END;

    myitems[newmonkey] = myitems[newmonkey] || ' ' || current_item;

  END LOOP;

SELECT INTO x MAX(ms) FROM unnest(monkeysee) ms;
  SELECT INTO y ms FROM unnest(monkeysee) ms ORDER BY ms DESC LIMIT 1 OFFSET 1;

  RAISE NOTICE 'Monkey answer for % and %: %', x,y, x::bigint*y::bigint;

  return;
END
$$;


SELECT monkey_business(20);

Running the above gives the correct answer very quickly. For compatibility I used the regexp_match function, but if you are using Postgres 15 or newer you can use the better regexp_substr function:


-- >= v15:   current_item = regexp_substr(myitems[thismonkey], '\d+', 1);
-- <= v14:   current_item = (regexp_match(myitems[thismonkey], '\d+'))[1];

Part Two gets a lot more involved, with the changes being a lot more rounds (from 20 to 10,000) and removal of the current_items = current_items / 3 bit. Simple, right? Of course not, the AOC challenges are more devious than that! Here's the first attempt with just the divided by three part removed:

SELECT monkey_business(10000);

No problem, we will just switch the data type of the current_item variable from an INT to BIGINT!

SELECT monkey_business(10000);

Okay, so we are dealing with some very large numbers here. Surely a NUMERIC will suffice?

SELECT monkey_business(10000);

Well, that's not an error you see too often! Obviously these numbers are way too big, so we need another approach. Taking a closer look at the problem and the sample data, I noticed a few things:

The actual items have no identity - we are simply passing numbers representing those items around, and the values change mid flight.
All the tests are simple "divisible by", which means there are a range of solutions that give the same answer
All the divisor test numbers are prime
Thus, the numbers do not need to stay large - we can shrink them at each round, as long as they still meet the same requirements, e.g. true/false for each "divisible by" test.

So, we need a magic number that all the answers can be divided by. In this case, we simply multiply all those prime numbers together. In our setup loop at the top of the function, we add:

bigmodulo = bigmodulo * myrec.test;

Then instead of dividing by three each round, we can shrink the number using modulo math:

current_item = current_item % bigmodulo;

This worked great, and I was able to move current_item back to a BIGINT and ran 10,000 rounds in a little under 3 seconds! Here is the final version of the function:


CREATE or replace FUNCTION monkey_business(maxrounds int)--version 2returns void language plpgsql as $$
DECLARE
  maxmonkey int;
  myrec record;
  myops text[]; mytests int[]; myitems text[]; monkeysee int[]; myway int[]; hiway int[];
  thismonkey int = 0;
  current_item bigint;
  round int = 1;
  yesno bool;
  newmonkey int;
  x int; y int;
  bigmodulo int = 1;
BEGIN

SELECT INTO maxmonkey MAX(num) FROM monkey;

FOR myrec IN SELECT * FROM monkey ORDER BY num LOOP
    bigmodulo = bigmodulo * myrec.test;
    myops[myrec.num] = myrec.op;
    mytests[myrec.num] = myrec.test;
    myitems[myrec.num] = myrec.items;
    myway[myrec.num] = myrec.yes;
    hiway[myrec.num] = myrec.no;
    monkeysee[myrec.num] = 0;
  END LOOP;

FOR x IN 1..1000000 LOOP
IF myitems[thismonkey] !~ '\d' THEN
      thismonkey = thismonkey + 1;
      IF thismonkey > maxmonkey THEN round = round + 1; thismonkey = 0; END IF;
      IF round > maxrounds THEN EXIT; END IF;
      CONTINUE;
    END IF;

current_item = (regexp_match(myitems[thismonkey], '\d+'))[1];

myitems[thismonkey] = regexp_replace(myitems[thismonkey], ' *\d+', '');

monkeysee[thismonkey] = monkeysee[thismonkey] + 1;

IF myops[thismonkey] ~ '\* \d+' THEN
      current_item = current_item * (regexp_match(myops[thismonkey], '\d+'))[1]::int;
    ELSIF myops[thismonkey] ~ '\+ \d+' THEN
      current_item = current_item + (regexp_match(myops[thismonkey], '\d+'))[1]::int;
    ELSIF myops[thismonkey] ~ '\* old' THEN
      current_item = current_item * current_item;
    END IF;

    IF maxrounds <= 20 THEN current_item = current_item / 3; END IF;

    yesno = 0 = current_item % mytests[thismonkey];
    newmonkey = CASE WHEN yesno THEN myway[thismonkey] ELSE hiway[thismonkey] END;

   current_item = current_item % bigmodulo;

   myitems[newmonkey] = myitems[newmonkey] || ' ' || current_item;

END LOOP;

   SELECT INTO x MAX(ms) FROM unnest(monkeysee) ms;
   SELECT INTO y ms FROM unnest(monkeysee) ms ORDER BY ms DESC LIMIT 1 OFFSET 1;

RAISE NOTICE 'Monkey answer for % and %: %', x,y, x::bigint*y::bigint;

  return;
END
$$;

Hope you enjoyed! Will post some more solutions as time permits.

Loading terminal...