DEV Community

Cover image for Toboggan Trajectory
Robert Mion
Robert Mion

Posted on

Toboggan Trajectory

Advent of Code 2020 Day 3

Try the simulator!

Simulator of Parts 1 and 2

Task: Solve for X where...

X = the number of trees hit for each of N trajectories
Enter fullscreen mode Exit fullscreen mode
  1. N = 1
  2. N = 5

Example input

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#
Enter fullscreen mode Exit fullscreen mode

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:
..##.........##.........##.........##.........##.........##.......
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#
Enter fullscreen mode Exit fullscreen mode

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

-
   -
      -
         -
            -
               -
                  -
                     -
                        -
                           -
                              -
                                 -
Enter fullscreen mode Exit fullscreen mode

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

-
   -
      -
         -
            -
-
   -
      -
         -
            -
-
   -
      -
         -
            -
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!
Simulator of Parts 1 and 2

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

Thus, this puzzle felt especially easy to solve.

Top comments (0)