How to Solve Advent of Code 2022 Using Postgres - Day 8
Spoiler Alert!
This article will contain spoilers both on how I solved 2022 Day 8's challenge "Treetop Tree House" 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 8's challenge if you want to try it with a pre-loaded data set.
AOC Day 8
This challenge asks us to take a grid of numbers and compare the "views" as we look either north, south, east, or west from various locations. Overall, a fairly simple challenge. Amongst the assortment of tools to solve it were:
- file_fdw, a built-in foreign data wrapper for Postgres
- The PL/pgSQL language
- The
window function
row_number() - A sequence to misuse
- The
regexp_split_to_table()function
The challenge file looks like this:
30373
25512
65332
33549
35390
Each number in the grid represents a tree as a potential location of a treehouse. Our task is to find the one most hidden from outside viewing. The numbers represent the height - taller trees block shorter ones. A tree is considered visible if it can be seen from outside the grid. We want a total count of all trees in this grid that are NOT blocked by some other tree when viewed from the four directions north, south, east, and west. As always, we import the file into a foreign table. This time we'll be good citizens and put things into a separate namespace (aka schema) to keep things tidy:
CREATE EXTENSION if not exists file_fdw;
CREATE SERVER if not exists aoc2022 foreign data wrapper file_fdw;
DROP SCHEMA if exists tree CASCADE;
CREATE SCHEMA tree;
SET search_path = tree;
DROP FOREIGN TABLE if exists aoc_day8;
CREATE FOREIGN TABLE aoc_day8 (line text)
SERVER aoc2022 options(filename '/tmp/aoc2022.day8.input');
DROP SEQUENCE if exists aoc;
CREATE SEQUENCE if not exists aoc;
We need to transform our lines of digits into a proper grid, so we use the
row_number() function to increment our "rows" once per line, and a sequence to
increment out "column" once per letter. Each letter is put into its own row by
use of regexp_split_to_table. We end up with a 3-D table structure of one row
representing a single tree, with it's three coordinates (row,column,height):
WITH x AS (SELECT setval('aoc',1,false), line FROM aoc_day8)
,xgrid AS (
SELECT row_number() over() AS row, nextval('aoc') AS col,
regexp_split_to_table(line, '')::int AS height
FROM x)
SELECT * FROM xgrid LIMIT 10;
row | col | height
-----+-----+--------
1 | 1 | 3
1 | 2 | 0
1 | 3 | 3
1 | 4 | 7
1 | 5 | 3
2 | 1 | 2
2 | 2 | 5
2 | 3 | 5
2 | 4 | 1
2 | 5 | 2
(10 rows)
While we could keep building this into a complex CTE, let's create a proper table and store things in there. For performance reasons, we will make this table unlogged, which means it is not tracked by WAL. The downside with unlogged tables is that on a server restart, the table gets truncated, but for a one-time process like this, the tradeoff is worth it.
DROP TABLE if exists grid;
CREATE UNLOGGED TABLE grid (
row smallint,
col smallint,
height smallint,
north bool not null default true,
east bool not null default true,
south bool not null default true,
west bool not null default true
);
CREATE INDEX grid_rch ON grid (row,col,height); -- this really, really helps for large data sets
WITH x AS (SELECT setval('aoc',1,false), line FROM aoc_day8)
,xgrid AS (
SELECT row_number() over() AS row, nextval('aoc') AS col,
regexp_split_to_table(line, '')::int AS height
FROM x)
INSERT INTO grid SELECT * FROM xgrid;
To solve this problem, we are going to walk from the tallest groups of trees to the smallest. For each direction, we can look down the row or column and find the first tree at the specified height. Any trees before the "first" tree are visible; any ones after it are not. If we look back at our grid and look at the first column from the north:
| North | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| West |
| East | |||||||||||||||||||||||||
| South |
We can see that the tree at height 6 means that anyone looking from the north
down the column will not be able to see the two trees at height 3. But they will
be able to see the first two trees at heights 3 and 2, as well as 6 itself (but
once we consider trees at height three, we know the 2 will be blocked as well).
We can put this logic into a PL/pgSQL function. Note the use of the REVERSE
keyword so our FOR loop runs backwards from the normal usage. We mark each
tree/direction as false once we know it is not visible. For the UPDATE
commands, we also add in a final check so that we do not flip items to false
that are already false - this is an important optimization for things that get
updated a lot, as an update in Postgres, due to the way it implements MVCC,
means inserting a new row and deleting another one.
CREATE or replace FUNCTION treewalker()
returns void language plpgsql as $$
DECLARE myrec record;
BEGIN
FOR h in REVERSE 9..0 LOOP
-- Looking from the north
FOR myrec IN select col, min(row) as minrow from grid where height=h group by 1 LOOP
UPDATE grid set north=false where col=myrec.col and height<=h and row > myrec.minrow and north is true;
END LOOP;
-- Looking from the south
FOR myrec IN select col, max(row) as maxrow from grid where height=h group by 1 LOOP
UPDATE grid set south=false where col=myrec.col and height<=h and row < myrec.maxrow and south is true;
END LOOP;
-- Looking from the east
FOR myrec IN select row, max(col) as maxcol from grid where height=h group by 1 LOOP
UPDATE grid set east=false where row=myrec.row and height<=h and col < myrec.maxcol and east is true;
END LOOP;
-- Looking from the west
FOR myrec IN select row, min(col) as mincol from grid where height=h group by 1 LOOP
UPDATE grid set west=false where row=myrec.row and height<=h and col > myrec.mincol and west is true;
END LOOP;
END LOOP;
RETURN;
END;
$$;
To get the final answer, we run the function, then grab all the trees that are NOT blocked by any of the four directions:
SELECT treewalker();
SELECT count(*) FROM grid WHERE south OR north OR west OR east;
count
-------
21
For part two of the challenge, we need to find the best place to put the treehouse based on it "scenic view", or the number of trees that are visible from the tree house in each direction, multiplied together. This is a slight variation of the previous task. To start, let's create a column in our table to track the new variable:
ALTER TABLE grid ADD scenic_score int;
Then we create a new function that walks through each tree in the grid, determines how many trees are visible in each direction (up, down, left, right)
CREATE or replace FUNCTION treefinder()
returns void language plpgsql as $$
DECLARE
mytree record; score int;
upview int; leftview int; downview int; rightview int;
BEGIN
FOR mytree IN SELECT * FROM grid ORDER BY row, col LOOP
-- How far up can we see?
SELECT INTO score COALESCE(MAX(row),0) FROM grid
WHERE col=mytree.col AND row < mytree.row AND height >= mytree.height;
SELECT INTO upview count(*) FROM grid
WHERE col=mytree.col AND row < mytree.row AND row >= score;
-- How far left can we see?
SELECT INTO score COALESCE(MAX(col),0) FROM grid
WHERE row=mytree.row AND col < mytree.col AND height >= mytree.height;
SELECT INTO leftview count(*) FROM grid
WHERE row=mytree.row AND col < mytree.col AND col >= score;
-- How far down can we see?
SELECT INTO score COALESCE(MIN(row),123456) FROM grid -- 123456 effectively infinity for viewing
WHERE col=mytree.col AND row > mytree.row AND height >= mytree.height;
SELECT INTO downview count(*) FROM grid
WHERE col=mytree.col AND row > mytree.row AND row <= score;
-- How far right can we see?
SELECT INTO score COALESCE(MIN(col),123456) FROM grid
WHERE row=mytree.row AND col > mytree.col AND height >= mytree.height;
SELECT INTO rightview count(*) FROM grid
WHERE row=mytree.row AND col > mytree.col AND col <= score;
UPDATE grid SET scenic_score = upview * leftview * downview * rightview
WHERE row=mytree.row AND col=mytree.col;
END LOOP;
RETURN;
END;
$$;
SELECT treefinder();
SELECT scenic_score FROM grid ORDER BY 1 DESC LIMIT 5;
scenic_score
--------------
486540
470596
198450
191760
165984
(5 rows)
That's all for Day 8. Next up is something snakey...
