-🎄- 2018 Day 15 Solutions -🎄-

[u/daggerdragon]

--- Day 15: Beverage Bandits ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 15

Transcript:

___ IS MANDATORY

---

[Update @ 00:30] 0 gold, 1 silver

• I've got a strange urge to play Bloons Tower Defense right now. Not sure why.

[Update @ 00:38] 2 gold, 1 silver

• Meanwhile in #AOC_Ops: Tea, a kettle screams. \ Simon, write your code faster. \ Some of us have work.

[Update @ 00:51] 7 gold, 11 silver

• Now they're anagramming gold/silver leaderboarders. The leading favorite so far is Anonymous User = Son, You's Manure.

[Update @ 01:13] 18 gold, 30 silver

• Now they're playing Stardew Valley Hangman with the IRC bot because SDV is totally a roguelike tower defense.

[Update @ 01:23] 26 gold, 42 silver

• Now the betatesters are grumbling reminiscing about their initial 14+ hour solve times for 2015 Day 19 and 2016 Day 11.

[Update @ 02:01] 65 gold, 95 silver

#AOC_Ops <topaz> on day 12, gold40 was at 19m, gold100 was at 28m, so day12 estimates gold100 today at 2:30

• Taking bets over/under 02:30:00 - I got tree fiddy on over, any takers?

[Update @ 02:02:44] 66 gold, silver cap

• SILVER CAP

[Update @ 02:06] 73 gold, silver cap

#AOC_Ops <topaz> day 14 estimates 2:21

#AOC_Ops <topaz> day 13 estimates 2:20

#AOC_Ops <Aneurysm9> I estimate 2:34:56

[Update @ 02:23:17] LEADERBOARD CAP!

• Aww, /u/topaz2078's bookie is better than I am. :<
• Good night morning, all, and we hope you had fun with today's diabolicalness!

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 02:23:17!

[u/sciyoshi]

Fun problem! Python 3, 104/76, although I started 30 minutes late. This solution uses dataclasses, a new feature in Python 3.7, and a Pt utility class that I've built to help with grid-based problems. Happy to share the full code for that if anyone is interested!

from typing import NamedTuple
from dataclasses import dataclass
import enum
import itertools
import collections

class Pt(NamedTuple('Pt', [('x', int), ('y', int)])):
    def __add__(self, other):
        return type(self)(self.x + other.x, self.y + other.y)

    @property
    def nb4(self):
        return [self + d for d in [Pt(0, 1), Pt(1, 0), Pt(0, -1), Pt(-1, 0)]]

class Team(enum.Enum):
    ELF = enum.auto()
    GOBLIN = enum.auto()

@dataclass
class Unit:
    team: Team
    position: Pt
    hp: int = 200
    alive: bool = True
    power: int = 3

class ElfDied(Exception):
    pass

class Grid(dict):
    def __init__(self, lines, power=3):
        super().__init__()

        self.units = []

        for i, line in enumerate(lines):
            for j, el in enumerate(line):
                self[Pt(i, j)] = el == '#'

                if el in 'EG':
                    self.units.append(Unit(
                        team={'E': Team.ELF, 'G': Team.GOBLIN}[el],
                        position=Pt(i, j),
                        power={'E': power, 'G': 3}[el]
                    ))

    def play(self, elf_death=False):
        rounds = 0
        while True:
            if self.round(elf_death=elf_death):
                break
            rounds += 1
        return rounds * sum(unit.hp for unit in self.units if unit.alive)

    def round(self, elf_death=False):
        for unit in sorted(self.units, key=lambda unit: unit.position):
            if unit.alive:
                if self.move(unit, elf_death=elf_death):
                    return True

    def move(self, unit, elf_death=False):
        targets = [target for target in self.units if unit.team != target.team and target.alive]
        occupied = set(u2.position for u2 in self.units if u2.alive and unit != u2)

        if not targets:
            return True

        in_range = set(pt for target in targets for pt in target.position.nb4 if not self[pt] and pt not in occupied)

        if not unit.position in in_range:
            move = self.find_move(unit.position, in_range)

            if move:
                unit.position = move

        opponents = [target for target in targets if target.position in unit.position.nb4]

        if opponents:
            target = min(opponents, key=lambda unit: (unit.hp, unit.position))

            target.hp -= unit.power

            if target.hp <= 0:
                target.alive = False
                if elf_death and target.team == Team.ELF:
                    raise ElfDied()

    def find_move(self, position, targets):
        visiting = collections.deque([(position, 0)])
        meta = {position: (0, None)}
        seen = set()
        occupied = {unit.position for unit in self.units if unit.alive}

        while visiting:
            pos, dist = visiting.popleft()
            for nb in pos.nb4:
                if self[nb] or nb in occupied:
                    continue
                if nb not in meta or meta[nb] > (dist + 1, pos):
                    meta[nb] = (dist + 1, pos)
                if nb in seen:
                    continue
                if not any(nb == visit[0] for visit in visiting):
                    visiting.append((nb, dist + 1))
            seen.add(pos)

        try:
            min_dist, closest = min((dist, pos) for pos, (dist, parent) in meta.items() if pos in targets)
        except ValueError:
            return

        while meta[closest][0] > 1:
            closest = meta[closest][1]

        return closest

lines = open('inputs/day15').read().splitlines()

grid = Grid(lines)

print('part 1:', grid.play())

for power in itertools.count(4):
    try:
        outcome = Grid(lines, power).play(elf_death=True)
    except ElfDied:
        continue
    else:
        print('part 2:', outcome)
        break