Advent of Code - Day 12

AOC Day 12 Tech used: • file_fdw to read in the input file

• Parse the input with sequences, the row_number() function, and the regexp_split_to_table() function • An IDENTITY column • Two very similar plpgsql functions (which really should be rolled into one!) • Various text arrays populated and depopulated via || and array_remove

For this challenge, we are tasked with finding the shortest route through a grid, in which the "height" of each item in the grid determines if you can move a certain direction or not. First, the usual setup, including a generic sequence.


DROP SEQUENCE if exists aoc;
CREATE SEQUENCE aoc;



SELECT left(line,30) FROM aoc_day12 LIMIT 10;

              left
--------------------------------
 abccccccccccccccccccccaaaaaaaa
 abcccccccccccccccccccaaaaaaaaa
 abccccccccccccccccccaaaaaaaaaa
 abccccccccccaaacaaacaaacaaaccc
 abccccccccaaaaaccaaaaaccaaaccc
 abccccccccaaaaaaccaaaaaaaaaaac
 abccccccccaaaaaaaaaaaaaaaaaaac
 abccccccccaaaaacaaaaaccaaaaaaa
 abccccccccaaaaacaacaaacaaaaaaa
 abcaaccccccccccccccaaaccaaaaaa
(10 rows)

Each line of the input file contains a long string of characters from a-z, representing the height. So we basically have a three dimensional grid, as we are given a row (the line), columns (characters), and height (what the characters represent). We need to split each line into individual characters, using a sequence to track what column it is in, and using the row_number() windowing function to track what row we are in. Each time a new line is read in, we reset our column count to 1 via the setval call:


WITH x AS (SELECT setval('aoc',1,false), line FROM aoc_day12)
,xgrid AS (
  SELECT row_number() over() AS row, nextval('aoc') AS col,
  regexp_split_to_table(line, '') AS height
FROM x)
SELECT * FROM xgrid LIMIT 10;

row | col | height
-----+-----+--------
   1 |   1 | a
   1 |   2 | b
   1 |   3 | c
   1 |   4 | c
   1 |   5 | c
   1 |   6 | c
   1 |   7 | c
   1 |   8 | c
   1 |   9 | c
   1 |  10 | c
(10 rows)

Let's create and populate a table to hold this information, with the addition of a unique "id" column at the end:


DROP TABLE if exists heightmap;
CREATE UNLOGGED TABLE heightmap(
  row    int,
  col    int,
  height char,
  id     INT GENERATED ALWAYS AS IDENTITY
);

WITH x AS (SELECT setval('aoc',1,false), line from aoc_day12)
,xgrid AS (
  SELECT row_number() over() AS row, nextval('aoc') AS col,
  regexp_split_to_table(line, '') AS height
FROM x)
INSERT INTO heightmap SELECT * FROM xgrid;

The goal is to find the shortest path from a start point to an end point, with the limitation that you can only move up one "higher" character. I solved this by a simple brute force searching by starting at the first place and radiating outward in all four directions until the destination is found. Probably best to let the function speak for itself at this point:


CREATE or replace FUNCTION climber()
  returns void language plpgsql AS $$
DECLARE
  myrec record;
  direction int;
  currentq int[]; visited int[]; warp record;
  startpoint int; endpoint int;  xcost int[];
  lowestcost int = 0; cost int = 0;
BEGIN

  UPDATE heightmap SET height = 'a' WHERE height='S' RETURNING id INTO startpoint;
  UPDATE heightmap SET height = 'z' WHERE height='E' RETURNING id INTO endpoint;

  currentq = currentq || startpoint;

  visited = visited || startpoint;

  <<xx>> LOOP

    cost = cost + 1;

    FOR myrec IN SELECT * FROM heightmap WHERE id = any(currentq) LOOP
      FOR warp IN values(-1,0),(+1,0),(0,+1),(0,-1) LOOP
        SELECT INTO direction id FROM heightmap
          WHERE row=myrec.row+warp.column1
          AND col=myrec.col+warp.column2
          AND ASCII(height) <= ASCII(myrec.height)+1;
        IF direction IS NULL OR direction = any(visited) THEN CONTINUE; END IF;
        IF direction = endpoint THEN EXIT xx; END IF;
        currentq = direction || currentq;

        visited = visited || direction;
      END LOOP;

      currentq = array_remove(currentq, myrec.id);

    END LOOP;

    IF currentq[1] IS NULL THEN EXIT; END IF;

  END LOOP;

RAISE NOTICE 'Got to the end! Lowest cost is %', cost;
RETURN;
END;
$$;

Before running, we should create a functional index to help the query out:


CREATE INDEX heightmap_helper on heightmap ( row, col, ascii(height) );

We also want to copy the table, so we can restore it quickly, as the function modifies the rows:


DROP TABLE if exists heightmap_template;
CREATE TABLE heightmap_template AS SELECT * FROM heightmap;

After a few seconds, the function spits out the correct answer:


select climber();



NOTICE:  Got to the end! Lowest cost is 490
 climber
---------

(1 row)

On to Part Two of the challenge. This time, there are multiple possible starting points, but the goal is the same - the shortest route to the ending point. Rather than worrying about where to start, we simply flip it around and find the shortest path from the end to any of the beginnings. Once that is done, the two major changes are to ignore the "endpoint" and change the winning condition from matching the endpoint to matching any a character:

IF 'a' = newheight THEN
  EXIT xx;  -- leave the main loop END IF;

Before running, we need to reset our points to their original values:


TRUNCATE TABLE heightmap;
INSERT INTO heightmap OVERRIDING SYSTEM VALUE SELECT * FROM heightmap_template;

The final function looks like this:


CREATE or replace FUNCTION climber2()
  returns void language plpgsql AS $$
DECLARE
  myrec record; warp record;
  direction int;  startpoint int; cost int = 0;
  currentq int[]; visited int[];
  newheight char;
BEGIN
  UPDATE heightmap SET height = 'a' WHERE height='S';
  UPDATE heightmap SET height = 'z' WHERE height='E' RETURNING id INTO startpoint;
  currentq = currentq || startpoint;
  visited = visited || startpoint;
  <<xx>> LOOP
    cost = cost + 1;
    FOR myrec IN SELECT * FROM heightmap WHERE id = any(currentq) LOOP
      FOR warp IN values(-1,0),(+1,0),(0,+1),(0,-1)  LOOP
        SELECT INTO direction,newheight
                    id,height
        FROM heightmap
        WHERE row=myrec.row+warp.column1 AND col=myrec.col+warp.column2
        AND   ASCII(height) >= ASCII(myrec.height)-1;
        IF direction IS NULL OR direction = any(visited) THEN CONTINUE; END IF;
        IF 'a' = newheight THEN
          EXIT xx; 
        END IF;
        currentq = direction || currentq;
        visited = visited || direction;
      END LOOP; 
      currentq = array_remove(currentq, myrec.id);
    END LOOP; 
    IF currentq[1] IS NULL THEN EXIT; END IF;
  END LOOP;
  RAISE NOTICE 'Found a path! Cost is %', cost;
  RETURN;
END;
$$;

Running it now gives the new correct value:


select climber2();


NOTICE:  Found a path! Cost is 488
 climber2
----------

(1 row)nocopy

That's the end of Day 12! Stay tuned for further solutions.

Loading terminal...