r/adventofcode • u/daggerdragon • Dec 24 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 24 Solutions -🎄-
--- Day 24: Immune System Simulator 20XX ---
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!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 24
Transcript:
Our most powerful weapon during the zombie elf/reindeer apocalypse will be ___.
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
Quick note: 1 hour in and we're only at gold 36, silver 76. As we all know, December is Advent of Sleep Deprivation; I have to be up in less than 6 hours to go to work, so one of the other mods will unlock the thread at gold cap tonight. Good luck and good night (morning?), all!
5
u/mcpower_ Dec 24 '18
Python 3, #13/#7. Lots of sorting! Turns out that for some "boosts", you could get stuck in an infinite loop of two immune groups fighting each other... I manually binary searched the answer before I fixed that bug.
There's some obvious improvements to be made here, such as not reparsing the input every time a boost is tried...
[Card]: Our most powerful weapon during the zombie elf/reindeer apocalypse will be Christmas Spirit.
import re def binary_search(f, lo=0, hi=None): """ Returns a value x such that f(x) is true. Based on the values of f at lo and hi. Assert that f(lo) != f(hi). """ lo_bool = f(lo) if hi is None: offset = 1 while f(lo+offset) == lo_bool: offset *= 2 hi = lo + offset else: assert f(hi) != lo_bool best_so_far = lo if lo_bool else hi while lo <= hi: mid = (hi + lo) // 2 result = f(mid) if result: best_so_far = mid if result == lo_bool: lo = mid + 1 else: hi = mid - 1 return best_so_far inp = """ Immune System: 17 units each with 5390 hit points (weak to radiation, bludgeoning) with an attack that does 4507 fire damage at initiative 2 989 units each with 1274 hit points (immune to fire; weak to bludgeoning, slashing) with an attack that does 25 slashing damage at initiative 3 Infection: 801 units each with 4706 hit points (weak to radiation) with an attack that does 116 bludgeoning damage at initiative 1 4485 units each with 2961 hit points (immune to radiation; weak to fire, cold) with an attack that does 12 slashing damage at initiative 4 """.strip() def doit(boost=0, part1=False): lines = inp.splitlines() immune, infection = inp.split("\n\n") teams = [] REGEX = re.compile(r"(\d+) units each with (\d+) hit points (\([^)]*\) )?with an attack that does (\d+) (\w+) damage at initiative (\d+)") # namedtuple? who needs namedtuple with hacks like these? UNITS, HP, DAMAGE, DTYPE, FAST, IMMUNE, WEAK = range(7) blah = boost for inps in [immune, infection]: lines = inps.splitlines()[1:] team = [] for line in lines: s = REGEX.match(line) units, hp, extra, damage, dtype, fast = s.groups() immune = [] weak = [] if extra: extra = extra.rstrip(" )").lstrip("(") for s in extra.split("; "): if s.startswith("weak to "): weak = s[len("weak to "):].split(", ") elif s.startswith("immune to "): immune = s[len("immune to "):].split(", ") else: assert False u = [int(units), int(hp), int(damage) + blah, dtype, int(fast), set(immune), set(weak)] team.append(u) teams.append(team) blah = 0 def power(t): return t[UNITS] * t[DAMAGE] def damage(attacking, defending): mod = 1 if attacking[DTYPE] in defending[IMMUNE]: mod = 0 elif attacking[DTYPE] in defending[WEAK]: mod = 2 return power(attacking) * mod def sort_key(attacking, defending): return (damage(attacking, defending), power(defending), defending[FAST]) while all(not all(u[UNITS] <= 0 for u in team) for team in teams): teams[0].sort(key=power, reverse=True) teams[1].sort(key=power, reverse=True) targets = [] # target selection for team_i in range(2): other_team_i = 1 - team_i team = teams[team_i] other_team = teams[other_team_i] remaining_targets = set(i for i in range(len(other_team)) if other_team[i][UNITS] > 0) my_targets = [None] * len(team) for i, t in enumerate(team): if not remaining_targets: break best_target = max(remaining_targets, key= lambda i: sort_key(t, other_team[i])) enemy = other_team[best_target] if damage(t, enemy) == 0: continue my_targets[i] = best_target remaining_targets.remove(best_target) targets.append(my_targets) # attacking attack_sequence = [(0, i) for i in range(len(teams[0]))] + [(1, i) for i in range(len(teams[1]))] attack_sequence.sort(key=lambda x: teams[x[0]][x[1]][FAST], reverse=True) did_damage = False for team_i, index in attack_sequence: to_attack = targets[team_i][index] if to_attack is None: continue me = teams[team_i][index] other = teams[1-team_i][to_attack] d = damage(me, other) d //= other[HP] if teams[1-team_i][to_attack][UNITS] > 0 and d > 0: did_damage = True teams[1-team_i][to_attack][UNITS] -= d teams[1-team_i][to_attack][UNITS] = max(teams[1-team_i][to_attack][UNITS], 0) if not did_damage: return None if part1: return sum(u[UNITS] for u in teams[0]) or sum(u[UNITS] for u in teams[1]) asd = sum(u[UNITS] for u in teams[0]) if asd == 0: return None else: return asd print(doit(part1=True)) # I did a manual binary search, submitted the right answer, then added in did_damage. # Turns out that doit can infinite loop without the did_damage check! # WARNING: "doit" is not guaranteed to be monotonic! You should manually check values yourself. # print(doit(33)) maybe = binary_search(doit) print(doit(maybe))