2018-12-15 - Beverage Bandits
(original .ipynb)
real_input = [
"################################",
"#######################.########",
"######################....######",
"#######################.....####",
"##################..##......####",
"###################.##.....#####",
"###################.....G..#####",
"##################.....G...#####",
"############.....GG.G...#..#####",
"##############...##....##.######",
"############...#..G............#",
"###########......E.............#",
"###########...#####..E........##",
"#...#######..#######.......#####",
"#..#..G....G#########.........##",
"#..#....G...#########..#....####",
"##.....G....#########.E......###",
"#####G.....G#########..E.....###",
"#####.......#########....#.....#",
"#####G#G....G#######.......#..E#",
"###.....G.....#####....#.#######",
"###......G.....G.G.......#######",
"###..................#..########",
"#####...................########",
"#####..............#...#########",
"####......G........#.E.#E..#####",
"####.###.........E...#E...######",
"####..##........#...##.....#####",
"########.#......######.....#####",
"########...E....#######....#####",
"#########...##..########...#####",
"################################"
]
from advent import grid_animated_combine, grid_animated_render_frame, grid_to_file, grid_reveal_tiles, neighbours4
import math
# part 1
# simulate the combat between a bunch of elves and goblins
# why can't we all just get along
def is_elf(col):
return col[0] == "E"
def is_goblin(col):
return col[0] == "G"
def is_open(col):
return col[0] == "."
def printable(col):
return col[0]
def reading_order_key(unit_positions):
def order(unit):
row, col = unit_positions[unit]
return float(f"{row}.{col:03d}")
return order
def reading_order(positions):
def order(position):
row, col = position
return float(f"{row}.{col:03d}")
return sorted(positions, key=order)
def identify_units(raw_grid):
identifier = 0
positions = {}
grid = []
for r, row in enumerate(raw_grid):
new_row = []
for c, col in enumerate(row):
if is_elf(col) or is_goblin(col):
col = col + str(identifier)
positions[col] = (r, c)
identifier += 1
new_row.append(col)
grid.append(new_row)
return (grid, positions)
def get_neighbours(origin, grid):
r, c = origin
return list(neighbours4(grid, r, c))
def get_movement_grid(origin, grid):
move_grid = []
for row in grid:
new_row = []
for col in row:
new_row.append(None)
move_grid.append(new_row)
steps = 1
queue = get_neighbours(origin, grid)
while any(queue):
next_queue = []
for r,c in queue:
if is_open(grid[r][c]) and move_grid[r][c] == None:
move_grid[r][c] = steps
next_queue += get_neighbours((r,c), grid)
queue = next_queue
steps += 1
return move_grid
# ctrl+c/ctrl+v because lazy
def flatten(t):
return [item for sublist in t for item in sublist]
def acquire_move_target(unit, positions, grid):
is_enemy = is_goblin if is_elf(unit) else is_elf
# if we're already next to an enemy, stay put
next_to_enemy = any(
1 for r,c
in get_neighbours(positions[unit], grid)
if is_enemy(grid[r][c])
)
if next_to_enemy:
return positions[unit]
# find the distances from our unit to everywhere it can reach
move_grid = get_movement_grid(positions[unit], grid)
# locate all enemies
all_enemies = list(u for u in positions.keys() if is_enemy(u))
if not any(all_enemies):
return None
# find the neighbouring tiles to each enemy
move_candidates = [
(r,c)
for r,c in flatten(get_neighbours(positions[u], grid) for u in all_enemies)
if is_open(grid[r][c]) and move_grid[r][c] != None
]
if not any(move_candidates):
return positions[unit]
# find the nearest reachable tiles
shortest_path = math.inf
targets = []
for r,c in move_candidates:
if move_grid[r][c] < shortest_path:
targets = [(r,c)]
shortest_path = move_grid[r][c]
elif move_grid[r][c] == shortest_path:
targets.append((r,c))
# if there are no targets, bail
if not any(targets):
return None
# the target tile is the first in reading order
target = reading_order(targets)[0]
# (r,c) is our target, we will use the move-grid to
# track back from there to find our next step
candidates = []
next_moves = [target]
while any(next_moves):
cr,cc = next_moves.pop(0)
distance = move_grid[cr][cc]
if distance == 1:
candidates.append((cr,cc))
else:
next_moves += [
(nr, nc)
for nr,nc
in get_neighbours((cr,cc), move_grid)
if move_grid[nr][nc] == distance - 1 and not ((nr,nc) in next_moves)
]
return reading_order(candidates)[0]
def move(unit, new_location, positions, grid):
old_location = positions[unit]
# we're not moving
if new_location == old_location:
return
new_r, new_c = new_location
old_r, old_c = old_location
move_x = abs(new_r - old_r) == 1
move_y = abs(new_c - old_c) == 1
# set the old position to open and move
grid[old_r][old_c] = "."
grid[new_r][new_c] = unit
positions[unit] = (new_r, new_c)
def initialize_hit_points(units):
hit_points = {}
for unit in units:
hit_points[unit] = 200
return hit_points
def attack(unit, hit_points, positions, grid, power):
is_enemy = is_goblin if is_elf(unit) else is_elf
origin = positions[unit]
enemy_positions = {
grid[r][c]:(r,c) for r,c
in get_neighbours(origin, grid)
if is_enemy(grid[r][c])
}
if not any(enemy_positions):
return
min_hp = math.inf
targets = {}
for enemy in enemy_positions:
if hit_points[enemy] < min_hp:
targets = {enemy:enemy_positions[enemy]}
min_hp = hit_points[enemy]
elif hit_points[enemy] == min_hp:
targets[enemy] = enemy_positions[enemy]
min_hp = hit_points[enemy]
enemies_ordered = sorted(targets.keys(), key=reading_order_key(targets))
enemy = enemies_ordered[0]
hit_points[enemy] -= power
if hit_points[enemy] <= 0:
r, c = positions[enemy]
grid[r][c] = "."
del positions[enemy]
del hit_points[enemy]
def get_attack_power(unit, elf_attack_pwr):
if is_elf(unit):
return elf_attack_pwr
return 3
def count_elves(positions):
return len(list(u for u in positions.keys() if is_elf(u)))
def solve(input_grid, fail_on_elf_death=False, elf_attack_pwr=3, render_to_file=None):
grid, positions = identify_units(input_grid)
hit_points = initialize_hit_points(positions.keys())
rounds = 0
initial_elf_count = count_elves(positions)
render_frames = []
while True:
ordered_units = sorted(positions.keys(), key=reading_order_key(positions))
for unit in ordered_units:
if not (unit in positions):
continue
target = acquire_move_target(unit, positions, grid)
if target == None:
if render_to_file:
grid_animated_combine(render_frames, render_to_file, show=True)
return rounds * sum(hit_points[u] for u in positions.keys())
move(unit, target, positions, grid)
power = get_attack_power(unit, elf_attack_pwr)
attack(unit, hit_points, positions, grid, power)
if fail_on_elf_death and initial_elf_count != count_elves(positions):
return -1
if render_to_file:
f = []
for row in grid:
new_row = []
for col in row:
new_row.append(printable(col))
f.append(new_row)
render_frames.append(grid_animated_render_frame(f, palette))
rounds += 1
############################
# test area
test0 = [
'#######',
'#.G...#',
'#...EG#',
'#.#.#G#',
'#..G#E#',
'#.....#',
'#######'
]
test1 = [
"#######",
"#G..#E#",
"#E#E.E#",
"#G.##.#",
"#...#E#",
"#...E.#",
"#######"
]
test2 = [
"#######",
"#E..EG#",
"#.#G.E#",
"#E.##E#",
"#G..#.#",
"#..E#.#",
"#######"
]
test3 = [
"#######",
"#E.G#.#",
"#.#G..#",
"#G.#.G#",
"#G..#.#",
"#...E.#",
"#######"
]
test4 = [
"#######",
"#.E...#",
"#.#..G#",
"#.###.#",
"#E#G#G#",
"#...#G#",
"#######"
]
test5 = [
"#########",
"#G......#",
"#.E.#...#",
"#..##..G#",
"#...##..#",
"#...#...#",
"#.G...G.#",
"#.....G.#",
"#########"
]
assert 27730 == solve(test0)
assert 36334 == solve(test1)
assert 39514 == solve(test2)
assert 27755 == solve(test3)
assert 28944 == solve(test4)
assert 18740 == solve(test5)
print(solve(real_input))
181952
# part 2
# find the minimum attack power where the elves don't lose a single guy
def solve2(input_grid):
elf_power = 3
solution = solve(input_grid, True, elf_power)
while solution < 0:
elf_power += 1
solution = solve(input_grid, True, elf_power)
return solution
assert 4988 == solve2(test0)
#assert ??? == solve2(test1)
assert 31284 == solve2(test2)
assert 3478 == solve2(test3)
assert 6474 == solve2(test4)
assert 1140 == solve2(test5)
print(solve2(real_input))
47296
palette = {
".": "white",
"#": "brown",
"G": "red",
"E": "blue"
}
solve(real_input, False, 3, "day-15-part1.gif")
181952
solve(real_input, True, 25, "day-15-part2.gif")
47296