Mode Maze
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-06-04 00:48:41

## [Advent of Code 2018 Day 22](https://adventofcode.com/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