We are asked to play out a battle between elves and goblins. The biggest challenge is figuring out how to move; once next to an enemy stepping through the actions should be simple.
We've last seen a similar problem (finding the best options in a simulated battle) in AoC 2015, day 22, and I'll again use the A* search algorithm to find the paths, picking the shortest path (sorting equal lengths by the 'reading' order, (y, x) tuple sorting, of the first step). Once a shortest path to a target is found, we can stop the search and execute a move.
So the trick here is to see a short path that started off to the left then down as separate from a node that steps down then left. In most A* implementations you'd see this as the same node in the graph (position the same, distance the same, same heuristic score to any target goals). So here, we attach the first step of a potential path to the A* nodes so that it is used in equality testing and hashing, and include the first positon in the priority for the priority queue to prefer paths whose first step come first in reading order over others when they otherwise have the same cost.
from dataclasses import dataclass, field
from enum import Enum
from heapq import heappop, heappush
from itertools import count
from operator import attrgetter
from typing import Iterable, Iterator, Mapping, Optional, Sequence, Set, Tuple
Position = Tuple[int, int] # y, x order
class NoTargetsRemaining(Exception):
"""No more targets to attack"""
class NoTargetsReachable(Exception):
"""No path found that reaches a target"""
class ElfDied(Exception):
"""We lost, because an elf died"""
class Race(Enum):
elf = "E"
goblin = "G"
@dataclass(order=True)
class Unit:
race: Race = field(compare=False)
y: int
x: int
hitpoints: int = field(default=200, compare=False)
attackpower: int = field(default=3, compare=False)
@property
def pos(self) -> Position:
return self.y, self.x
def adjacent(self, cave: "CaveCombat") -> Set[Position]:
"""All cave positions adjacent to the current position"""
positions = (
(self.y + dy, self.x + dx) for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0))
)
return {(y, x) for y, x in positions if cave.map[y][x] == "."}
def available(self, cave: "CaveCombat") -> Set[Position]:
"""All positions this unit could move to"""
return {pos for pos in self.adjacent(cave) if cave[pos] is None}
def turn(self, cave: "CaveCombat") -> None:
# find targets to go after
targets = [u for u in cave.units if u.race is not self.race]
if not targets:
# end combat
raise NoTargetsRemaining
# determine if we need to move
adjacent = self.adjacent(cave)
in_range = [
u for pos in adjacent for u in (cave[pos],) if u and u.race is not self.race
]
# we need to move, make a move if possible
if not in_range:
# find a target to move to
target_positions = set().union(*(t.available(cave) for t in targets))
if not target_positions:
# no positions to move to, turn ends
return
# pick a shortest path to one of the positions, returns our new position
try:
self.y, self.x = cave.search_path(self.pos, target_positions)
except NoTargetsReachable:
pass
# check for in-range targets once more now that we have moved
adjacent = self.adjacent(cave)
in_range = [
u
for pos in adjacent
for u in (cave[pos],)
if u and u.race is not self.race
]
# attack if in range of a target
if in_range:
# pick target with lowest hitpoints; ties broken by reading order
target = min(in_range, key=attrgetter("hitpoints", "y", "x"))
target.hitpoints -= self.attackpower
if target.hitpoints <= 0:
# target died, remove them from the cave
cave.units.remove(target)
if cave.no_elf_dies and target.race is Race.elf:
raise ElfDied
return
_sentinel_first_pos: Position = (-1, -1)
@dataclass(frozen=True, order=True)
class Node:
"""Node on the A* search graph"""
y: int
x: int
distance: int = 0
# position of first actual transition node. Needed to distinguish
# between multiple possible paths to the same goal, and this is
# used to set the new unit position once a path has been picked.
first_pos: Position = _sentinel_first_pos
@property
def pos(self) -> Position:
return self.y, self.x
def cost(self, goals: Set[Position]) -> int:
"""Calculate the cost for this node, f(n) = g(n) + h(n)
The cost of this node is the distance travelled (g) plus
estimated cost to get to nearest goal (h).
Here we use the manhattan distance to the nearest goal as
the estimated cost.
"""
distances = (abs(y - self.y) + abs(x - self.x) for y, x in goals)
return self.distance + min(distances)
def transitions(self, cave: "CaveCombat") -> Iterator["Node"]:
cls = type(self)
positions = (
(self.y + dy, self.x + dx) for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0))
)
return (
cls(
y,
x,
self.distance + 1,
(y, x) if self.first_pos == _sentinel_first_pos else self.first_pos,
)
for y, x in positions
if cave.map[y][x] == "." and cave[(y, x)] is None
)
@dataclass
class CaveCombat:
map: Sequence[str]
units: Sequence[Unit]
round: int = 0
no_elf_dies: bool = False
def __post_init__(self):
# internal cache of unit positions, updated before each unit turn
self._unit_positions: Mapping = {}
@classmethod
def from_lines(cls, lines: Iterable[str], elf_attackpower: int = 3) -> "CaveCombat":
map = []
units = []
unit_chars = "".join(r.value for r in Race)
for y, line in enumerate(lines):
cleaned = []
for x, c in enumerate(line):
if c in unit_chars:
attackpower = elf_attackpower if c == "E" else 3
units.append(Unit(Race(c), y, x, attackpower=attackpower))
c = "."
cleaned.append(c)
map.append("".join(cleaned))
return cls(map, units)
def __str__(self) -> str:
map = [list(line) for line in self.map]
for unit in self.units:
map[unit.y][unit.x] = unit.race.value
return "\n".join(["".join(line) for line in map])
def __getitem__(self, yx: Position) -> Optional[Unit]:
if self._unit_positions:
return self._unit_positions.get(yx)
return next((u for u in self.units if u.pos == yx), None)
def do_battle(self) -> int:
while True:
result = self.turn()
if result is not None:
return result
def turn(self) -> Optional[int]:
for unit in sorted(self.units):
# skip units that are dead; these are still in the sorted
# loop iterable but have been removed from self.units
if unit.hitpoints <= 0:
continue
# cache unit positions once per round
self._unit_positions = {u.pos: u for u in self.units}
try:
unit.turn(self)
except NoTargetsRemaining:
return self.round * sum(u.hitpoints for u in self.units)
self.round += 1
return None
def search_path(self, start: Position, goals: Set[Position]) -> Position:
start_node = Node(*start)
open = {start_node}
unique = count() # tie breaker when costs are equal
pqueue = [
(start_node.cost(goals), start_node.first_pos, next(unique), start_node)
]
closed = set()
distances = {
start_node.pos: 0
} # pos -> distance. Ignore nodes that are longer.
while open:
node = heappop(pqueue)[-1]
if node.pos in goals:
return node.first_pos
open.remove(node)
closed.add(node)
for new in node.transitions(self):
if new in closed or new in open:
continue
if distances.get(new.pos, float("inf")) < new.distance:
# already reached this point with a shorter path
continue
open.add(new)
distances[new.pos] = new.distance
heappush(pqueue, (new.cost(goals), new.first_pos, next(unique), new))
raise NoTargetsReachable
movetest = CaveCombat.from_lines(
"""\
#########
#G..G..G#
#.......#
#.......#
#G..E..G#
#.......#
#.......#
#G..G..G#
#########""".splitlines()
)
outputs = (
"#########\n#G..G..G#\n#.......#\n#.......#\n#G..E..G#\n#.......#\n#.......#\n#G..G..G#\n#########",
"#########\n#.G...G.#\n#...G...#\n#...E..G#\n#.G.....#\n#.......#\n#G..G..G#\n#.......#\n#########",
"#########\n#..G.G..#\n#...G...#\n#.G.E.G.#\n#.......#\n#G..G..G#\n#.......#\n#.......#\n#########",
"#########\n#.......#\n#..GGG..#\n#..GEG..#\n#G..G...#\n#......G#\n#.......#\n#.......#\n#########",
)
for expected in outputs:
assert str(movetest) == expected
movetest.turn()
combattest = CaveCombat.from_lines(
"""\
#######
#.G...#
#...EG#
#.#.#G#
#..G#E#
#.....#
#######""".splitlines()
)
rounds = (
(
0,
"#######\n#.G...#\n#...EG#\n#.#.#G#\n#..G#E#\n#.....#\n#######",
("G", 200),
("E", 200),
("G", 200),
("G", 200),
("G", 200),
("E", 200),
),
(
1,
"#######\n#..G..#\n#...EG#\n#.#G#G#\n#...#E#\n#.....#\n#######",
("G", 200),
("E", 197),
("G", 197),
("G", 200),
("G", 197),
("E", 197),
),
(
2,
"#######\n#...G.#\n#..GEG#\n#.#.#G#\n#...#E#\n#.....#\n#######",
("G", 200),
("G", 200),
("E", 188),
("G", 194),
("G", 194),
("E", 194),
),
(
23,
"#######\n#...G.#\n#..G.G#\n#.#.#G#\n#...#E#\n#.....#\n#######",
("G", 200),
("G", 200),
("G", 131),
("G", 131),
("E", 131),
),
(
24,
"#######\n#..G..#\n#...G.#\n#.#G#G#\n#...#E#\n#.....#\n#######",
("G", 200),
("G", 131),
("G", 200),
("G", 128),
("E", 128),
),
(
25,
"#######\n#.G...#\n#..G..#\n#.#.#G#\n#..G#E#\n#.....#\n#######",
("G", 200),
("G", 131),
("G", 125),
("G", 200),
("E", 125),
),
(
26,
"#######\n#G....#\n#.G...#\n#.#.#G#\n#...#E#\n#..G..#\n#######",
("G", 200),
("G", 131),
("G", 122),
("E", 122),
("G", 200),
),
(
27,
"#######\n#G....#\n#.G...#\n#.#.#G#\n#...#E#\n#...G.#\n#######",
("G", 200),
("G", 131),
("G", 119),
("E", 119),
("G", 200),
),
(
28,
"#######\n#G....#\n#.G...#\n#.#.#G#\n#...#E#\n#....G#\n#######",
("G", 200),
("G", 131),
("G", 116),
("E", 113),
("G", 200),
),
(
47,
"#######\n#G....#\n#.G...#\n#.#.#G#\n#...#.#\n#....G#\n#######",
("G", 200),
("G", 131),
("G", 59),
("G", 200),
),
)
for round, expected, *units in rounds:
while combattest.round != round:
combattest.turn()
assert str(combattest) == expected
assert [(u.race.value, u.hitpoints) for u in sorted(combattest.units)] == units
assert combattest.turn() == 27730
tests = (
(
"#######\n#G..#E#\n#E#E.E#\n#G.##.#\n#...#E#\n#...E.#\n#######",
"#######\n#...#E#\n#E#...#\n#.E##.#\n#E..#E#\n#.....#\n#######",
36334,
),
(
"#######\n#E..EG#\n#.#G.E#\n#E.##E#\n#G..#.#\n#..E#.#\n#######",
"#######\n#.E.E.#\n#.#E..#\n#E.##.#\n#.E.#.#\n#...#.#\n#######",
39514,
),
(
"#######\n#E.G#.#\n#.#G..#\n#G.#.G#\n#G..#.#\n#...E.#\n#######",
"#######\n#G.G#.#\n#.#G..#\n#..#..#\n#...#G#\n#...G.#\n#######",
27755,
),
(
"#######\n#.E...#\n#.#..G#\n#.###.#\n#E#G#G#\n#...#G#\n#######",
"#######\n#.....#\n#.#G..#\n#.###.#\n#.#.#.#\n#G.G#G#\n#######",
28944,
),
(
"#########\n#G......#\n#.E.#...#\n#..##..G#\n#...##..#\n#...#...#\n#.G...G.#\n#.....G.#\n#########",
"#########\n#.G.....#\n#G.G#...#\n#.G##...#\n#...##..#\n#.G.#...#\n#.......#\n#.......#\n#########",
18740,
),
)
for start, end, expected in tests:
testcave = CaveCombat.from_lines(start.splitlines())
assert testcave.do_battle() == expected
assert str(testcave) == end
import aocd
data = aocd.get_data(day=15, year=2018)
cave = CaveCombat.from_lines(data.splitlines())
print("Part 1:", cave.do_battle())
Part 1: 195811
Runnig a full battle is not that cheap, so incrementing the attack power one step at a time is going to take a long time.
So we need a faster method. We could use bisection here; we can figure out a lower and upper bound for Elf strength, then start in between those two points and see if the Elves can survive with that strength. If not, we have a new lower bound, if they can win, we have a new upper bound. Repeat with the new midpoint until we have the lowest viable attack strength. Bisection lets us home in on the ideal minimal attack strength in $O(\log_2 n)$ steps for $n$ strengths between the low bound (3 at least) and 200 (at most).
We could limit those bounds further, perhaps. The lower and upper bounds are determined by the goblin vs. elves mix, and how many elves can take on a goblin together vs. how many goblins might surround an elf to attack together, so we can probably do better than 3 and 200 here.
For example, in a scenario with just one elf in the cave and 5 goblins, the best case scenario is that the elf can take on the goblins one by one, while the worst case is that 4 goblins surround our elf right at the start and start hacking away. The elf then has to defeat 2 goblins before the numbers go down.
Put generically, with $\gamma$ goblins and $\epsilon$ elves:
The worst case involves the goblins all focusing on 1 elf. That single elf has to hack their way through a replentishing number of goblins; $\gamma$ goblins can sustain $\gamma - 3$ deaths before they can no longer surround a single elf. We can take this an an average attack strength; $avga = \frac{12\max(0, \gamma - 4) + 3(\frac{\min(4, \gamma)(\min(4, \gamma) + 1)}{2})}{\gamma}$. The single elf can survive $minr = \lfloor\frac{200}{avga}\rfloor$ rounds, so their attack strength needs to be adjusted to match that; $strength = min(200, \lceil\frac{200\gamma}{minr}\rceil)$; note that the maximum attack power is 200, there is no point in putting this higher, we must assume that we never have to deal with such a no-win setup.
The best case has elves ganging up on goblins 4 elves at a time, so the ganged-up goblins can only do 3 points of damage per round divided over up to 4 elves. Elves can gang up on $maxg = \lceil\frac{\epsilon}{4}\rceil$ goblins, which have to divide their strength over those $\epsilon$ elves (we'll assume we can rotate out weakened elves), giving an average gobling attack strength of $avga = \frac{3maxg}{\epsilon}$. This means the elves can last $minr = \lfloor\frac{200\epsilon}{avga}\rfloor$ rounds, and need an attack strength $strength = max(3, \lceil\frac{200\gamma}{minr}\rceil)$ (the minimum attack strength to win with must be 4, but we do need to test at 3 to find the lowest 'losing' point).
Once we have a lower and upper bound for attack strength, we can find the actual minimal strength with bisection.
For the example with $\epsilon = 1$ and $\gamma = 5$, the minimum is 16, maximum is 44. You run the scenario with a midpoint first, $\lfloor\frac{44 - 16}{2}\rfloor + 16 = 30$. This scenario fails, our single elf dies, so we know 30 to be a new lower bound. We next try with $\lfloor\frac{44 - 30}{2}\rfloor + 30 = 37$ (fails), then at 40 the elf succeeds, so we have a new upper bound and step to 38. Here the elf wins again, and since that's 1 step above our lower bound, we know that that's the right answer here.
In the end, for the actual puzzle input, the bounds are 3 and 200 anyway, so the above work was more complicated than actually needed. Oh well.
import math
def optimise_strength(cavelines: Iterable[str], verbose=False) -> int:
log = print if verbose else lambda *a, **k: None
elves = sum(line.count("E") for line in cavelines)
goblins = sum(line.count("G") for line in cavelines)
# worst case, highest strength required
avga = (
12 * max(0, goblins - 4) + 3 * (min(4, goblins) * (min(4, goblins) + 1)) // 2
) / goblins
high = min(200, math.ceil(200 * goblins / (200 // avga)))
# best case, lowest strength required
minr = math.ceil(200 * elves / ((3 * math.ceil(elves / 4)) / elves))
low = max(3, math.ceil((200 * goblins) / minr))
last_high_outcome = 0
log(f"Optimising, strength between {low} and {high}")
while low < high:
mid = (high - low) // 2 + low
log(f"\n - Trying strength {mid}")
cave = CaveCombat.from_lines(cavelines, mid)
cave.no_elf_dies = True
try:
outcome = cave.do_battle()
except ElfDied:
# not high enough
log(" - Too low, an elf died")
low = mid
else:
log(" - Elves victorious")
high = mid
last_high_outcome = outcome
# See if high is one step above low, that's our sweet spot
if high == low + 1:
return last_high_outcome
raise AssertionError("wrong low or high starting points")
optimise_tests = (
("#######\n#.G...#\n#...EG#\n#.#.#G#\n#..G#E#\n#.....#\n#######", 4988),
("#######\n#E..EG#\n#.#G.E#\n#E.##E#\n#G..#.#\n#..E#.#\n#######", 31284),
("#######\n#E.G#.#\n#.#G..#\n#G.#.G#\n#G..#.#\n#...E.#\n#######", 3478),
("#######\n#.E...#\n#.#..G#\n#.###.#\n#E#G#G#\n#...#G#\n#######", 6474),
(
"#########\n#G......#\n#.E.#...#\n#..##..G#\n#...##..#\n#...#...#\n#.G...G.#\n#.....G.#\n#########",
1140,
),
)
for lines, expected in optimise_tests:
assert optimise_strength(lines.splitlines()) == expected
print("Part 2:", optimise_strength(data.splitlines()))
Part 2: 69867
As I checked out the Advent of Code sub-Reddit discussions I found that there are scenarios where the elves win at $strength = n$ but lose at $strength = n + 1$, because it takes longer to kill a goblin at $strength = n$ and so a weak elf won't walk into the healthier goblin that would kill it at $strength = n + 1$. This means there is no strict ordering over the range of strengths (there is no single point where losing turns to winning), and we can't use bisection in that case.
So the correct solution is to iterate up from $strength = 4$. As an elf dying means the battle is cut short, this isn't all that bad. We can still complete this task in a few seconds.
def optimise_strength_corrected(cavelines: Iterable[str], verbose=False) -> int:
log = print if verbose else lambda *a, **k: None
for strength in range(4, 200):
log(f"\n- Trying strength {strength}")
cave = CaveCombat.from_lines(cavelines, strength)
cave.no_elf_dies = True
try:
outcome = cave.do_battle()
except ElfDied:
# not high enough
log(" - Too low, an elf died")
else:
log(" - Elves victorious")
return outcome
for lines, expected in optimise_tests:
assert optimise_strength_corrected(lines.splitlines()) == expected
print("Part 2:", optimise_strength_corrected(data.splitlines()))
Part 2: 69867