Introducing Crunchy Data Warehouse: A next-generation Postgres-native data warehouse. Crunchy Data Warehouse Learn more

Advent of Code

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

Avatar for Greg Sabino Mullane

Greg Sabino Mullane

7 min read

Spoiler Alert!

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

AOC Day 12

Tech used:

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:

CREATE EXTENSION if not exists file_fdw;

CREATE SERVER if not exists aoc2022 FOREIGN DATA WRAPPER file_fdw;

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

DROP FOREIGN TABLE if exists aoc_day12;

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

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

 -- Record our start and end points, and also change them to the lowest and highest characters:
  UPDATE heightmap SET height = 'a' WHERE height='S' RETURNING id INTO startpoint;
  UPDATE heightmap SET height = 'z' WHERE height='E' RETURNING id INTO endpoint;

  -- This array stores which points we are currently interested in
  currentq = currentq || startpoint;

  -- This array stores points that have already been checked
  visited = visited || startpoint;

  -- In PL/pgSQL, loops can be named with the << .. >> syntax
  <<xx>> LOOP

    -- The cost is how many steps it takes to get from the start to the finish
    cost = cost + 1;

    -- Loop through all the points in the current queue. Order does not matter
    FOR myrec IN SELECT * FROM heightmap WHERE id = any(currentq) LOOP
      -- Try heading north, south, east, and west
      FOR warp IN values(-1,0),(+1,0),(0,+1),(0,-1) LOOP
        -- Pull the id of the current compass direction, if the height allows it
        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;
        -- No match means direction is set to null, so skip it
        -- Also skip if we have already checked on this point
        IF direction IS NULL OR direction = any(visited) THEN CONTINUE; END IF;

        -- If we reached the end, abandon the entire outer loop
        IF direction = endpoint THEN EXIT xx; END IF;

        -- Not at the end, so add this to the queue of places to visit next
        currentq = direction || currentq;

        -- Mark as checked, in case we approach from another direction later
        visited = visited || direction;
      END LOOP; -- end each direction

      -- We finished checking all directions, so remove ourself from the queue
      currentq = array_remove(currentq, myrec.id);

    END LOOP; -- end each item in the queue

    -- If the queue is empty, we are done
    IF currentq[1] IS NULL THEN EXIT; END IF;

  END LOOP; -- Loop back and try out the current queue

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:

postgres=# 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;

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 -- Look N S E W
        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; -- leave the main loop
        END IF;

        currentq = direction || currentq;
        visited = visited || direction;

      END LOOP; -- end checking N S E W

      currentq = array_remove(currentq, myrec.id);

    END LOOP; -- end checking every item in currentq

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

  END LOOP;

  RAISE NOTICE 'Found a path! Cost is %', cost;

  RETURN;
END;

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;

Running it now gives the new correct value:

postgres=# select climber2();

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

(1 row)

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

Related Articles