Robert Mion

Posted on

# Beverage Bandits

## 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:

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.

### 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 was very accessible and informative
• This 4-part article 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 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.