Advent of Code 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
2. 2018 Day 24: Immune System Simulator 20XX
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
2. 2021 Day 12: Passage Pathing
3. 2019 Day 20: Donut Maze
4. 2019 Day 18: Many-Worlds Interpretation
5. 2018 Day 22: Mode Maze
6. 2018 Day 20: A Regular Map

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.