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
 Another round of combat
 Understanding the
rounds
 Major blocker: pathfinding
 Recounting all the puzzles that thwarted me
 What am I to do?
 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:
 Target an enemy, if any exist
 Move toward that enemy, if possible, or don't if already next to one
 Attack that enemy
In each microstep of a unit's turn, Reading order
is of utmost importance: Zpattern  start topleft
, move right, continuing until the bottomright
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
orReachable
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
 2021 Day 15: Chiton
 2021 Day 12: Passage Pathing
 2019 Day 20: Donut Maze
 2019 Day 18: ManyWorlds Interpretation
 2018 Day 22: Mode Maze
 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 wellversed 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 4part 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 shortestpath 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.
Top comments (0)