Advent of Code - Day 8

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:

The plpgsql language
The window function row_number()
A sequence to misuse
The regexp_split_to_table() function

The challenge file looks like this:

3041021012313252202444225543366262
1242223102410220252216340212034562
2314324313515524120356365625343141


SELECT * FROM aoc_day8 LIMIT 3;

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 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); 
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:

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 plpgsql 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 itis 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
    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;
    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;
    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;
    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
-------
    1684

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
    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;
    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;
    SELECT INTO score COALESCE(MIN(row),123456) FROM grid 
        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;
    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...

Loading terminal...