Toboggan Trajectory
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-04-14 19:52:34

## [Advent of Code 2020 Day 3](https://adventofcode.com/2020/day/3)

## [Try the simulator!](https://aoctoboggantrajectory.rmion.repl.co/)
![Simulator of Parts 1 and 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fv3nk518c6gl229wyy75.gif)

## 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!](https://aoctoboggantrajectory.rmion.repl.co/)
![Simulator of Parts 1 and 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fv3nk518c6gl229wyy75.gif)

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

Thus, this puzzle felt especially easy to solve.