How to Solve Advent of Code 2022 Using Postgres - Day 12
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:
- 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:
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.
