Solution for Advent of Code 2018 - Day 15: Beverage Bandits

Link to the puzzle text

Part 1

In this puzzle we are given a grid of units and have to simulate a battle. There are two types: elves and goblins. Each round, they act according to a ruleset on how to find a enemy and how to attack. We are asked to simulate the battle round by round until only one team remains.

We store the position of each unit as a complex number as usual in addition to their current hit points. The units act according to their position in the grid, so we first sort them. To find the nearest enemy unit, we used a breadth-first search and move one cell on this path. For attacking we again have to sort the enemies by their hit points first and their position next. For the calculation of the final points, we also have to track if all units have acted in a round or we ended early.

While the search is a bit inefficient, it was still fast enough so no A* was needed. 

Part 2

In part 2, we have to vary the attack power of the elves until they win without losing a single unit.

We start by moving the attack power from a static value to a variable. We then simulate multiple battles with an increasing attack power. After the battle, we count the number of elves remaining. If they are the same as before the battle, no unit was lost and we can return the solution.

Link to my solutions