DEV Community

Robert Mion
Robert Mion

Posted on

Beverage Bandits

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
Enter fullscreen mode Exit fullscreen mode

Example input

#########
#G..G..G#
#.......#
#.......#
#G..E..G#
#.......#
#.......#
#G..G..G#
#########
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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#   
#######       #######       #######   
Enter fullscreen mode Exit fullscreen mode
  • 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#  
#######       #######       #######       #######  
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (0)