Advent of Code 2018 Day 22
Task: Solve for X where...
Part 1
X = the total risk level for the smallest rectangle that includes 0,0 and the target's coordinates
Part 2
X = the fewest number of minutes it can take to reach the target
Example input
depth: 510
target: 10,10
It represents:
- Details about a cave system: particularly, it's depth: Y (must be infinitely wide: X)
- Details about the bearded man's friend's X,Y position in the cave system
Part 1
- Working backwards to understand and calculate risk level
- Creating the smallest rectangular area as a data structure
- Calculating each cell's erosion and risk levels
- Highlights of my working algorithm
Working backwards to understand and calculate risk level
To generate the correct answer for Part 1, I need to calculate the sum or several regions' risk levels
.
A risk level can be one of three single-digit integer values:
0 for rocky regions
1 for wet regions
2 for narrow regions
How do I determine the type
of a region?
erosion level modulo (%) 3
How do I determine erosion level
?
( region's geologic index
+ the cave system's depth)
% 20183
The puzzle input will supply the cave system's depth.
How do I determine the region's geologic index
?
1. Is location 0,0?
0
2. Is location target?
0
3. Is location *,0?
From X,0: X * 16807
4. Is location 0,*?
From 0,Y: Y * 48271
5. Else:
erosion level of X-1,Y * erosion level of X,Y-1
The instructions offer five example equations for five coordinates using the example input:
0,0's risk level and type:
Meets rule 1
(0 + 510) % 20183 = 510 % 3 = 0 rocky
1,0's risk level and type:
Meets rule 3
1 * 16807 = (16807 + 510) % 20183 = 17317 % 3 = 1 wet
0,1's risk level and type:
Meets rule 4
1 * 48271 = (48271 + 510) % 20183 = 8415 % 3 = 0 rocky
1,1's risk level and type:
Meets catch-all rule 5
8415 * 17317 = (145722555 + 510) % 20183 = 1805 % 3 = 2 narrow
10,10's risk level and type:
Meets rule 2
(0 + 510) % 20183 = 510 % 3 = 0 rocky
Creating the smallest rectangular area as a data structure
Here's the example input again:
depth: 510
target: 10,10
The smallest rectangle is 10 x 10
.
I'll use X x Y
instead:
Create an array of length Y
Where each item is an array of length X
Calculating each cell's erosion and risk levels
For each row in rectangle
For each col in row
Use the coordinate col,row to match one of the five rules
Calculate each level accordingly
Store each attribute in an ordered 2-item list as the value of the current cell
Once all cell's contain an erosion and risk level, I can use reduce()
to sum up each risk level
.
Let's see if I can write this algorithm to generate the correct answer for the example input.
Off I go!...
...and I'm back.
I did it!!
Highlights of my working algorithm
- A regular expression
/\d+/g
to extract the three digits - Two loops to iterate through each cell in the rectangular area
- Five conditions for each rule
- A 2-item array stored in each cell
- Two
reduce()
methods to calculate the sum of each row's column's risk levels, then the sum of each row's summed risk levels
I quiver in fear at how complicated Part 2 will be, given:
- How relatively easy Part 1 was
- ...much like Day 23...
- and most Day 20+ Part 2s tend to be
- Oh, and the title of today has
Maze
in it...so, pathfinding is bound to be part of it!
Part 2
- Yup. Pretty complicated.
Yup. Pretty complicated.
- I was right. The name of the puzzle was a hint: Maze? Pathfinding involved.
- This is another
shortest path
challenge - But with twisted move rules like swapping tools
If I spent a ton of time, I might be able to manually find one path from 0,0
to target
.
It most certainly wouldn't be the shortest.
So, I must throw in the towel on another Part 2 before trying.
Celebrating my accomplishments
- I solved Part 1!
- I leveraged my skills with regular expressions, array creation, and
reduce()
Bummers:
- I didn't solve Part 2, let alone attempt it
- I felt prohibited to attempt another challenge due to my lack of practice with pathfinding algorithms
- I didn't make any GIFs - the instructional text offered all the algorithmic knowledge
- I didn't make a simulator - it would have been really fun to visualize an algorithm finding each path!
Brief stats and attitude check:
- 4 days in
- 3/8 stars
- I don't like that ratio
- But I am still proud that I have any stars at all, given I started with what are often the toughest puzzles of the year
Top comments (0)