DEV Community

Cover image for Toboggan Trajectory
Robert Mion
Robert Mion

Posted on

Toboggan Trajectory

#adventofcode #algorithms #computerscience #programming

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)