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

Posted by ads' corner on Thursday, 2020-12-03
Posted in [Sql]

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.

 ``````1 2 3 4 5 6 `````` ``````DROP TABLE IF EXISTS day3; CREATE TABLE day3 ( id SERIAL NOT NULL PRIMARY KEY, value TEXT ); ``````

 ``````1 2 3 4 5 6 7 `````` ``````COPY day3 (value) FROM STDIN; ....#..#.................#..#.. #..#.#.#..#.###.#..#...#..#.... .#....#......#.#.#..##...#...#. .............#.#..#........#.#. ............##.#..#...##.###... \. ``````

A total of `323` rows in the table:

 ``````1 2 3 4 5 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````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:

 ``````1 2 3 4 5 `````` ``````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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````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:

 ``````1 2 3 4 5 6 7 `````` ``````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
• `numrow`s: 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:

 ``````1 2 3 4 `````` ``````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.

 ``````1 2 `````` `````` 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:

 ``````1 `````` `````` numrow := numrow + movedown; ``````

And then I fetch the row from the table:

 ``````1 2 3 4 `````` `````` -- 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:

 ``````1 2 3 4 5 `````` `````` -- 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:

 ``````1 2 3 4 5 6 `````` `````` -- \$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:

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

All the function code in one piece:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 `````` ``````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:

 ``````1 2 3 4 5 `````` ``````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:
 ``````1 2 3 4 5 `````` ``````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) ``````