Toboggan Trajectory

Advent of Code 2020 Day 3

Try the simulator!

Task: Solve for X where...

X = the number of trees hit for each of N trajectories

1. N = 1
2. N = 5

Example input

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

It represents:

• A forrest area
• Where '.'s are open areas and '#'s are trees

Part 1

1. Identifying the correct mental model
2. Using modulo to implement this model
3. Writing a working algorithm

Identifying the correct mental model

• The instructions indicate that the forrest area expands infinitely to the right
• That is represented one way, like this:

..##.........##.........##.........##.........##.........##.......
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#

A path from north-west to south-east would look like this:

-
   -
      -
         -
            -
               -
                  -
                     -
                        -
                           -
                              -
                                 -

But the trick to this challenge is shifting from that mental model, to more of a spiral staircase...or cylindrical model:

-
   -
      -
         -
            -
-
   -
      -
         -
            -
-
   -
      -
         -
            -

Using modulo to implement this model

• The resulting path for Part 1's trajectory for the example input looks like this:

O.##.......
#..O#...#..
.#....X..#.
..#.#...#O#
.X...##..#.
..#.X#.....
.#.#.#.O..#
.#........X
#.X#...#...
#...#X....#
.#..#...X.#

-
   -
      -
         -
 -
    -
       -
          -
   -
      -
         -

0
   3
      6
         9
 1
    4
       7
          10
  2
     5
        8

• Going from 0 to 3, to 6, to 9 is easy
• But from 9 to 1? How would we do that?

Modulo calculates the remainder after dividing one value by another.

• The example input has lines with 11 characters
• 9 % 11 == 9
• (9 + 3) % 11 == 12 % 11 == 1

Voila! Using modulo, the line length, the current index and the appropriate offset...gets us the correct horizontal location in each iteration.

Writing a working algorithm

Split the input at each new-line character into an array of strings
  Split each string into an array of characters

Set variables for row, col and hits...all starting at 0

As long as the location in the processed input at row exists
  Increment hits by 1 if the value at the row and column is a #
  Increment row by 1
  Update col to equal the remainder after dividing the sum of col and 3 by the length of the nested array

Return the value stored in hits

Part 2

1. Understanding the scope creep
2. Writing an updated working algorithm
3. Building the simulator

Understanding the scope creep

• Part 1 featured a single trajectory: (3,1)
• Part 2 features five trajectories
• Therefore, my algorithm must now generate the number of hits for all five trajectories...then calculate the product of all

Writing an updated working algorithm

Split the input at each new-line character into an array of strings
  Split each string into an array of characters

Set an array with five 2-element arrays to represent each trajectory

For each trajectory
  Change the 2-element array into the number of hits encountered by following these operations:
    Set variables for row, col and hits...all starting at 0

    As long as the location in the processed input at row exists
      Increment hits by 1 if the value at the row and column is a #
      Increment row by the value at location 1 from the original 2-element array
      Update col to equal the remainder after dividing the sum of col and the value at location 2 from the original 2-element array by the length of the nested array

Return the product after multiplying each value together

Building the simulator

• I wanted to render the path for each trajectory for any valid input
• When pressing the button corresponding to a trajectory, the forrest area should reset and then progressively render each X and O

Try the simulator!

Thankfully, I encountered this spiral-like algorithm in some puzzles from 2021.

Thus, this puzzle felt especially easy to solve.