Sean McLemon | Advent of Code

Home | Czech | Blog | GitHub | Advent Of Code | Notes


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