Toboggan Trajectory
Robert Mion
Posted on April 14, 2022
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
- N = 1
- N = 5
Example input
..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#
It represents:
- A forrest area
- Where '.'s are open areas and '#'s are trees
Part 1
- Identifying the correct mental model
- Using
moduloto implement this model - 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
- Understanding the scope creep
- Writing an updated working algorithm
- 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
Thankfully, I encountered this spiral-like algorithm in some puzzles from 2021.
Thus, this puzzle felt especially easy to solve.
💖 💪 🙅 🚩
Robert Mion
Posted on April 14, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
