Skip to content

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)

 

  • Twitter
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at del.icio.us
  • Facebook
  • Google Bookmarks
  • FriendFeed
  • Digg Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3
  • Bloglines Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3
  • Technorati Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3
  • Fark this: Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at YahooMyWeb
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at Furl.net
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at reddit.com
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at blinklist.com
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at Spurl.net
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at Simpy.com
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 at blogmarks
  • Bookmark Advent of Code 2020: &quot;Toboggan Trajectory&quot; - Day 3 with wists
  • wong it!
  • Bookmark using any bookmark manager!
  • Stumble It!
  • Identi.ca

Trackbacks

No Trackbacks

Comments

Display comments as Linear | Threaded

No comments

Add Comment

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.
E-Mail addresses will not be displayed and will only be used for E-Mail notifications.
To leave a comment you must approve it via e-mail, which will be sent to your address after submission.
Form options