Beverage Bandits
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-06-16 01:17:23

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

## Task: Solve for X where...
### Part 1
```
X = the product of the number of full rounds that were completed and the sum of the hit points of all remaining units
```

## Example input
```
#########
#G..G..G#
#.......#
#.......#
#G..E..G#
#.......#
#.......#
#G..G..G#
#########
```

It represents:
- A scan of an area
- `#` are walls
- `.` are open caverns
- `G` are Goblins
- `E` are Elves

## Part 1
1. Another round of combat
2. Understanding the `rounds`
3. Major blocker: pathfinding
4. Recounting all the puzzles that thwarted me
5. What am I to do?
6. Learnings I discovered

### Another round of combat
This puzzle is the third instance among the `combat`-themed puzzles:
1. [2020 Day 22: Crab Combat](https://adventofcode.com/2020/day/22)
2. [2018 Day 24: Immune System Simulator 20XX](https://adventofcode.com/2018/day/24)
3. Today

All these puzzles featured rather complex expositions, largely to describe what happens during each `round` of `combat`.

Today's puzzle has the longest exposition for a Part 1.
- It's incredibly intimidating
- And also intriguing

Let's dive in!

### Understanding the `rounds`
Each round, each unit attempts to complete its turn:
1. Target an enemy, if any exist
2. Move toward that enemy, if possible, or don't if already next to one
3. Attack that enemy

In each micro-step of a unit's turn, `Reading order` is of utmost importance: Z-pattern - start `top-left`, move right, continuing until the `bottom-right`

In essence:
```
Start-->
------->
------->
---->End
```

### Major blocker: pathfinding
This diagram from the instructions revealed a major hurtle for me if I tried to solve this puzzle:
```
Targets:      In range:     Reachable:
#######       #######       #######   
#E..G.#       #E.?G?#       #E.@G.#   
#...#.#  -->  #.?.#?#  -->  #.@.#.#   
#.G.#G#       #?G?#G#       #@G@#G#   
#######       #######       #######   
```
- I foresee no difficulty identifying the targets
- However, I don't know how to write an algorithm that would identify targets `In range` or `Reachable`

Furthermore, the following instruction and diagram are hurdles:
> The unit then takes a single step toward the chosen square along the shortest path to that square

```
In range:     Nearest:      Chosen:       Distance:
#######       #######       #######       #######  
#.E...#       #.E...#       #.E...#       #4E212#  
#...?.#  -->  #...!.#  -->  #...+.#  -->  #32101#  
#..?G?#       #..!G.#       #...G.#       #432G2#  
#######       #######       #######       #######  
```

Sadly, I am once again prevented from attempting to solve a puzzle due to my inability to understand and write `shortest path`/`pathfinding` algorithms.

### Recounting all the puzzles that thwarted me
1. [2021 Day 15: Chiton](https://adventofcode.com/2021/day/15)
2. [2021 Day 12: Passage Pathing](https://adventofcode.com/2021/day/12)
3. [2019 Day 20: Donut Maze](https://adventofcode.com/2019/day/20)
4. [2019 Day 18: Many-Worlds Interpretation](https://adventofcode.com/2019/day/18)
5. [2018 Day 22: Mode Maze](https://adventofcode.com/2018/day/22)
6. [2018 Day 20: A Regular Map](https://adventofcode.com/2018/day/20)

### What am I to do?
- Use this as an opportunity to research, learn and practice writing pathfinding algorithms?
- That's what I did after being thwarted by a puzzle that required the use of a regular expression...and now I at least don't feel nearly as blocked by those when I encounter them in puzzles
- Or do I carry on, knowing that any further pathfinding puzzles I encounter will just get added to the list above?

I feel compelled to spend a day or two trying to become more well-versed in how Dijkstra's pathfinding algorithm works.

### Learnings I discovered
- [This visual guide to how Dijkstra's algorithm works](https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/) was very accessible and informative
- [This 4-part article](https://www.codingame.com/playgrounds/1608/shortest-paths-with-dijkstras-algorithm/introduction) further solidified each major step of the algorithm, and even gave me the opportunity to practice writing one of the steps!
- To understand any pathfinding algorithm, I really have to understand graphs as a data structure. Thankfully, [FreeCodeCamp.org has an entire section](https://www.freecodecamp.org/learn/coding-interview-prep/#data-structures) related to the topic that I'm excited to start completing 
- Lastly, it seems today's puzzle was rated by several reddit solver's as one of the toughest in the series. There was also one confusing phrase in the instructions that many misinterpreted. I'm a bit glad I couldn't even start this puzzle knowing now that - even if I had the skills - it would have taken me days to write an algorithm that probably wouldn't have generated the correct answer due to some small detail

## Celebrating my accomplishments
- I catalogued each of the `shortest path`-themed puzzles in this series that I can look forward to attempting one day when I have acquired the skills to solve them
- I bookmarked a few resources that helped me understand how Dijkstra's algorithm works, and that can help me understand some of the fundamental computer science concepts that I'll have to use when writing a shortest-path algorithm
- I avoided a huge obstacle and headache by being forced to not even attempt this puzzle

I'm hopeful that Days 14 and earlier will present puzzles that I am competent enough to attempt solving.