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.

1
2
3
4
5
6
DROP TABLE IF EXISTS day3;

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

And load the data:

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.

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.

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

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)

Task 2

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)

Categories: [Sql]

Tags: [Advent] [Advent-of-Code] [Challenge] [Plpgsql] [Postgresql] [Psql] [Sql]

Preparation

Task 1

Task 2

Friends