## Advent of Code 2020: "Toboggan Trajectory" - Day 3

Have to admit, on first glance this challenge looks a bit complicated. It's well suited for languages which can do string manipulations, but it's not well suited for PostgreSQL. Earlier today I already looked at this problem together with the kid, in Python. Therefore I already knew that I have to jump multiple rows as well. To sum it up: adjust x, including overruns, jump multiple rows in y direction, count trees along the way. All in a single SQL query.

Decided to do the map search in a pl/pgSQL instead, and write a function for it.

Task 1: you get a map of "." and "#", where the "#" are trees. You get instructions to move a certain number of steps into x and y direction, and see if there is a tree. Then repeat until the end of the map. A detail problem is that the number of fields in x direction is smaller than the y direction. There are no clear instructions how to handle this, but the correct solution is to just start at the leftmost position again.

Task 2: Repeat the task from task 1, but 5 times with 5 different instructions for x and y movement. The resulting numbers are to be multiplied.

### Preparation

As usual, I load the data into a table in PostgreSQL. This time I not only have a column with the TEXT data (the forst), but I also need an ID which I use to query specific rows later on. In order to do that I add a SERIAL column to the table.

``````DROP TABLE IF EXISTS day3;

CREATE TABLE day3 (
id      SERIAL NOT NULL PRIMARY KEY,
value   TEXT
);``````

``````COPY day3 (value) FROM STDIN;
....#..#.................#..#..
#..#.#.#..#.###.#..#...#..#....
.#....#......#.#.#..##...#...#.
.............#.#..#........#.#.
............##.#..#...##.###...
\.``````

A total of 323 rows in the table:

``````SELECT COUNT(*) FROM day3;
count
-------
323
(1 row)``````

There is however a small problem: since I want to access the rows by ID, I need to make sure that the IDs are strictly monotonous, and start with 1. The 1 I ensure by creating the table from scratch, this also creates a fresh sequence for the ID. Let's check if the IDs are monotonous:

``````SELECT (COUNT(*) > 0)
FROM (SELECT day3.*, LAG(id) OVER (ORDER BY id) AS prev_value
from day3
) day3
WHERE prev_value > id;

?column?
----------
f
(1 row)``````

No divergence, good.

And I need to know the total length of the rows:

``````SELECT MIN(LENGTH(value)), MAX(LENGTH(value)) FROM day3;
min | max
-----+-----
31 |  31
(1 row)``````

Every row is 31 characters. I will encode that into the pl/pgSQL function later.

Since I already know that I have to jump different rows and columns, I create he function in a way which can handle both x and y. A pl/pgSQL function has a header, which defines the name, input types (if any), and the return type. And at the end the used language is specified.

``````DROP FUNCTION IF EXISTS day3_walk_trees(movedown INT, moveright INT);
CREATE FUNCTION day3_walk_trees(movedown INT, moveright INT)
RETURNS INT
AS
\$\$

...

END;
\$\$
LANGUAGE plpgsql;``````

A pl/pgSQL function can have an optional DECLARE block to define variables used in the function:

``````DECLARE
numrow INT DEFAULT 0;
numcolumn INT DEFAULT 0;
numtrees INT DEFAULT 0;
lengthrow INT DEFAULT 31;
numrows INT;
thisrow TEXT;``````
• numrow: holds the current row number, starts with 0
• numcolumn: holds the current column number, starts with 0
• numtrees: number of trees found, starts with 0
• lengthrow: the length of each text row, for easyness I looked this up before and hardcode it to 31 here
• numrows: number of rows in the table
• thisrow: a TEXT variable used to fetch the row I'm working on in the function

The first task is to find out how many rows the field has. I could have done that before as well, but I thought I leave this in the function as an exercise:

``````BEGIN
-- need the number of entries in the table
SELECT COUNT(*) INTO numrows FROM day3;
-- RAISE NOTICE 'Number rows: %', numrows;``````

This query populates numrows with the number of rows in the table. The query is static, as in: can't be changed in the function. And the "SELECT ... INTO" form is not to be confused with the same syntax in regular SQL. In a pl/pgSQL function this will store the result into the variable after INTO.

Next I need to loop over the field. For that I already know that I might have to jump multiple lines, therefore a simple loop over each line is not sufficient. Hence I also need to know the number of rows before: this way I can have a while loop which runs as long as numrow is smaller than numrows.

``````    WHILE numrow < (numrows - 1) LOOP
-- RAISE NOTICE 'number: %', numrow;``````

Inside the while loop I first increase the line number by the number of y steps:

``        numrow := numrow + movedown;``

And then I fetch the row from the table:

``````        -- need the row with the \$numrow number
-- careful, it's off by one, numrow = 0 equals id = 1
SELECT value INTO thisrow FROM day3 WHERE id = numrow + 1;
-- RAISE NOTICE '%', thisrow;``````

Strictly speaking I don't need to fetch the entire row: I could combine this step with the next step and just fetch the one character I'm interested in. But it's cleaner this way.

In the next step I move the number of x steps sideways. And if there is an overrun, I just take the remaining number of steps and start again with them:

``````        -- move sideways number steps from \$moveright
-- and if the new position exceeds length of the field
-- then start at the beginning
numcolumn := (numcolumn + moveright) % lengthrow;
-- RAISE NOTICE 'numcolumn: %', numcolumn;``````

Finally now that I have the line, and know which position in the line I can select the character and see if that is a tree:

``````        -- \$thisrow has the line with the trees, need the character from \$numcolumn
-- again \$numcolumn = 0 equals the first character (1)
IF SUBSTRING(thisrow FROM (numcolumn + 1) FOR 1) = '#' THEN
-- it's a tree, be careful with the reindeers!
numtrees := numtrees + 1;
END IF;``````

At the end return the number of trees:

``````    -- return number of trees
RETURN numtrees;``````

All the function code in one piece:

``````DROP FUNCTION IF EXISTS day3_walk_trees(movedown INT, moveright INT);
CREATE FUNCTION day3_walk_trees(movedown INT, moveright INT)
RETURNS INT
AS
\$\$
DECLARE
numrow INT DEFAULT 0;
numcolumn INT DEFAULT 0;
numtrees INT DEFAULT 0;
lengthrow INT DEFAULT 31;
numrows INT;
thisrow TEXT;
BEGIN
-- need the number of entries in the table
SELECT COUNT(*) INTO numrows FROM day3;
-- RAISE NOTICE 'Number rows: %', numrows;

WHILE numrow < (numrows - 1) LOOP
-- RAISE NOTICE 'number: %', numrow;
numrow := numrow + movedown;
-- need the row with the \$numrow number
-- careful, it's off by one, numrow = 0 equals id = 1
SELECT value INTO thisrow FROM day3 WHERE id = numrow + 1;
-- RAISE NOTICE '%', thisrow;

-- move sideways number steps from \$moveright
-- and if the new position exceeds length of the field
-- then start at the beginning
numcolumn := (numcolumn + moveright) % lengthrow;
-- RAISE NOTICE 'numcolumn: %', numcolumn;

-- \$thisrow has the line with the trees, need the character from \$numcolumn
-- again \$numcolumn = 0 equals the first character (1)
IF SUBSTRING(thisrow FROM (numcolumn + 1) FOR 1) = '#' THEN
-- it's a tree, be careful with the reindeers!
numtrees := numtrees + 1;
END IF;
END LOOP;

-- return number of trees
RETURN numtrees;
END;
\$\$
LANGUAGE plpgsql;``````

Now I have one function which can move arbitrary steps into x and y direction. All what is to do to solve task one is to execute the function:

``````SELECT day3_walk_trees(1, 3);
day3_walk_trees
-----------------
237
(1 row)``````

Repeat this 5 times with 5 different walking instructions, and multiply the resulting number of trees:

``````SELECT day3_walk_trees(1, 1)  day3_walk_trees(1, 3)  day3_walk_trees(1, 5)  day3_walk_trees(1, 7)  day3_walk_trees(2, 1);
?column?
------------
2106818610
(1 row)``````