## 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
);
```

And load the data:

```
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.

### Task 1

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)
```

### Task 2

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)

## Comments

Display comments as Linear | Threaded