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

1. Working backwards to understand and calculate risk level
2. Creating the smallest rectangular area as a data structure
3. Calculating each cell's erosion and risk levels
4. 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

1. 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