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 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
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: Many-Worlds 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 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.
Top comments (0)