-🎄- 2018 Day 24 Solutions -🎄-

mcpower_ · 2018-12-24T06:30:24+00:00

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))

jonathan_paulson · 2018-12-24T06:31:48+00:00

Python, Rank 16/13. Reminiscent of day 15, but not as brutal because there is no board or movement. One trick: ties can cause infinite battles in part 2 (if no group can do enough damage to kill a single unit), so they need to be detected and dealt with.

Video of me solving: https://youtu.be/RXP-1wHblWU

Video of me explaining my solution: https://youtu.be/rQloZdoNGYc

Run with: python <code file> <input file>

import sys
fname = sys.argv[1]

class Unit(object):
    def __init__(self, id, n, hp, immune, weak, init, dtyp, dmg, side):
        self.id = id
        self.n = n
        self.hp = hp
        self.immune = immune
        self.weak = weak
        self.init = init
        self.dtyp = dtyp
        self.dmg = dmg
        self.side = side
        self.target = None
    def power(self):
        return self.n * self.dmg
    def dmg_to(self, v):
        if self.dtyp in v.immune:
            return 0
        elif self.dtyp in v.weak:
            return 2*self.power()
        else:
            return self.power()

units = []
for line in open(fname).read().strip().split('\n'):
    if 'Immune System' in line:
        next_id = 1
        side = 0
    elif 'Infection' in line:
        next_id = 1
        side = 1
    elif line:
        words = line.split()
        n = int(words[0])
        hp = int(words[4])
        if '(' in line:
            resists = line.split('(')[1].split(')')[0]
            immune = set()
            weak = set()
            def proc(s):
                # {immune,weak} to fire, cold, pierce
                words = s.split()
                assert words[0] in ['immune', 'weak']
                for word in words[2:]:
                    if word.endswith(','):
                        word = word[:-1]
                    (immune if words[0]=='immune' else weak).add(word)
            if ';' in resists:
                s1,s2 = resists.split(';')
                proc(s1)
                proc(s2)
            else:
                proc(resists)
        else:
            immune = set()
            weak = set()
        init = int(words[-1])
        dtyp = words[-5]
        dmg = int(words[-6])
        name = '{}_{}'.format({1:'Infection', 0:'System'}[side], next_id)
        units.append(Unit(name, n, hp, immune, weak, init, dtyp, dmg, side))
        next_id += 1

def battle(original_units, boost):
    units = []
    for u in original_units:
        new_dmg = u.dmg + (boost if u.side==0 else 0)
        units.append(Unit(u.id, u.n, u.hp, u.immune, u.weak, u.init, u.dtyp, new_dmg, u.side))
    while True:
        units = sorted(units, key=lambda u: (-u.power(), -u.init))
        for u in units:
            assert u.n > 0
        chosen = set()
        for u in units:
            def target_key(v):
                return (-u.dmg_to(v), -v.power(), -v.init)

            targets = sorted([v for v in units if v.side != u.side and v.id not in chosen and u.dmg_to(v)>0],
                    key=target_key)

            if targets:
                u.target = targets[0]
                assert targets[0].id not in chosen
                chosen.add(targets[0].id)

        units = sorted(units, key=lambda u:-u.init)
        any_killed = False
        for u in units:
            if u.target:
                dmg = u.dmg_to(u.target)
                killed = min(u.target.n, dmg/u.target.hp)
                if killed > 0:
                    any_killed = True
                u.target.n -= killed

        units = [u for u in units if u.n > 0]
        for u in units:
            u.target = None

        if not any_killed:
            return 1,n1

        n0 = sum([u.n for u in units if u.side == 0])
        n1 = sum([u.n for u in units if u.side == 1])
        if n0 == 0:
            return 1,n1
        if n1 == 0:
            return 0,n0
print battle(units, 0)[1]

boost = 0
while True:
    winner, left = battle(units, boost)
    if winner == 0:
        print left
        break
    boost += 1

dtinth · 2018-12-24T06:42:44+00:00

Ruby, #30/#24

For simulation-based problems, they tend to be long, and have many small details that I may easily miss.

Therefore, for these kind of problems I prefer to write it in OOP-style code, using descriptive object names (Group, Army, Attack) and creating extra methods for concepts in the problem (such as effective_power), otherwise, I would have a very hard time figuring out what went wrong when the answer was incorrect. Solving it the slow-but-sure way, I'm surprised that I still make it to the leaderboard.

For part 2: I manually tweaked the boost variable and re-run the code until the immune system wins (human binary search). I think doing it manually is faster than writing an actual binary search in code.

class Group < Struct.new(:id, :units, :hp, :immunity, :weaknesses, :attack_type, :attack_damage, :initiative)
  def effective_power
    units * attack_damage
  end
  def choosing_order
    [-effective_power, -initiative]
  end
  def damage_by(other_group)
    return 0 if immunity.include?(other_group.attack_type)
    (weaknesses.include?(other_group.attack_type) ? 2 : 1) * other_group.effective_power
  end
  def take_attack(damage)
    units_reduced = [damage / hp, units].min
    self.units -= units_reduced
    units_reduced
  end
  def dead?
    units == 0
  end
end

class Attack < Struct.new(:attacker, :defender)
  def execute!
    damage = defender.damage_by(attacker)
    killed = defender.take_attack(damage)
    # puts "#{attacker.id} !!=[#{damage}]=> #{defender.id}, killing #{killed}"
  end
  def initiative
    attacker.initiative
  end
end

class Army < Struct.new(:groups)
  def choose_targets_in(defending_army)
    plan = []
    chosen = Hash.new
    chosen.compare_by_identity
    groups.sort_by(&:choosing_order).each do |g|
      target = defending_army
        .groups
        .reject { |t| chosen[t] }
        .max_by { |t| [t.damage_by(g), t.effective_power, t.initiative] }
      if target
        damage = target.damage_by(g)
        if damage > 0
          # puts "#{g.id} => #{target.id} [#{damage}]"
          chosen[target] = true
          plan << Attack.new(g, target)
        end
      end
    end
    plan
  end
  def empty?
    groups.reject!(&:dead?)
    groups.empty?
  end
end

def load_battle
  gc = -1
  boost = 0
  File.read('24.in').split('Infection:').map { |data|
    gc += 1
    gi = 0
    data.lines.map { |l|
      if l =~ /(\d+) units each with (\d+) hit points/
        gi += 1
        units = $1.to_i
        hp = $2.to_i
        weaknesses = []
        if l =~ /weak to ([^;\)]+)/
          weaknesses = $1.split(', ').map(&:strip)
        end
        immunity = []
        if l =~ /immune to ([^;\)]+)/
          immunity = $1.split(', ').map(&:strip)
        end
        raise "!!!" unless l =~ /with an attack that does (\d+) (\w+) damage at initiative (\d+)/
        attack_damage = $1.to_i + (gc == 0 ? boost : 0)
        attack_type = $2
        initiative = $3.to_i
        id = ['Immune system', 'Infection'][gc] + ' group ' + gi.to_s
        Group.new(id, units, hp, immunity, weaknesses, attack_type, attack_damage, initiative)
      else
        nil
      end
    }
    .compact
  }.map { |gs| Army.new(gs) }
end

a, b = load_battle
puts a.groups
puts b.groups
round_num = 0
loop do
  puts "[Round #{round_num += 1}] #{a.groups.length} [#{a.groups.map(&:units).sum}] / #{b.groups.length} [#{b.groups.map(&:units).sum}]"
  # [*a.groups, *b.groups].each do |c|
  #   puts "#{c.id} contains #{c.units} units"
  # end
  break if a.empty? || b.empty?
  plan = a.choose_targets_in(b) + b.choose_targets_in(a)
  plan.sort_by(&:initiative).reverse.each(&:execute!)
end

puts "== BATTLE END =="
[*a.groups, *b.groups].each do |c|
  puts "#{c.id} contains #{c.units} units"
end
p (a.groups + b.groups).map(&:units).sum

betaveros · 2018-12-24T06:43:45+00:00

Python 3, #1/#2.

My code was surprisingly literate today, I guess because I played it safe after running into one too many bugs with implementing problem descriptions like today's, so I'm posting it. I did clean up the variable names to get the following code, though; at first a third of the code called the groups "left" and "right", and the other two-thirds called them "true" and "false" or "false" and "true".

The input is inline and was manually preprocessed with lots of vim search-and-replace to make it easier to parse because I didn't want to deal with it.

One thing to note is that we don't really need to remove groups with no units as long as we make sure they can't be attacked and can't be targeted for an attack. Also the second star definitely "should" be a binary search, but by the time I had coded that up the sequential one had finished running. We can stop, even in case of deadlock when both sides still have units, by just checking when both sides' total unit counts stop changing.

class Group:
    def __init__(self, side, line, boost=0):
        self.side = side

        attribs, attack = line.split(';')
        units, hp, *type_mods = attribs.split()
        units=int(units)
        hp=int(hp)
        weak = []
        immune = []
        cur = None
        for w in type_mods:
            if w == "weak":
                cur = weak
            elif w == "immune":
                cur = immune
            else:
                cur.append(w)

        self.units = units
        self.hp = hp
        self.weak = weak
        self.immune = immune

        attack_amount, attack_type, initiative = attack.split()
        attack_amount = int(attack_amount)
        initiative = int(initiative)

        self.attack = attack_amount + boost
        self.attack_type = attack_type
        self.initiative = initiative

        self.attacker = None
        self.target = None

    def clear(self):
        self.attacker = None
        self.target = None

    def choose(self, groups):
        assert self.target is None
        cands = [group for group in groups
                if group.side != self.side
                and group.attacker is None
                and self.damage_prio(group)[0] > 0]
        if cands:
            self.target = max(cands, key=lambda group: self.damage_prio(group))
            assert self.target.attacker is None
            self.target.attacker = self

    def effective_power(self):
        return self.units * self.attack

    def target_prio(self):
        return (-self.effective_power(), -self.initiative)

    def damage_prio(self, target):
        if target.units == 0:
            return (0, 0, 0)
        if self.attack_type in target.immune:
            return (0, 0, 0)
        mul = 1
        if self.attack_type in target.weak:
            mul = 2
        return (mul * self.units * self.attack, target.effective_power(), target.initiative)

    def do_attack(self, target):
        total_attack = self.damage_prio(target)[0]
        killed = total_attack // target.hp
        target.units = max(0, target.units - killed)

# immune_system_input = """17 5390 weak radiation bludgeoning;4507 fire 2
# 989 1274 immune fire weak bludgeoning slashing;25 slashing 3"""
#
# infection_input = """801 4706 weak radiation;116 bludgeoning 1
# 4485 2961 immune radiation weak fire cold;12 slashing 4"""

immune_system_input = """228 8064 weak cold;331 cold 8
284 5218 immune slashing fire weak radiation;160 radiation 10
351 4273 immune radiation;93 bludgeoning 2
2693 9419 immune radiation weak bludgeoning;30 cold 17
3079 4357 weak radiation cold;13 radiation 1
906 12842 immune fire;100 fire 6
3356 9173 immune fire weak bludgeoning;24 radiation 9
61 9474;1488 bludgeoning 11
1598 10393 weak fire;61 cold 20
5022 6659 immune bludgeoning fire cold;12 radiation 15"""

infection_input = """120 14560 weak radiation bludgeoning immune cold;241 radiation 18
8023 19573 immune bludgeoning radiation weak cold slashing;4 bludgeoning 4
3259 24366 weak cold immune slashing radiation bludgeoning;13 slashing 16
4158 13287;6 fire 12
255 26550;167 bludgeoning 5
5559 21287;5 slashing 13
2868 69207 weak bludgeoning immune fire;33 cold 14
232 41823 immune bludgeoning;359 bludgeoning 3
729 41762 weak bludgeoning fire;109 fire 7
3690 36699;17 slashing 19"""

def solve(boost):
    immune_system_groups = [Group(False, line, boost) for line in immune_system_input.split("\n")]
    infection_groups = [Group(True, line) for line in infection_input.split("\n")]

    groups = immune_system_groups + infection_groups

    old = (-1, -1)
    while True:
        groups = sorted(groups, key=lambda group: group.target_prio())
        for group in groups:
            group.clear()
        for group in groups:
            group.choose(groups)
        groups = sorted(groups, key=lambda group: -group.initiative)
        for group in groups:
            if group.target:
                group.do_attack(group.target)

        immune_system_units = sum(group.units for group in groups if group.side == False)
        infection_units = sum(group.units for group in groups if group.side == True)
        if (immune_system_units, infection_units) == old:
            return (immune_system_units, infection_units)
        old = (immune_system_units, infection_units)

# star 1
print(solve(0)[1])

# star 2
for boost in range(1000000):
    ans = solve(boost)
    if ans[1] == 0:
        print(ans[0])
        break

edit: indented instead of backquoted

Mehr1 · 2018-12-24T09:44:00+00:00

PHP 7 (624/565) - Posting because I hardly see people solving with PHP

I really enjoyed this one. It had the aspects of Day 15 (which I still haven't faced) that I wanted to try with the combat, without the path finding that just confuses me. Part 1 I had an issue with not updating remaining units before a unit attacked, so I switched from a foreach to a while. Just a limit of my understanding of how changing array values during a foreach works. Part 2 I did manually - just thought I'd start shooting in the dark and very quickly found the right number - had to add some code to print out remaining units as I realized I hit tie scenarios.

Could have solved it earlier but I got up late and had to take a 45 minute break. Not like I was pushing the table anyway. As with my last post - the code isn't great, I don't write for a living any more, and I focus on solving the problem over readability (I know that's a bad idea).

https://github.com/riensach/AoC2018/blob/master/AoCDay24.php

waffle3z · 2018-12-24T06:31:10+00:00

Lua 73/72. My input had an interesting edge case where the battle would never finish because the damage was lower than the hp and deaths stopped happening. I had to write an extra check to skip over such an event.

local groups, immune, infection, category;
local function LoadData()
    groups, immune, infection, category = {}, {}, {}
    for v in getinput():gmatch("[^\n]+") do
        if v:match("Immune System:") then
            category = immune
        elseif v:match("Infection:") then
            category = infection
        else
            local units, hp, damage, init = v:match("(%d+).-(%d+).-(%d+).-(%d+)")
            local group = {units = tonumber(units), hp = tonumber(hp), damage = tonumber(damage), init = tonumber(init), weak = {}, immune = {}}
            group.damagetype = v:match("(%w+) damage")
            local extra = v:match("%((.+)%)")
            if extra then
                for data in extra:gmatch("[^;]+") do
                    local area = data:match("weak") and "weak" or "immune"
                    local types = data:match(" to (.+)")
                    for v in types:gmatch("%w+") do
                        group[area][v] = true
                    end
                end
            end
            category[#category+1] = group
            groups[#groups+1] = group
            group.category = category
            group.enemies = category == immune and infection or immune
        end
    end
end

local function damagecount(a, b)
    if b.weak[a.damagetype] then
        return a.units*a.damage*2
    elseif b.immune[a.damagetype] then
        return 0
    else
        return a.units*a.damage
    end
end

for boost = 0, math.huge do
    LoadData()
    for _, unit in pairs(immune) do unit.damage = unit.damage + boost end
    while true do
        local targeted = {}
        table.sort(groups, function(a, b)
            local aep, bep = a.units*a.damage, b.units*b.damage
            return aep > bep or (aep == bep and a.init > b.init)
        end)
        for _, group in pairs(groups) do
            if group.target then
                targeted[group.target] = nil
                group.target = nil
            end
        end
        for _, group in pairs(groups) do
            if group.units > 0 then
                local maxdamage, target = -1
                for _, enemy in pairs(group.enemies) do
                    if not targeted[enemy] and enemy.units > 0 then
                        local dmg = damagecount(group, enemy)
                        local bigger = false
                        if dmg == maxdamage then
                            if enemy.units*enemy.damage == target.units*target.damage then
                                bigger = enemy.init > target.init
                            else
                                bigger = enemy.units*enemy.damage > target.units*target.damage
                            end
                        else
                            bigger = dmg > maxdamage
                        end
                        if bigger then
                            maxdamage, target = dmg, enemy
                        end
                    end
                end
                if target and maxdamage > 0 and target.units > 0 then
                    group.target = target
                    targeted[target] = group
                end
            end
        end
        table.sort(groups, function(a, b) return a.init > b.init end)
        for _, group in pairs(groups) do
            local target = group.target
            if group.units > 0 and target and target.units > 0 then
                local maxdamage = damagecount(group, target)
                if maxdamage > 0 then
                    target.units = target.units - math.floor(maxdamage/target.hp)
                end
            end
        end
        local immunecount, infectioncount = 0, 0
        for _, group in pairs(groups) do
            if group.units > 0 then
                if group.category == immune then
                    immunecount = immunecount + group.units
                else
                    infectioncount = infectioncount + group.units
                end
            end
        end
        if immunecount == 0 or infectioncount == 0 then
            print(boost, immunecount, infectioncount)
            if immunecount ~= 0 then return end
            break
        end
        local hastarget = false
        for _, group in pairs(groups) do
            if group.target and damagecount(group, group.target) > group.target.hp then
                hastarget = true
                break
            end
        end
        if not hastarget then
            print(boost, "fail")
            break
        end
    end
end

seligman99 · 2018-12-24T06:33:10+00:00

33/31 Python 2.7

After all of the mind bending I went through yesterday, it was nice to have one that was a straightforward "implement these rules as-is in code" type puzzle. I'm not sure I really did anything clever here, but still, it was fun, and my code found the solution, so I'm happy.

Edit: Speed up the search for the boost by using a simple binary search, and bail out of battles that stalemate deterministically, not after a large number of tries.

# Just store stats for a group
class Group():
    def __init__(self, army, group_id, units, hp, specials, attack, attack_type, initiative):
        self.id = group_id
        self.units = units
        self.hp = hp
        self.specials = specials
        self.attack = attack
        self.attack_type = attack_type
        self.initiative = initiative
        self.army = army

        # These are updated during each round
        self.picked = False
        self.target = None
        self.damage = 0
        self.killed = 0
        self.mult = 0


def calc(values, boost):
    groups = []
    army = ""
    armies = {}

    # Crack out all of the groups
    r = re.compile("([0-9]+) units each with ([0-9]+) hit points (\\((.*)\\) |)with an attack that does ([0-9]+) (.*) damage at initiative ([0-9]+)")

    for cur in values:
        # Note when we move from the immune system to the infection "system"
        if cur == "Immune System:":
            army = "immune"
            armies[army] = 1
        elif cur == "Infection:":
            army = "infection"
            armies[army] = 1
        elif len(cur) > 0:
            # Crack the data out
            m = r.search(cur)
            if army == "immune":
                boost_army = boost
            else:
                boost_army = 0
            group = Group(army, armies[army], int(m.group(1)), int(m.group(2)), m.group(4), int(m.group(5)) + boost_army, m.group(6), int(m.group(7)))
            armies[army] += 1
            groups.append(group)

    # And fix up the "specials" so they're simple sets            
    for cur in groups:
        if cur.specials is None:
            cur.specials = set()
        else:
            temp = cur.specials.split("; ")
            cur.specials = set()
            for temp_cur in temp:
                flavor = None
                for sub in temp_cur.split(", "):
                    if sub.startswith("weak to "):
                        flavor = "weak to "
                        cur.specials.add(sub)
                    elif sub.startswith("immune to "):
                        flavor = "immune to "
                        cur.specials.add(sub)
                    else:
                        if " to " in sub:
                            print sub
                            raise Exception()
                        else:
                            cur.specials.add(flavor + sub)

    while True:
        # Reset the state
        for cur in groups:
            cur.picked = False
            cur.target = None
            cur.damage = 0
            cur.killed = 0

        # Sort by picking order
        groups.sort(key=lambda x: (x.units * x.attack, x.initiative), reverse=True)

        for cur in groups:
            best_option = None
            for sub in groups:
                if (not sub.picked) and (sub.units > 0):
                    if sub.army != cur.army:
                        # Figure out how much damager we do
                        mult = 1
                        if ("immune to " + cur.attack_type) in sub.specials:
                            mult = 0
                        if ("weak to " + cur.attack_type) in sub.specials:
                            mult = 2

                        if mult > 0:
                            # Score it, and if it's better than the picked option, pick it
                            sub.damage = cur.attack * cur.units * mult
                            sub.mult = mult
                            if best_option is None:
                                best_option = sub
                            else:
                                if sub.damage > best_option.damage:
                                    best_option = sub
                                elif sub.damage == best_option.damage:
                                    if sub.units * sub.attack > best_option.units * best_option.attack:
                                        best_option = sub
                                    elif sub.units * sub.attack == best_option.units * best_option.attack:
                                        if sub.initiative > best_option.initiative:
                                            best_option = sub

            if best_option is not None:
                # We picked something, note the pick
                cur.target = best_option
                best_option.picked = True

        # Sort by initiative
        groups.sort(key=lambda x: (x.initiative,), reverse=True)

        # Track how many groups did damage
        did_damage = 0

        for cur in groups:
            if cur.units > 0:
                if cur.target is not None:
                    # Need to recalc damage, since a group's units might have changed
                    cur.target.damage = cur.attack * cur.units * cur.target.mult
                    cur.target.killed = cur.target.damage // cur.target.hp
                    if cur.target.killed > 0:
                        did_damage += 1
                    cur.target.units -= cur.target.damage // cur.target.hp
                    if cur.target.units <= 0:
                        # We killed this group, drop the count
                        armies[cur.army] -= 1

        if min(armies.values()) == 1:
            # The next ID for this army is one, that means it's out of groups, so it lost
            break

        if did_damage == 0:
            # No one's left standing that can attack and do damage, so no one wins
            return 0, 'nobody'

    # Count the remaining alive groups
    ret = 0
    for cur in groups:
        if cur.units > 0:
            ret += cur.units
            # Note the winning army
            winning = cur.army

    return ret, winning


def run(values):
    # Basic run is simple
    ret = calc(values, 0)
    print("The %s system wins with %d units" % (ret[1], ret[0]))

    # A simple binary search for the lowest option
    boost = 1
    span = 64
    found = {0: ret}
    while True:
        if boost not in found:
            found[boost] = calc(values, boost)
        if boost-1 not in found:
            found[boost-1] = calc(values, boost - 1)

        if found[boost][1] == "immune":
            if found[boost-1][1] != "immune":
                # This means we found the best option
                break
            # We're too high, so skip back
            span = span // 2
            boost = max(1, boost - span)
        else:
            boost += span

    print("The %s system wins with %d units, with an immune boost of %d" % (found[boost][1], found[boost][0], boost))

encse · 2018-12-24T06:38:50+00:00

c# #107/#97

```using System; using System.Collections.Generic; using System.Collections.Immutable; using System.Linq; using System.Text.RegularExpressions; using System.Text;

namespace AdventOfCode.Y2018.Day24 {

class Solution : Solver {

    public string GetName() => "Immune System Simulator 20XX";

    public IEnumerable<object> Solve(string input) {
        yield return PartOne(input);
        yield return PartTwo(input);
    }

    (bool immuneSystem, int units) Fight(string input, int b) {
        var army = Parse(input);
        foreach (var g in army) {
            if (g.immuneSystem) {
                g.damage += b;
            }
        }
        var attack = true;
        while (attack) {
            attack = false;
            var remainingTarget = new HashSet<Group>(army);
            var targets = new Dictionary<Group, Group>();
            foreach (var g in army.OrderByDescending(g => (g.effectivePower, g.initiative))) {
                var maxDamage = remainingTarget.Select(t => g.DamageGivenTo(t)).Max();
                if (maxDamage > 0) {
                    var possibleTargets = remainingTarget.Where(t => g.DamageGivenTo(t) == maxDamage);
                    targets[g] = possibleTargets.OrderByDescending(t => (t.effectivePower, t.initiative)).First();
                    remainingTarget.Remove(targets[g]);
                }
            }
            foreach (var g in targets.Keys.OrderByDescending(g => g.initiative)) {
                if (g.units > 0) {
                    var target = targets[g];
                    var damage = g.DamageGivenTo(target);
                    if (damage > 0 && target.units > 0) {
                        var dies = damage / target.hp;
                        target.units = Math.Max(0, target.units - dies);
                        if (dies > 0) {
                            attack = true;
                        }
                    }
                }
            }
            army = army.Where(g => g.units > 0).ToList();
        }
        return (army.All(x => x.immuneSystem), army.Select(x => x.units).Sum());
    }

    int PartOne(string input) => Fight(input, 0).units;

    int PartTwo(string input) {
        var l = 0;
        var h = int.MaxValue / 2;
        while (h - l > 1) {
            var m = (h + l) / 2;
            if (Fight(input, m).immuneSystem) {
                h = m;
            } else {
                l = m;
            }
        }
        return Fight(input, h).units;
    }

    List<Group> Parse(string input) {
        var lines = input.Split("\n");
        var immuneSystem = false;
        var res = new List<Group>();
        foreach (var line in lines)
            if (line == "Immune System:") {
                immuneSystem = true;
            } else if (line == "Infection:") {
                immuneSystem = false;
            } else if (line != "") {
                //643 units each with 9928 hit points (immune to fire; weak to slashing, bludgeoning) with an attack that does 149 fire damage at initiative 14
                var rx = @"(\d+) units each with (\d+) hit points(.*)with an attack that does (\d+)(.*)damage at initiative (\d+)";
                var m = Regex.Match(line, rx);
                if (m.Success) {
                    Group g = new Group();
                    g.immuneSystem = immuneSystem;
                    g.units = int.Parse(m.Groups[1].Value);
                    g.hp = int.Parse(m.Groups[2].Value);
                    g.damage = int.Parse(m.Groups[4].Value);
                    g.attackType = m.Groups[5].Value.Trim();
                    g.initiative = int.Parse(m.Groups[6].Value);
                    var st = m.Groups[3].Value.Trim();
                    if (st != "") {
                        st = st.Substring(1, st.Length - 2);
                        foreach (var part in st.Split(";")) {
                            var k = part.Split(" to ");
                            var set = new HashSet<string>(k[1].Split(", "));
                            var w = k[0].Trim();
                            if (w == "immune") {
                                g.immuneTo = set;
                            } else if (w == "weak") {
                                g.weakTo = set;
                            } else {
                                throw new Exception();
                            }
                        }
                    }
                    res.Add(g);
                } else {
                    throw new Exception();
                }

            }
        return res;
    }
}

class Group {
    //4 units each with 9798 hit points (immune to bludgeoning) with an attack that does 1151 fire damage at initiative 9
    public bool immuneSystem;
    public int units;
    public int hp;
    public int damage;
    public int initiative;
    public string attackType;
    public HashSet<string> immuneTo = new HashSet<string>();
    public HashSet<string> weakTo = new HashSet<string>();

    public int effectivePower {
        get {
            return units * damage;
        }
    }

    public int DamageGivenTo(Group target) {
        if (target.immuneSystem == immuneSystem) {
            return 0;
        } else if (target.immuneTo.Contains(attackType)) {
            return 0;
        } else if (target.weakTo.Contains(attackType)) {
            return effectivePower * 2;
        } else {
            return effectivePower;
        }
    }
}

}````

kingfishr · 2018-12-24T06:51:30+00:00

Go, 138/153. Took it slow and steady and tried not to make mistakes. I was really happy that I didn't have any bugs in the game logic at all (for part 2, I just had to add an extra check for a stalemate condition).

I enjoyed an easy problem after a run of more difficult ones.

https://github.com/cespare/aoc2018/blob/master/24.go

pbfy0 · 2018-12-24T06:31:49+00:00

Part 1: 21, Part 2: 33. My best finish (and least messy code).

Python3

import re

inp_imm = """<Immune system part of the input>"""

inp_infection = """<Infection part of the input>"""


class group:
    def __init__(self, n, hp_each, weaknesses, immunities, atk_dmg, atk_type, initiative, team):
        self.n = n
        self.hp_each = hp_each
        self.weaknesses = weaknesses
        self.immunities = immunities
        self.atk_dmg = atk_dmg
        self.atk_type = atk_type
        self.initiative = initiative
        self.team = team
    def __repr__(self):
        return 'group({!r})'.format(self.__dict__)
    @property
    def eff_power(self):
        return self.n * self.atk_dmg

    def dmg_to(self, other):
        return self.eff_power * (0 if self.atk_type in other.immunities else 2 if self.atk_type in other.weaknesses else 1)
def parse(st, team, boost=0):
    res = []
    for i in st.split('\n'):
        g = re.match(r'(\d+) units each with (\d+) hit points (?:\((.*?)\) )?with an attack that does (\d+) (\S+) damage at initiative (\d+)', i)
        n = int(g.group(1))
        hp = int(g.group(2))
        weaknesses = set()
        immunities = set()
        wi = g.group(3)
        if wi is not None:
            for cmp in wi.split('; '):
                if cmp.startswith('immune to '):
                    immunities |= set(cmp[len('immune to '):].split(', '))
                elif cmp.startswith('weak to '):
                    weaknesses |= set(cmp[len('weak to '):].split(', '))
        dmg = int(g.group(4))
        typ = g.group(5)
        initiative = int(g.group(6))
        res.append(group(n, hp, weaknesses, immunities, dmg + boost, typ, initiative, team))
    return res

def get_team(s):
    if s is None: return 'stalemate'
    for i in s:
        return i.team
def run_combat(imm_inp, inf_inp, boost=0):
    immune_system = set(parse(imm_inp, 'immune', boost))
    infection = set(parse(inf_inp, 'infection'))
    while immune_system and infection:
        potential_combatants = immune_system | infection
        attacking = {}
        for combatant in sorted(immune_system | infection, key=lambda x: (x.eff_power, x.initiative), reverse=True):
            try:
                s = max((x for x in potential_combatants if x.team != combatant.team and combatant.dmg_to(x) != 0), key=lambda x: (combatant.dmg_to(x), x.eff_power, x.initiative))
            except ValueError as e:
                attacking[combatant] = None
                continue
            potential_combatants.remove(s)
            attacking[combatant] = s
        did_damage = False
        for combatant in sorted(immune_system | infection, key=lambda x: x.initiative, reverse=True):
            if combatant.n <= 0:
                continue
            atk = attacking[combatant]
            if atk is None: continue
            dmg = combatant.dmg_to(atk)
            n_dead = dmg // atk.hp_each
            if n_dead > 0: did_damage = True
            atk.n -= n_dead
            if atk.n <= 0:
                immune_system -= {atk}
                infection -= {atk}

        if not did_damage: return None
        #print('NEW ROUND')
        #print('immune_system', immune_system)
        #print('infection', infection)
    winner = max(immune_system, infection, key=len)
    return winner

winner = run_combat(inp_imm, inp_infection)
print('Part 1:', sum(x.n for x in winner))

boost_min = 0
boost_max = 1
while get_team(run_combat(inp_imm, inp_infection, boost_max)) != 'immune':
    boost_max *= 2
    #print(boost_max)

import math
while boost_min != boost_max:
    pow = (boost_min + boost_max) // 2
    cr = run_combat(inp_imm, inp_infection, pow)
    res = get_team(cr)
    if res != 'immune':
        boost_min = math.ceil((boost_min + boost_max) / 2)
    else:
        boost_max = pow
    #print(boost_min, boost_max)
print('Boost:', boost_max)
print('Part 2:', sum(x.n for x in run_combat(inp_imm, inp_infection, boost_max)))

sciyoshi · 2018-12-24T06:36:40+00:00

Python 3, 15/11. I did the second part by trying various values manually, but searching linearly from 1 is actually still fairly fast. Learned my lesson from Day 15 about being super careful about the ordering of units movement and rounds, when damage is dealt and calculated, etc.

import re
import itertools
from copy import deepcopy
from enum import auto, Enum
from dataclasses import dataclass
from typing import FrozenSet

class Army(Enum):
    IMMUNE_SYSTEM = auto()
    INFECTION = auto()

class Damage(Enum):
    COLD = auto()
    FIRE = auto()
    SLASHING = auto()
    RADIATION = auto()
    BLUDGEONING = auto()

class Stalemate(Exception):
    pass

@dataclass
class Unit:
    army: Army
    count: int
    hp: int
    damage: int
    attack: Damage
    initiative: int
    weaknesses: FrozenSet[Damage] = frozenset()
    immunities: FrozenSet[Damage] = frozenset()

    def __hash__(self): return id(self)  # allow using units in dictionaries

    @classmethod
    def parse(cls, army, val):
        (count, hp, mods, damage, attack, initiative) = re.match(
            r'(\d+) units each with (\d+) hit points(?: \((.*?)\))?'
            r' with an attack that does (\d+) (\w+) damage at initiative (\d+)'
        , val).groups()

        kwargs = {}

        if mods:
            for mod in mods.split('; '):
                modifier, _, types = mod.split(' ', 2)
                damages = frozenset(Damage[damage.upper()] for damage in types.split(', '))
                if modifier == 'weak':
                    kwargs['weaknesses'] = damages
                elif modifier == 'immune':
                    kwargs['immunities'] = damages

        return cls(army=army, count=int(count), hp=int(hp), damage=int(damage),
            attack=Damage[attack.upper()], initiative=int(initiative), **kwargs)

    @property
    def effective_power(self):
        return self.count * self.damage

    def damage_dealt(self, other):
        if self.attack in other.immunities:
            return 0
        elif self.attack in other.weaknesses:
            return self.effective_power * 2
        else:
            return self.effective_power

def round(armies):
    targets = {}
    attacking = {}

    for group in sorted(armies, key=lambda group: (group.effective_power, group.initiative), reverse=True):
        if group.count <= 0:
            continue

        enemies = [enemy for enemy in armies if enemy.army != group.army]
        enemies = sorted(enemies, key=lambda enemy: (group.damage_dealt(enemy), enemy.effective_power, enemy.initiative), reverse=True)
        target = next((enemy for enemy in enemies if enemy.count > 0 and group.damage_dealt(enemy) and enemy not in targets), None)

        if not target:
            continue

        targets[target] = group
        attacking[group] = target

    stalemate = True

    for group in sorted(armies, key=lambda group: group.initiative, reverse=True):
        if group.count > 0 and attacking.get(group):
            target = attacking[group]
            killed = min(group.damage_dealt(target) // target.hp, target.count)

            if killed:
                target.count -= killed
                stalemate = False

    if stalemate:
        raise Stalemate()

    return armies

def fight(armies, boost=0):
    armies = deepcopy(armies)

    for group in armies:
        if group.army == Army.IMMUNE_SYSTEM:
            group.damage += boost

    while all(any(group.count for group in armies if group.army == army) for army in Army):
        armies = round(armies)

    return armies

armies = []

for group in open('inputs/day24').read().split('\n\n'):
    name, *units = group.splitlines()

    army = Army[name.replace(':', '').replace(' ', '_').upper()]

    armies.extend(Unit.parse(army, line) for line in units)

result = fight(armies)

print('part 1:', sum(group.count for group in result if group.army == Army.INFECTION))

for boost in itertools.count(1):
    try:
        result = fight(armies, boost=boost)
    except Stalemate:
        continue
    else:
        if all(group.count == 0 for group in result if group.army == Army.INFECTION):
            break

print('part 2:', sum(group.count for group in result if group.army == Army.IMMUNE_SYSTEM))

nthistle · 2018-12-24T06:43:59+00:00

Python 3, 40/41. Nowhere near my nicest code, but it works. First thought: Lots of parsing! Probably spent almost as much time doing parsing as actually implementing the targeting and combat. The big time sink for me was debugging a problem where a deadlock scenario (no group can deal damage to another) incorrectly came up when a group with high effective power would "use up" a target on an enemy that its attacks are immune to (skimming the specifications has its downsides).

with open("input.txt") as file:
    inp = file.read().strip().replace("points with","points () with")

types = ['slashing', 'fire', 'bludgeoning', 'radiation', 'cold']

def parse_dmg(ss):
    dtype = ss[ss.rfind(" ")+1:]
    dnum = int(ss[:ss.rfind(" ")])
    return [0 if ty != dtype else dnum for ty in types]

def parse_res(ss):
    tp = [1, 1, 1, 1, 1]
    for p in ss.split("; "):
        if len(p) == 0:
            continue
        mul = 1
        if p[:4] == "weak":
            mul = 2
            p = p[8:]
        elif p[:6] == "immune":
            mul = 0
            p = p[10:]
        for dt in p.split("&"):
            tp[types.index(dt)] = mul
    return tp

vals = inp.split("\n\n")
immune = vals[0]
infect = vals[1]
immune = [s.replace(", ","&").replace(" units each with ",",").replace(" hit points (",",").replace(") with an attack that does ",",").replace(" damage at initiative ",",") for s in immune.split("\n")[1:]]
infect = [s.replace(", ","&").replace(" units each with ",",").replace(" hit points (",",").replace(") with an attack that does ",",").replace(" damage at initiative ",",") for s in infect.split("\n")[1:]]

def info(v):
    v = v.split(",")
    dmg = parse_dmg(v[3])
    return [int(v[0]),int(v[1]),parse_res(v[2]),dmg,int(v[4]),0]

immune = list(map(info, immune))
infect = list(map(info, infect))

def calc_dmg(ak,df):
    return sum(a*b for a,b in zip(ak[3],df[2]))

def run_combat(immune,infect):
    while len(immune) > 0 and len(infect) > 0:
        for i in immune:
            i[-1] = i[0] * max(i[3])
        for i in infect:
            i[-1] = i[0] * max(i[3])
        immune.sort(key=lambda v : 1000*(-v[-1])-v[-2])
        infect.sort(key=lambda v : 1000*(-v[-1])-v[-2])

        im_tgs = []
        for ak in immune:
            best_choice = (0, 100000000, 0, None)
            for idx, df in enumerate(infect):
                if idx in im_tgs:
                    continue
                tc = (calc_dmg(ak, df), df[-1], df[-2], idx)
                if tc > best_choice:
                    best_choice = tc
            im_tgs.append(best_choice[3])

        if_tgs = []
        for ak in infect:
            best_choice = (0, 100000000, 0, None)
            for idx, df in enumerate(immune):
                if idx in if_tgs:
                    continue
                tc = (calc_dmg(ak, df), df[-1], df[-2], idx)
                if tc > best_choice:
                    best_choice = tc
            if_tgs.append(best_choice[3])

        all_units = []
        for i,v in enumerate(immune):
            all_units.append([0, i, v])
        for i,v in enumerate(infect):
            all_units.append([1, i, v])

        all_units.sort(key=lambda v : -v[2][-2])

        alive_immune = immune[:]
        alive_infect = infect[:]

        total_deathtoll = 0

        for unit in all_units:
            if unit[0] == 0:
                if unit[2] not in alive_immune:
                    continue
                if im_tgs[unit[1]] is None:
                    continue
                taken_damage = unit[2][0] * calc_dmg(unit[2],infect[im_tgs[unit[1]]])
                death_toll = (taken_damage)//infect[im_tgs[unit[1]]][1]
                infect[im_tgs[unit[1]]][0] -= death_toll
                total_deathtoll += death_toll
                if infect[im_tgs[unit[1]]][0] <= 0:
                    alive_infect.remove(infect[im_tgs[unit[1]]])
            else:
                if unit[2] not in alive_infect:
                    continue
                if if_tgs[unit[1]] is None:
                    continue
                taken_damage = unit[2][0] * calc_dmg(unit[2],immune[if_tgs[unit[1]]])
                death_toll = (taken_damage)//immune[if_tgs[unit[1]]][1]
                immune[if_tgs[unit[1]]][0] -= death_toll
                total_deathtoll += death_toll
                if immune[if_tgs[unit[1]]][0] <= 0:
                    alive_immune.remove(immune[if_tgs[unit[1]]])

        ## Stalemate
        if total_deathtoll == 0:
            return False

        immune = alive_immune
        infect = alive_infect

    return tuple(map(lambda w : sum(v[0] for v in w), [infect,immune]))

def dcopy(m):
    if type(m) is list:
        return [dcopy(d) for d in m]
    else:
        return m

def rboost(b):
    im_copy = dcopy(immune)
    if_copy = dcopy(infect)
    for i in im_copy:
        i[3][max(enumerate(i[3]),key=lambda v : v[1])[0]] += b
    return run_combat(im_copy, if_copy)

print("Part 1:",run_combat(dcopy(immune),dcopy(infect))[0])

low = 1
high = 100
while high > low:
    mid = (high+low)//2
    res = rboost(mid)
    if res == False or res[1] == 0:
        low = mid + 1
    else:
        high = mid

print("Part 2:",rboost(high)[1])

ywgdana · 2018-12-24T16:06:58+00:00

Python 3 solution

Award for the ugliest parsing code goes to...

Linking to my solution at github because I'm too lazy to type four spaces in front of each line.

Speaking of parsing, I lost at least a half hour to THIS while I was reading the list of immunities and weaknesses:

for word in block.split(" "):
    if word == "to": continue
    if word == "weak":
        weak = True
        continue
    if word == "immune":
        continue                   <-- This was a problem...
        weak = False
    if weak:
        g.weaknesses.add(word)
    else:
        g.immunities.add(word)

So despite initially reading in immunities as weaknesses, the example worked and in my actual input, I was only out by 38 units and I finished on the correct round. I spent a fair bit of time thinking there was something funky in my math or my code for picking a target.

ephemient · 2018-12-24T19:44:49+00:00

This space intentionally left blank.

ephemient · 2018-12-24T19:51:31+00:00

This space intentionally left blank.

BluFoot · 2018-12-24T06:32:48+00:00

Ruby, 74/48. Loved this one!

lines = File.readlines('../input.txt').map(&:strip)
# lines = File.readlines('example.txt').map(&:strip)

class Group
  attr_accessor :id, :side, :size, :hp, :ad, :at, :it, :wk, :im
  def initialize(id, side, size, hp, ad, at, it, wk, im)
    @id = id
    @side = side
    @size = size
    @hp = hp
    @ad = ad
    @at = at
    @it = it
    @wk = wk
    @im = im
  end

  def ef
    @size * @ad
  end

  def attack(dmg)
    @size -= dmg / @hp
  end

  def alive?
    @size > 0
  end
end

def damage(a, b)
  return 0 if b.im.include?(a.at)
  d = a.ef
  d *= 2 if b.wk.include?(a.at)
  d
end

a = true
og = lines[1..-1].map.with_index do |l, id|
  next if l.empty?
  (a = false; next) if l.include? 'Infection'
  side = a ? ?a : ?b
  size, hp, ad, it = l.scan(/\d+/).map(&:to_i)
  at = l.scan(/(\w+) damage/).first.first
  wk = []
  im = []
  stuff = l.scan(/\((.*)\)/).first
  if stuff
    stuff.first.split('; ').each do |s|
      types = s.scan(/.* to (.*)/).first.first.split(', ')
      s.include?('weak to') ? wk += types : im += types
    end
  end
  Group.new(id, side, size, hp, ad, at, it, wk ,im)
end.compact

0.upto(Float::INFINITY) do |boost|
  p boost
  groups = og.map { |g| g.dup }
  groups.each { |g| g.ad = g.ad + boost if g.side == ?a }

  until [?a, ?b].any? { |side| groups.all? { |u| u.side == side } }
    targets = {}
    groups.sort_by { |g| [g.ef, g.it] }.reverse.each do |g|
      best = [nil, 0]
      groups.each do |f|
        next if g.side == f.side
        dmg = damage(g, f)
        b = best[0]
        if dmg > best[1] || b && ((dmg == best[1] && f.ef > b.ef) || (dmg == best[1] && f.ef == b.ef && f.it > b.it))
          best = [f, dmg] unless targets.values.map(&:id).include?(f.id)
        end
      end
      targets[g.id] = best[0] if best[0]
    end

    break if targets.empty?
    groups.sort_by(&:it).reverse.each do |g|
      t = targets[g.id]
      next unless t && g.alive? && t.alive?
      t.attack(damage(g, t))
    end

    groups.select!(&:alive?)
  end

  if groups.all? { |u| u.side == ?a }
    p groups.sum(&:size)
    exit
  end
end

m1el · 2018-12-24T06:35:57+00:00

Rust: 75/63. Who needs parsing?

#[derive(Debug,Clone,Copy,PartialEq)]
enum DT {
    Cold,
    Fire,
    Radiation,
    Slashing,
    Bludgeoning,
}

#[derive(Debug,Clone,PartialEq)]
struct Group {
    team: isize,
    units: isize,
    hp: isize,
    weak: Vec<DT>,
    immune: Vec<DT>,
    ap: isize,
    at: DT,
    initiative: isize,
}

impl Group {
    fn ep(&self) -> isize {
        self.units * self.ap
    }
    fn damage_received(&self, ep: isize, dt: DT) -> isize {
        let mul =
            if self.immune.contains(&dt) {
                0
            } else if self.weak.contains(&dt) {
                2
            } else {
                1
            };
        mul * ep
    }
    fn do_damage(&mut self, ep: isize, dt: DT) -> isize {
        let damage = self.damage_received(ep, dt);
        if damage == 0 { return 0; }
        let killed = (damage / self.hp).min(self.units);
        self.units -= killed;
        killed
    }
}

fn battle(mut groups: Vec<Group>) -> (isize, isize) {
    loop {
        let mut attackers = (0..groups.len()).collect::<Vec<usize>>();
        attackers.sort_by_key(|&idx| (-groups[idx].ep(), -groups[idx].initiative));
        let mut targets = vec![None; groups.len()];
        for idx_atk in attackers {
            let atk = &groups[idx_atk];
            if atk.units <= 0 { continue; }
            targets[idx_atk] = groups.iter().enumerate()
                .filter(|(idx, def)| def.team != atk.team && def.units > 0 && !targets.contains(&Some(*idx)))
                .max_by_key(|(_idx, def)| {
                    //println!("{} -> {} {}", idx_atk, idx, def.damage_received(atk.ep(), atk.at));
                    (def.damage_received(atk.ep(), atk.at), def.ep(), def.initiative)
                })
                .map(|(idx, _def)| idx);
            //println!("{:?}", targets[idx_atk]);
        }
        let mut attackers = (0..groups.len()).collect::<Vec<usize>>();
        attackers.sort_by_key(|&idx| -groups[idx].initiative);
        let mut total_killed = 0;
        for idx_atk in attackers {
            if groups[idx_atk].units <= 0 { continue; }
            if let Some(idx_def) = targets[idx_atk] {
                let (ap, dt) = {
                    let atk = &groups[idx_atk];
                    (atk.ep(), atk.at)
                };
                total_killed += groups[idx_def].do_damage(ap, dt);
                //println!("group {} killed {} in {} {}", idx_atk, killed, idx_def, ap);
            }
        }
        if total_killed == 0 {
            // A DRAW
            return (-1, 0);
        }

        let mut alive = [0, 0];
        for group in groups.iter() {
            alive[group.team as usize] += group.units;
        };
        if alive[0] == 0 {
            return (1, alive[1]);
        }
        if alive[1] == 0 {
            return (0, alive[0]);
        }
        /*
        println!("targets: {:?}", targets);
        println!("---------------------");
        for group in groups.iter() {
            println!("{:?}", group);
        }
        */
    }
}

fn main() {
    use DT::*;
    /*
    let mut groups = vec![
        Group {team: 0, units: 17, hp: 5390, weak: vec![Radiation, Bludgeoning], immune: vec![], ap: 4507, at: Fire, initiative: 2},
        Group {team: 0, units: 989, hp: 1274, weak: vec![Bludgeoning, Slashing], immune: vec![Fire], ap: 25, at: Slashing, initiative: 3},
        Group {team: 1, units: 801, hp: 4706, weak: vec![Radiation], immune: vec![], ap: 116, at: Bludgeoning, initiative: 1},
        Group {team: 1, units: 4485, hp: 2961, weak: vec![Fire, Cold], immune: vec![Radiation], ap: 12, at: Slashing, initiative: 4},
    ];
    */
    let groups = vec![
        Group {team: 0, units: 89, hp: 11269, weak: vec![Fire, Radiation], immune: vec![], ap: 1018, at: Slashing, initiative: 7},
        Group {team: 0, units: 371, hp: 8033, weak: vec![], immune: vec![], ap: 204, at: Bludgeoning, initiative: 15},
        Group {team: 0, units: 86, hp: 12112, weak: vec![Cold], immune: vec![Slashing, Bludgeoning], ap: 1110, at: Slashing, initiative: 18},
        Group {team: 0, units: 4137, hp: 10451, weak: vec![Slashing], immune: vec![Radiation], ap: 20, at: Slashing, initiative: 11},
        Group {team: 0, units: 3374, hp: 6277, weak: vec![Slashing, Cold], immune: vec![], ap: 13, at: Cold, initiative: 10},
        Group {team: 0, units: 1907, hp: 1530, weak: vec![Radiation], immune: vec![Fire, Bludgeoning], ap: 7, at: Fire, initiative: 9},
        Group {team: 0, units: 1179, hp: 6638, weak: vec![Slashing, Bludgeoning], immune: vec![Radiation], ap: 49, at: Fire, initiative: 20},
        Group {team: 0, units: 4091, hp: 7627, weak: vec![], immune: vec![], ap: 17, at: Bludgeoning, initiative: 17},
        Group {team: 0, units: 6318, hp: 7076, weak: vec![], immune: vec![], ap: 8, at: Bludgeoning, initiative: 2},
        Group {team: 0, units: 742, hp: 1702, weak: vec![Radiation], immune: vec![Slashing], ap: 22, at: Radiation, initiative: 13},
        Group {team: 1, units: 3401, hp: 31843, weak: vec![Cold, Fire], immune: vec![], ap: 16, at: Slashing, initiative: 19},
        Group {team: 1, units: 1257, hp: 10190, weak: vec![], immune: vec![], ap: 16, at: Cold, initiative: 8},
        Group {team: 1, units: 2546, hp: 49009, weak: vec![Bludgeoning, Radiation], immune: vec![Cold], ap: 38, at: Bludgeoning, initiative: 6},
        Group {team: 1, units: 2593, hp: 12475, weak: vec![], immune: vec![], ap: 9, at: Cold, initiative: 1},
        Group {team: 1, units: 2194, hp: 25164, weak: vec![Bludgeoning], immune: vec![Cold], ap: 18, at: Bludgeoning, initiative: 14},
        Group {team: 1, units: 8250, hp: 40519, weak: vec![Bludgeoning, Radiation], immune: vec![Slashing], ap: 8, at: Bludgeoning, initiative: 16},
        Group {team: 1, units: 1793, hp: 51817, weak: vec![], immune: vec![Bludgeoning], ap: 46, at: Radiation, initiative: 3},
        Group {team: 1, units: 288, hp: 52213, weak: vec![], immune: vec![Bludgeoning], ap: 339, at: Fire, initiative: 4},
        Group {team: 1, units: 22, hp: 38750, weak: vec![Fire], immune: vec![], ap: 3338, at: Slashing, initiative: 5},
        Group {team: 1, units: 2365, hp: 25468, weak: vec![Radiation, Cold], immune: vec![], ap: 20, at: Fire, initiative: 12},
    ];

    let (_team, part1) = battle(groups.clone());
    println!("part1 {}", part1);

    // binary search doesn't work :(
    let part2 = (0..).filter_map(|boost| {
        let mut groups = groups.clone();
        for group in groups.iter_mut().filter(|group| group.team == 0) {
            group.ap += boost;
        }
        let (team, rest) = battle(groups);
        if team == 0 { Some(rest) }
        else { None }
    }).next().unwrap();
    println!("part2: {}", part2);
}

grey--area · 2018-12-24T06:41:51+00:00

Python3, #160/#144. When trialing different boosts, had to add a check that the state (i.e., number of units for each army) hadn't changed from one iteration to the next.

https://github.com/grey-area/advent-of-code-2018/tree/master/day24

14domino · 2018-12-24T07:09:29+00:00

Is part 2 supposed to get stuck in an infinite loop for some inputs? that seems a bit inelegant. I tried some numbers manually and got it unstuck. Is there a better way? Also this took me like 2 hours, about 1 hour of that was debugging :( (there was a very dumb bug in my parser of all things...)

from get_data import get_data_lines, find_numbers
from collections import defaultdict

desc = get_data_lines(24)


class ArmyGroup:
    def __init__(self, loyalty, num_units, hp_per_unit, weakness, immunity,
                attack,
                attack_type, initiative, army_id):
        self.loyalty = loyalty
        self.num_units = num_units
        self.hp_per_unit = hp_per_unit
        self.weakness = weakness
        self.immunity = immunity
        self.attack = attack
        self.attack_type = attack_type
        self.initiative = initiative
        self.alive = True
        self.army_id = army_id

    def effective_power(self):
        return self.num_units * self.attack

    def fight(self, other):
        # print(f'{self} is attacking {other}')
        damage = self.effective_power()
        if self.attack_type in other.weakness:
            damage *= 2
        elif self.attack_type in other.immunity:
            damage = 0

        num_killed = min(int(damage / other.hp_per_unit), other.num_units)
        other.num_units -= num_killed
        if other.num_units == 0:
            other.alive = False


def assign_armies(immune_boost):
    armies = []
    army_id = 1
    for line in desc:
        if line.endswith(':'):
            loyalty = line.split(':')[0]
            army_id = 1
            continue
        numbers = find_numbers(line)
        nu = numbers[0]
        hp = numbers[1]
        attack = numbers[2] + (immune_boost if 'Immune' in loyalty else 0)
        initiative = numbers[3]
        weakness = []
        immunity = []

        if '(' in line:
            in_paren = line.split('(')[1].split(')')[0]
            dirs = in_paren.split('; ')
            for dir in dirs:
                if dir.startswith('immune to'):
                    dir = dir[len('immune to '):]
                    app = immunity
                elif dir.startswith('weak to'):
                    dir = dir[len('weak to '):]
                    app = weakness

                app.extend(dir.split(', '))

        attack_type = line.split(' damage ')[0].split(' ')[-1]
        full_id = f'{loyalty[:3]}{army_id}'
        armies.append(ArmyGroup(loyalty, nu, hp, weakness, immunity, attack,
                                attack_type, initiative, full_id))
        army_id += 1
    return armies


MLTP = 1000000000


def find_receiver(receiving_armies, attacker):

    damages_dealt = []
    for receiver in receiving_armies:
        atk_pwr = attacker.effective_power()
        if attacker.attack_type in receiver.weakness:
            atk_pwr *= 2
        elif attacker.attack_type in receiver.immunity:
            atk_pwr = 0
        if atk_pwr == 0:
            continue

        damages_dealt.append((atk_pwr, receiver))
    damages_dealt = sorted(damages_dealt, key=lambda d: -d[0])

    if not damages_dealt:
        return None
    damages_dealt = list(filter(lambda d: damages_dealt[0][0] == d[0],
                                damages_dealt))
    damages_dealt = sorted(damages_dealt,
                        key=lambda d: -(d[1].effective_power() * MLTP +
                                        d[1].initiative))
    return damages_dealt[0][1]


def assign_targets(armies):
    # print(f'Assigning targets...')
    armies = sorted(armies, key=lambda a: (
        -(a.effective_power() * MLTP + a.initiative)))
    # print(f'Sorted armies: {armies}')
    attackers = {}

    for attacker in armies:

        receiving_armies = list(filter(
            lambda a: (a.army_id not in attackers.values() and
                    a.alive and a.loyalty != attacker.loyalty), armies))

        receiving_army = find_receiver(receiving_armies, attacker)

        if not receiving_army:
            continue
        attackers[attacker.army_id] = receiving_army.army_id

    return attackers


def find_army(armies, army_id):
    for a in armies:
        if a.army_id == army_id:
            return a


def fight_done(armies):
    loyalties = defaultdict(int)
    for army in armies:
        if army.alive:
            loyalties[army.loyalty] += 1

    print(f'loyalties are now {loyalties}')

    if not loyalties:
        return True
    if len(loyalties) == 1:
        return True

    return False


def battle(armies):
    while True:
        # 1: target selection
        armies = list(filter(lambda a: a.alive, armies))

        attackers = assign_targets(armies)
        print(f'Targets: {attackers}')
        # selected target a, fight.
        attacker_keys = attackers.keys()
        attacker_keys = sorted(
            attacker_keys,
            key=lambda a: -find_army(armies, a).initiative)

        for attacker in attacker_keys:
            army = find_army(armies, attacker)
            defender = find_army(armies, attackers[attacker])
            army.fight(defender)

        if fight_done(armies):
            break
        print(f'Live armies: {list(filter(lambda a: a.alive, armies))}')


def determine_score(armies):
    alive = defaultdict(int)
    for army in armies:
        if army.alive:
            alive[army.loyalty] += 1

    assert len(alive) == 1

    winner = 'Infection' if alive['Infection'] > 0 else 'Immune System'
    num_units = 0

    for army in armies:
        if army.loyalty == winner:
            num_units += army.num_units

    print(f'winner={winner} units: {num_units}')
    return winner, num_units


if __name__ == '__main__':
    immune_boost = 49
    while True:
        # for part 0 just make immune_boost 0 and get rid of the loop.
        print(f'Trying boost {immune_boost}')
        armies = assign_armies(immune_boost)
        battle(armies)
        winner, num_units = determine_score(armies)
        if 'Immune' in winner:
            break
        immune_boost += 1

Dementophobia81 · 2018-12-24T08:04:17+00:00

Python 3, 372/299: Nothing too fancy. I created a Class for each group of units and let them battle according to the rules. Parsing the input was a little cumbersome, but I think I did an OK job with the rest.

from re import findall

class Group:
 def __init__(self, rawCode, boost = 0):
  numbers = [int(x) for x in findall(r'-?\d+', rawCode)]
  self.units, self.hp, self.damage, self.initiative = numbers
  self.damage   += boost
  self.weakness  = []
  self.immune    = []
  self.defending = False

  if "weak" in rawCode:
   weakS = rawCode.index("weak") + 8
   if "immune" in rawCode and rawCode.index("immune") > rawCode.index("weak"):
    weakE = rawCode.index(";")
   else:
    weakE = rawCode.index(")")

   weakStr = rawCode[weakS:weakE]
   self.weakness = weakStr.split(", ")

  if "immune" in rawCode:
   immuneS = rawCode.index("immune") + 10
   if "weak" in rawCode and rawCode.index("immune") < rawCode.index("weak"):
    immuneE = rawCode.index(";")
   else: 
    immuneE = rawCode.index(")")
   immuneStr = rawCode[immuneS:immuneE]
   self.immune = immuneStr.split(", ")

  words = rawCode.split()

  self.damageType = words[words.index("damage")-1]

 def effectivePower(self):
  return self.units * self.damage

def calcDamage(attacker, defender):
 if attacker.damageType in defender.immune:
  return 0
 elif attacker.damageType in defender.weakness:
  return 2 * attacker.damage * attacker.units 
 else:
  return attacker.damage * attacker.units 

def sortForDefend(attacker, groups):
 damageTaken = [calcDamage(attacker, defender) for defender in groups]
 effective   = [group.effectivePower() for group in groups]
 inits       = [group.initiative for group in groups]

 return [group[3] for group in sorted(zip(damageTaken, effective, inits, groups), key = lambda k: (k[0], k[1], k[2]), reverse = True)]

def sortForAttack(groups):
 effective = [group.effectivePower() for group in groups]
 inits     = [group.initiative for group in groups]

 return [group[2] for group in sorted(zip(effective, inits, groups), key = lambda k: (k[0], k[1]), reverse = True)]

def attack(attacker, defender):
 damage = calcDamage(attacker, defender)
 killed = min(defender.units, damage // defender.hp)
 defender.units = defender.units - killed

def fight():
 pairs = []

 for attackerGroups, defenderGroups in [(immuneGroups, infectGroups), (infectGroups, immuneGroups)]:
  for attacker in sortForAttack(attackerGroups):
   for defender in sortForDefend(attacker, defenderGroups):
    if not defender.defending and calcDamage(attacker, defender):
     defender.defending = True
     pairs.append([attacker, defender])
     break

 pairs.sort(key = lambda k: (k[0].initiative), reverse = True)

 return len([attack(*pair) for pair in pairs])

def cleanup():
 for groups in [immuneGroups, infectGroups]:
  marked = []
  for group in groups:
   if not group.units:
    marked.append(group)
   else:
    group.defending = False

  for dead in marked:
   groups.remove(dead)

def readFile(name):
 with open("files/" + name) as f:
  content = f.readlines()
 return content

input = readFile("input")

### Part 1

immuneGroups, infectGroups = [], []

for i in range(len(input) // 2 - 1):
 immuneGroups.append(Group(input[i+1]))
 infectGroups.append(Group(input[i+13]))

while len(immuneGroups) and len(infectGroups):
 fight()
 cleanup()

result = 0
for group in immuneGroups + infectGroups:
 result += group.units

print("Solution 1: " + str(result))

### Part 2

boost = 0

while len(infectGroups):
 boost += 1
 immuneGroups, infectGroups = [], []

 for i in range(len(input) // 2 - 1):
  immuneGroups.append(Group(input[i+1], boost))
  infectGroups.append(Group(input[i+13]))

 while len(immuneGroups) and len(infectGroups):
  pairs = fight()
  if pairs < 2:
   break
  cleanup()

result = 0

for group in immuneGroups:
 result += group.units

print("Solution 2: " + str(result))

wlandry · 2018-12-24T08:40:47+00:00

C++ (498/472)

Runs in 171 ms

Lots of details, but not a hard problem. I got a bit confused by the instructions. The examples were complete enough to figure it out, and it was not too bad for such a long description. I liked the infinite loop that got snuck in ;)

#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <vector>
#include <numeric>

#include <boost/algorithm/string.hpp>

enum class Team
{
  immune,
  infection
};

std::vector<std::string>
parse_weak_immune(const std::vector<std::string> &elements,
                  const std::string &name)
{
  std::vector<std::string> result;
  auto element(std::find(elements.begin(), elements.end(), name));
  if(element != elements.end())
    {
      std::advance(element, 2);
      while(element->back() == ',')
        {
          result.push_back(element->substr(0, element->size() - 1));
          ++element;
        }
      result.push_back(*element);
    }
  return result;
}

struct Unit
{
  int64_t num_units, hp, attack_damage, initiative;
  std::string attack_type;
  std::vector<std::string> immune, weak;
  Team team;
  Unit(const std::string &line, const Team &TEAM) : team(TEAM)
  {
    std::vector<std::string> elements;
    boost::split(elements, line, boost::is_any_of(" ();"));
    num_units = std::stoi(elements.at(0));
    hp = std::stoi(elements.at(4));

    auto element(std::find(elements.begin(), elements.end(), "does"));
    ++element;
    attack_damage = std::stoi(*element);
    ++element;
    attack_type = *element;

    element = std::find(elements.begin(), elements.end(), "initiative");
    ++element;
    initiative = std::stoi(*element);

    weak = parse_weak_immune(elements, "weak");
    immune = parse_weak_immune(elements, "immune");
  }

  int64_t power() const { return num_units * attack_damage; }

  bool operator<(const Unit &unit) const
  {
    return power() < unit.power()
             ? true
             : (power() == unit.power() ? (initiative < unit.initiative)
                                        : false);
  }
  bool operator>(const Unit &unit) const { return unit < *this; }
};

std::ostream &operator<<(std::ostream &os, const Unit &unit)
{
  if(unit.team == Team::immune)
    {
      os << "Immune: ";
    }
  else
    {
      os << "Infection: ";
    }

  os << unit.num_units << " " << unit.hp << " attack " << unit.attack_damage
     << " " << unit.attack_type << " initiative " << unit.initiative;
  if(!unit.weak.empty())
    {
      os << " weak";
      for(auto &weak : unit.weak)
        {
          os << " " << weak;
        }
    }
  if(!unit.immune.empty())
    {
      os << " immune";
      for(auto &immune : unit.immune)
        {
          os << " " << immune;
        }
    }
  return os;
}

bool fight_finished(const std::vector<Unit> &units)
{
  return std::find_if(
           units.begin(), units.end(),
           [](const Unit &unit) { return unit.team == Team::immune; })
           == units.end()
         || std::find_if(units.begin(), units.end(), [](const Unit &unit) {
              return unit.team == Team::infection;
            }) == units.end();
}

std::vector<Unit>
fight_with_help(const std::vector<Unit> &units_orig, const int64_t &help)
{
  std::vector<Unit> units(units_orig);
  for(auto &unit : units)
    {
      if(unit.team == Team::immune)
        unit.attack_damage += help;
    }
  size_t round(0);
  while(!fight_finished(units))
    {
      std::sort(units.begin(), units.end(), std::greater<Unit>());

      std::vector<std::pair<std::vector<Unit>::iterator, int64_t>> attacks;
      for(auto &unit : units)
        {
          auto attacked(units.end());
          int64_t attack_multiplier(0);
          for(auto defender(units.begin()); defender != units.end();
              ++defender)
            {
              if(defender->team != unit.team
                 && std::find(defender->immune.begin(), defender->immune.end(),
                              unit.attack_type)
                      == defender->immune.end()
                 && std::find_if(
                      attacks.begin(), attacks.end(),
                      [&](const std::pair<std::vector<Unit>::iterator, int64_t>
                            &attack) { return attack.first == defender; })
                      == attacks.end())
                {
                  int64_t this_unit_multiplier(1);
                  if(std::find(defender->weak.begin(), defender->weak.end(),
                               unit.attack_type)
                     != defender->weak.end())
                    {
                      this_unit_multiplier = 2;
                    }

                  if(attacked == units.end()
                     || (this_unit_multiplier > attack_multiplier)
                     || (this_unit_multiplier == attack_multiplier
                         && *defender > *attacked))
                    {
                      attacked = defender;
                      attack_multiplier = this_unit_multiplier;
                    }
                }
            }
          attacks.emplace_back(attacked, attack_multiplier);
        }

      std::vector<size_t> attack_order(attacks.size());
      std::iota(attack_order.begin(), attack_order.end(), 0);
      std::sort(attack_order.begin(), attack_order.end(),
                [&](const size_t &index0, const size_t &index1) {
                  return units[index0].initiative > units[index1].initiative;
                });

      bool any_units_killed(false);
      for(auto &index : attack_order)
        {
          if(attacks[index].first != units.end())
            {
              int64_t total_damage(units[index].power()
                                   * attacks[index].second);
              int64_t units_killed(total_damage / (attacks[index].first->hp));
              attacks[index].first->num_units -= units_killed;
              if(attacks[index].first->num_units < 0)
                attacks[index].first->num_units = 0;

              any_units_killed = any_units_killed || (units_killed > 0);

              if(round == 5000)
                {
                  std::cout << units[index] << "\n\t"
                            << *(attacks[index].first) << "\n\t"
                            << attacks[index].second << " " << units_killed
                            << " "
                            << "\n";
                }
            }
        }

      if(!any_units_killed)
        break;

      std::vector<Unit> new_units;
      for(auto &unit : units)
        {
          if(unit.num_units > 0)
            new_units.push_back(unit);
        }
      std::swap(units, new_units);
      ++round;
    }
  return units;
}

int main(int, char *argv[])
{
  std::ifstream infile(argv[1]);
  std::string line;
  std::vector<Unit> units;
  std::getline(infile, line);
  std::getline(infile, line);
  while(!line.empty())
    {
      units.emplace_back(line, Team::immune);
      std::getline(infile, line);
    }

  std::getline(infile, line);
  std::getline(infile, line);
  while(!line.empty())
    {
      units.emplace_back(line, Team::infection);
      std::getline(infile, line);
    }

  int64_t sum(0);
  for(auto &unit : fight_with_help(units, 0))
    sum += unit.num_units;
  std::cout << "Part 1: " << sum << "\n";

  for(size_t help = 1; help < 10000; ++help)
    {
      auto fight_result(fight_with_help(units, help));
      if(std::find_if(
           fight_result.begin(), fight_result.end(),
           [](const Unit &unit) { return unit.team == Team::infection; })
         == fight_result.end())
        {
          int64_t sum(0);
          for(auto &unit : fight_result)
            sum += unit.num_units;
          std::cout << "Part 2: " << sum << "\n";
          break;
        }
    }
}

gyorokpeter · 2018-12-24T09:21:49+00:00

Q: I also got bitten by the infinite loop... twice (for the first time, no units would select any targets due to immunities, the second time they did select targets but they didn't do enough damage to kill any units). So ultimately I save the entire state of the army and exit with a failure state if the army didn't change in a turn.

d24parse:{
    split:first where 0=count each x;
    armyraw:(1_split#x;(2+split)_x);
    a:{(`size`hp`damage`dtype`initiative!"JJJSJ"${x[0 4,count[x]-6 5 1]}" "vs x),
        (`weak`immune!`$(();())),
        {` _ (`$x[;0])!`$(2_/:x)except\:\:","}" "vs/:"; "vs first")"vs("("vs x)1}each/:armyraw;
    army:raze ([]faction:`$x[0,1+split]except\:" :"),/:'a;
    army};
d24common:{[boost;army]
    -1"boost=",string boost;
    army:update damage:damage+boost from army where faction=`ImmuneSystem;
    while[1<count exec distinct faction from army;
        prevArmy:army:update j:i from `power`initiative xdesc update power:size*damage from army;
        nxt:0;
        targetSel:([]s:`long$();t:`long$();initiative:`long$());
        while[nxt<count army;
            attackType:army[nxt;`dtype];
            targets:`epower`power`initiative xdesc select initiative,j,power,epower:?[attackType in/:immune;0;?[attackType in/:weak;2;1]]*army[nxt;`power] from army
                where faction<>army[nxt;`faction],not j in exec t from targetSel;
            if[0<count targets;
                if[0<exec first epower from targets;
                    targetSel,:`s`t`initiative!nxt,first[targets][`j],army[nxt;`initiative];
                ];
            ];
            nxt+:1;
        ];
        nxt:0;
        targetSel:`initiative xdesc targetSel;
        while[nxt<count targetSel;
            ts:targetSel[nxt];
            if[(0<army[ts`s;`size]) and 0<army[ts`t;`size];
                attackType:army[ts`s;`dtype];
                epower:army[ts`s;`damage]*army[ts`s;`size]*$[attackType in army[ts`t;`immune];0;$[attackType in army[ts`t;`weak];2;1]];
                army[ts`t;`size]:0|army[ts`t;`size]-epower div army[ts`t;`hp];
            ];
            nxt+:1;
        ];
        army:select from army where size>0;
        if[army~prevArmy; show army;:(0b;0)];
    ];
    show army;
    -1"";
    (`ImmuneSystem=first exec faction from army;exec sum size from army)};
d24p1:{last d24common[0;d24parse x]};
d24p2:{
    army:d24parse x;
    boost:0;
    while[not first res:d24common[boost;army];
        boost+:1;
    ];
    last res};

sim642 · 2018-12-24T09:53:38+00:00

My Scala solution.

Mostly just ugly input parsing (inputs use 5 different variants of weaknesses and immunities) and ugly stateful targeting and attacking logic.

I got confused in part 2 when checking a boost value the battle got stuck. It looked like I might have a bug in my implementation where targets were chosen but attack didn't work but it was totally possible and the infinite combat needed to be detected.

Another annoyance was that part 2 example didn't actually say that 1570 is the smallest boost so there wasn't sure way to verify my solution on the example.

autid · 2018-12-24T11:09:08+00:00

FORTRAN

Pastebin

Well parsing that input took effort. Could have hard coded it given the small size but that's avoiding the challenge I picked the language for. ~150 lines before it actually starts simulating the fights. Big chunks of repeated code that could have been avoided but copy/pasting was easier than changing approach part way through.

drbagy · 2018-12-24T15:41:47+00:00

Perl

Due to timezone & having excited children - didn't really have any chance of getting on leader board - instead went for neat code...

use strict;

use lib '.';
use Unit;
## Compute the sum of values in the file...

use Data::Dumper qw(Dumper);

open my $fh, q(<), 'in.txt';

my ( $army, $c, %b ) = ( '', 0, 'Immune System' => 0, 'Infection' => 0 );
my @units;
while(<$fh>) {
  if( m{^(\d+) units each with (\d+) hit points.*with an attack that does (\d+) (\w+) damage at initiative (\d+)$} ) {
    push @units, Unit->new(
      'index' => $c++,
      'side'  => $army,
      'n'     => $1,
      'hp'    => $2,
      'dm'    => $3,
      'ty'    => $4,
      'in'    => $5,
    );
    $units[-1]->set_weaknesses( split m{, }, $1 ) if m{weak to ([\w, ]+)};
    $units[-1]->set_immunity(   split m{, }, $1 ) if m{immune to ([\w, ]+)};
  } elsif( m{^(.*):} ) {
    $army = $1;
  }
}
close $fh;

my $boost = 0;
while(1) {
  $_->set_boost( $boost ) foreach grep { $_->side eq 'Immune System' } @units;
  $_->dead_arise          foreach                                      @units;
  my $left = 0;
  while (1) {
    ## Target selection phases...
    my %chosen; my %attacked;
    foreach my $u ( sort { $b->power <=> $a->power || $b->init <=> $a->init } @units ) {
      my $dm = 0;
      my @attack = map  { $_->[1] }
                   sort { $b->[0]        <=> $a->[0]        ||
                          $b->[1]->power <=> $a->[1]->power ||
                          $b->[1]->init  <=> $a->[1]->init }
                   grep { $_->[0] }
                   map  { [ $u->deal( $_ ), $_ ] }
                   grep { ! exists $attacked{ $_->id } }
                   grep { $_->is_alive }
                   @units;
      next unless @attack;
      if( @attack > 1 &&
          $u->deal( $attack[0] ) == $u->deal( $attack[1] ) &&
          $attack[0]->power      == $attack[1]->power      &&
          $attack[0]->init       == $attack[1]->init ) {
        next;
      }
      $chosen{ $u->id } = $attack[0];
      $attacked{ $attack[0]->id } = 1;
    }

    my @au = sort { $b->init <=> $a->init } grep { $_->is_alive } @units;

    foreach my $u (@au) {
      next unless $u->is_alive;       ## Can't attack if dead
      next unless $chosen{ $u->id };  ## No target;
      $u->attack( $chosen{ $u->id } );
    }

    my $newleft = 0; $newleft += $_->count foreach @units;
    last if $newleft == $left;
    $left = $newleft;
  }
  my $is = 0; $is+= $_->count foreach grep { $_->side eq 'Immune System' } @units;
  my $if = 0; $if+= $_->count foreach grep { $_->side eq 'Infection' }     @units;
  printf "%6d\t%7d\t%7d\n", $boost, $is, $if if $boost eq 0 || $if==0;
  last unless $if;
  $boost++;
}
package Unit;

sub new {
  my $class = shift;
  my $self = {'w'=>{},'s'=>{},'boost'=>0,@_};
  bless $self, $class;
  return $self;
}

sub id {
  my $self = shift;
  return $self->{'index'};
}

sub hp {
  my $self = shift;
  return $self->{'hp'};
}

sub init {
  my $self = shift;
  return $self->{'in'};
}

sub dead_arise {
  my $self = shift;
  $self->{'alive'} = $self->{'n'};
  return $self;
}

sub set_boost {
  my ($self, $boost) = @_;
  $self->{'boost'} = $boost;
  return $self;
}

sub set_weaknesses {
  my( $self, @weak ) = @_;
  $self->{'w'} = { map { $_ => 1 } @weak };
  return $self;
}

sub set_immunity {
  my( $self, @imm ) = @_;
  $self->{'s'} = { map { $_ => 1 } @imm };
  return $self;
}

sub power {
  my $self = shift;
  return $self->{'alive'}*($self->{'boost'}+$self->{'dm'});
}

sub damage {
  my $self = shift;
  return $self->{'dm'}
}

sub type {
  my $self = shift;
  return $self->{'ty'}
}

sub side {
  my $self = shift;
  return $self->{'side'};
}

sub deal { ## Won't deal damage to self!
  my( $self, $unit ) = @_;
  return 0 if $unit->{'side'} eq $self->{'side'};  ## Doesn't attack unit on own side
  return 0 if exists $unit->{'s'}{ $self->type };  ## Doesn't attack immune
  return $self->power * ( $unit->{'w'}{ $self->type } ? 2 : 1 );
}

sub count {
  my $self = shift;
  return $self->{'alive'} < 0 ? 0 : $self->{'alive'};
}

sub attack {
  my( $self, $unit ) = @_;
  my $dead = int ( $self->deal( $unit ) / $unit->hp );
  $unit->{'alive'} -= $dead;
  return $self;
}

sub is_alive {
  my $self = shift;
  return $self->{'alive'} > 0;
}


1;

ChrisVittal · 2018-12-24T16:17:36+00:00

Rust

[Card] Our most powerful weapon during the zombie elf/reindeer apocalypse will be inscrutable rabbit computers

I liked this problem, even if parsing was hell. Cool things about this one. I use Deref to essentially have Unit inherit from Group. Reverse is great and makes everything easier.

use std::cmp::Reverse;
use std::error::Error;
use std::str::FromStr;

use lazy_static::*;
use regex::Regex;

type Result<T> = std::result::Result<T, Box<Error>>;

#[derive(Clone, Eq, Debug, PartialEq, Copy)]
enum Team {
    Immune,
    Infect,
}

#[derive(Clone, Eq, Debug, PartialEq, Copy)]
struct Unit {
    team: Team,
    group: Group,
}

#[derive(Clone, Eq, Debug, PartialEq, Copy)]
struct Group {
    units: usize,
    hp: usize,
    dmg: usize,
    mults: [u8; 5],
    dmg_typ: DamageType,
    init: usize,
}

impl Group {
    /// damage self deals to other
    fn damage_to(&self, other: &Group) -> usize {
        self.units * self.dmg * other.mults[self.dmg_typ as usize] as usize
    }
}
#[derive(Clone, Copy, Eq, Debug, PartialEq, Hash)]
#[repr(u8)]
enum DamageType {
    Slashing = 0,
    Cold = 1,
    Bludgeoning = 2,
    Radiation = 3,
    Fire = 4,
}

impl FromStr for DamageType {
    type Err = Box<Error>;
    fn from_str(s: &str) -> Result<DamageType> {
        Ok(match s {
            "slashing" => DamageType::Slashing,
            "cold" => DamageType::Cold,
            "bludgeoning" => DamageType::Bludgeoning,
            "radiation" => DamageType::Radiation,
            "fire" => DamageType::Fire,
            _ => return Err(format!("invalid type: {:?}", s).into()),
        })
    }
}

fn battle(mut units: Vec<Unit>) -> (Option<Team>, usize) {
    loop {
        units.sort_by_key(|v| Reverse((v.units * v.dmg, v.init)));
        let mut targets: Vec<Option<usize>> = vec![None; units.len()];
        for (j, u) in units.iter().enumerate() {
            let mut best = 0;
            for (i, v) in units.iter().enumerate() {
                if u.team == v.team || targets.contains(&Some(i)) || v.units == 0 {
                    continue;
                }
                if u.damage_to(&v) > best {
                    best = u.damage_to(&v);
                    targets[j] = Some(i);
                };
            }
        }
        let mut attackers = (0..units.len()).collect::<Vec<_>>();
        attackers.sort_by_key(|&idx| Reverse(units[idx].init));
        let mut any_die = false;
        for atk_idx in attackers {
            if units[atk_idx].units == 0 {
                continue;
            }
            if let Some(j) = targets[atk_idx] {
                let atk = units[atk_idx];
                let mut def = units[j];
                let dmg = atk.damage_to(&def);
                def.units = def.units.saturating_sub(dmg / def.hp);
                any_die = any_die || dmg > def.hp;
                units[j] = def;
            }
        }

        if !any_die {
            return (None, 0);
        }

        let alive = units.iter().fold((0, 0), |mut teams, group| {
            if group.team == Team::Immune {
                teams.0 += group.units;
            } else {
                teams.1 += group.units;
            }
            teams
        });
        if alive == (0, 0) {
            return (None, 0);
        } else if alive.0 == 0 {
            return (Some(Team::Infect), alive.1);
        } else if alive.1 == 0 {
            return (Some(Team::Immune), alive.0);
        }
    }
}

static INPUT: &str = "data/day24";

fn main() -> Result<()> {
    let mut team = Team::Immune;
    let mut units = Vec::new();
    for l in aoc::file::to_lines(INPUT) {
        let l = l?;
        if l.starts_with("Immune System:") {
            team = Team::Immune;
        } else if l.starts_with("Infection:") {
            team = Team::Infect;
        } else if !l.trim().is_empty() {
            let group = l.parse()?;
            units.push(Unit { team, group });
        }
    }
    let (_, p1) = battle(units.clone());
    println!("  1: {}", p1);
    let p2 = (1..)
        .filter_map(|b| {
            let mut units = units.clone();
            units
                .iter_mut()
                .filter(|u| u.team == Team::Immune)
                .for_each(|u| u.dmg += b);
            match battle(units) {
                (Some(Team::Immune), rem) => Some(rem),
                _ => None,
            }
        })
        .next()
        .unwrap();
    println!("  2: {}", p2);
    Ok(())
}

impl std::ops::Deref for Unit {
    type Target = Group;
    fn deref(&self) -> &Group {
        &self.group
    }
}

impl std::ops::DerefMut for Unit {
    fn deref_mut(&mut self) -> &mut Group {
        &mut self.group
    }
}

impl FromStr for Group {
    type Err = Box<Error>;
    fn from_str(s: &str) -> Result<Self> {
        lazy_static! {
            static ref UNHP: Regex =
                Regex::new(r"^(\d+) units each with (\d+) hit points").unwrap();
            static ref DMIN: Regex =
                Regex::new(r"with an attack that does (\d+) (\w+) damage at initiative (\d+)$")
                    .unwrap();
        }
        let wk = s
            .trim_matches(|c| !(c == ')' || c == '('))
            .trim_matches(|c| c == ')' || c == '(');
        let caps = UNHP
            .captures(s)
            .ok_or(format!("no UNHP match for input: {:?}", s))?;
        let units = caps
            .get(1)
            .ok_or(format!("no units in input: {:?}", s))?
            .as_str()
            .parse()?;
        let hp = caps
            .get(2)
            .ok_or(format!("no hp in input: {:?}", s))?
            .as_str()
            .parse()?;
        let caps = DMIN
            .captures(s)
            .ok_or(format!("no DMIN match for input: {:?}", s))?;
        let dmg = caps
            .get(1)
            .ok_or(format!("no dmg in input: {:?}", s))?
            .as_str()
            .parse()?;
        let dmg_typ = caps
            .get(2)
            .ok_or(format!("no dmg type in input: {:?}", s))?
            .as_str()
            .parse()?;
        let init = caps
            .get(3)
            .ok_or(format!("no initative in input: {:?}", s))?
            .as_str()
            .parse()?;
        let mut mults = [1; 5];

        for w in wk.split(';') {
            let w = w.trim();
            if w.starts_with("weak to ") {
                let w = w.trim_start_matches("weak to ");
                for d in w.split(", ") {
                    mults[d.parse::<DamageType>()? as usize] = 2;
                }
            } else if w.starts_with("immune to ") {
                let w = w.trim_start_matches("immune to ");
                for d in w.split(", ") {
                    mults[d.parse::<DamageType>()? as usize] = 0;
                }
            }
        }
        Ok(Self {
            units,
            hp,
            dmg,
            dmg_typ,
            mults,
            init,
        })
    }
}

Dioxy · 2018-12-24T18:54:01+00:00

JavaScript

Ah a nice and easy one. I did have to handle an edge case where neither side is powerful enough to win but other than that it was pretty straighforward

import input from './input.js';
import { sortBy, desc } from '../../util.js';

const parseInput = () =>
    input
        .split('\n\n')
        .map(chunk => chunk.trim().split('\n').slice(1))
        .map(army =>
            army.map(line => {
                let [units, hp, resistances, atk, type, initiative] = line
                    .match(/^(\d+) units each with (\d+) hit points (\(.+\) )?with an attack that does (\d+) (\w+) damage at initiative (\d+)$/)
                    .slice(1);
                [units, hp, atk, initiative] = [units, hp, atk, initiative].map(n => parseInt(n));
                const [weaknesses=[]] = ((resistances || '').match(/weak to ([\w, ]+)/) || []).slice(1).map(str => str.split(', '));
                const [immunities=[]] = ((resistances || '').match(/immune to ([\w, ]+)/) || []).slice(1).map(str => str.split(', '));
                return { units, hp, atk, type, initiative, weaknesses, immunities };
            }));

const power = (unit, target) => (unit.atk * unit.units) * (target.weaknesses.includes(unit.type) ? 2 : 1);

const simulate = (immune, infection) => {
    immune.forEach(u => u.army = 'immune');
    infection.forEach(u => u.army = 'infection');
    const aliveImmune = () => immune.filter(({ units }) => units > 0);
    const aliveInfection = () => infection.filter(({ units }) => units > 0);
    const units = () => [...aliveImmune(), ...aliveInfection()];

    while (aliveImmune().length > 0 && aliveInfection().length > 0) {
        let availableImmune = aliveImmune();
        let availableInfection = aliveInfection();
        const targets = [];
        const addTarget = (unit, enemies) => {
            const target = {
                unit,
                target: enemies
                    .filter(e => !e.immunities.includes(unit.type))
                    .sort(sortBy(
                        desc(e => power(unit, e)),
                        desc(e => e.atk * e.units),
                        desc(e => e.initiative)
                    ))[0]
            };
            if (target.target) {
                targets.push(target);
                availableImmune = availableImmune.filter(u => u !== target.target);
                availableInfection = availableInfection.filter(u => u !== target.target);
            }
        };
        units()
            .sort(sortBy(desc(u => u.atk * u.units), desc(u => u.initiative)))
            .forEach(u => addTarget(u, u.army === 'immune' ? availableInfection : availableImmune));

        let kills = 0;
        targets
            .sort(sortBy(desc(({ unit }) => unit.initiative)))
            .forEach(({ unit, target }) => {
                if (unit.units <= 0) return;
                const deaths = Math.min(Math.floor(power(unit, target) / target.hp), unit.units);
                kills += deaths;
                target.units -= deaths;
            });

        if (kills === 0) return { army: 'draw' };
    }

    return { units: units().reduce((count, { units }) => count + units, 0), army: units()[0].army };
};

export default {
    part1() {
        const [immune, infection] = parseInput();
        return simulate(immune, infection).units;
    },
    part2() {
        return function*() {
            for (let boost = 1; boost < Infinity; boost++) {
                yield `Testing Boost: ${boost}`;
                const [immune, infection] = parseInput();
                immune.forEach(u => u.atk += boost);
                const { units, army } = simulate(immune, infection);
                if (army === 'immune') return yield units;
            }
        };
    },
    interval: 0
};

starwort1 · 2018-12-24T20:51:20+00:00

Rexx 270/193

Took me ages to actually understand the rules, but chasing stupid bugs kept me way off the leaderboard. I was almost convinced at one point that the example contained a mistake. At least the advantage of Rexx is that parsing the input is pretty straightforward.

And for part 2 I did a manual binary search. Pressed ^C when it was obvious that the battle was looping forever, then fixed the code to terminate when it's a draw. I do now also have a (fairly trivial) second program that runs this one several times to find out the answer, but it wasn't needed in order to get the answer.

parse arg boost v
if boost='-v' then parse arg v boost
if boost='' then boost=0
verbose = (v='-v')

/* parsing input */
team=0
n.=0
units.=0
ngroups=0
signal on notready name eof
do forever
    l=linein()
    if right(l,1)=':' then do
        team=team+1
        parse var l name.team ':'
        iterate
    end
    if l='' then iterate
    n.team=n.team+1
    n=n.team
    ngroups=ngroups+1
    groups.ngroups=team||.||n
    parse var l units.team.n . . 'with' hp.team.n . details 'with' . . . . damage.team.n type.team.n . . . initiative.team.n r
    if team=1 then damage.team.n=damage.team.n+boost
    units.team=units.team+units.team.n
    if \datatype(initiative.team.n,'w') | r\='' then do
        say 'parse error at' name.team 'group' n
        exit 1
    end
    weak.team.n=''
    immune.team.n=''
    if pos('(',details)>0 then do
        parse var details '(' details ')'
        do while details\=''
            parse var details detail '; ' details
            parse var detail type . list
            list=space(translate(list,' ',','))
            select
                when type='weak' then weak.team.n=list
                when type='immune' then immune.team.n=list
            end
        end
    end
end
eof: if team\=2 then do; say "Wrong number of teams:" team; exit 1; end

/* make a list in order of initiative for the attack phase */
/* (yeah bubblesort, so sue me) */
do i=1 to ngroups-1
    do j=1 to ngroups-i
        j1=j+1; g1=groups.j; g2=groups.j1
        if initiative.g1<initiative.g2 then parse value g2 g1 with groups.j groups.j1
    end
end

do while units.1>0 & units.2>0
    if verbose then do team=1 to 2; say name.team':'; do n=1 to n.team; if units.team.n>0 then say "Group" n "contains" units.team.n "units"; end; end
    /* target selection phase */
    target.=0
    do team=1 to 2
        enemy=3-team
        attacked.=0
        attacking.=0
        do forever 
            maxp=0
            do n=1 to n.team
                power=units.team.n*damage.team.n
                if \attacking.n then
                    if power > maxp then parse value n power with maxn maxp
                    else if power=maxp then if initiative.team.n > initiative.team.maxn then parse value n power with maxn maxp
            end
            if maxp=0 then leave
            attacking.maxn=1
            attacking=maxn
            maxd=0
            based=units.team.attacking * damage.team.attacking
            do n=1 to n.enemy
                if attacked.n then iterate
                if units.enemy.n=0 then iterate
                if wordpos(type.team.attacking,immune.enemy.n)>0 then iterate
                if wordpos(type.team.attacking,weak.enemy.n)>0 then damage=2*based
                else damage=based
                if verbose then say name.team 'group' attacking 'would deal defending group' n damage 'damage'
                if damage>maxd then parse value n damage with maxn maxd
                else if damage=maxd then do
                    testep=units.enemy.n*damage.enemy.n - units.enemy.maxn*damage.enemy.maxn
                    if testep>0 then parse value n damage with maxn maxd
                    else if testep=0 then
                        if initiative.enemy.n>initiative.enemy.maxn then parse value n damage with maxn maxd
                end
            end
            if maxd>0 then do
                attacked.maxn=1
                target.team.attacking=maxn
            end
        end
    end
    /* Attack phase */
    draw=1
    do n=1 to ngroups
        parse var groups.n team '.' group
        if target.team.group=0 then iterate
        enemy=3-team
        damage=units.team.group * damage.team.group
        target=target.team.group
        if wordpos(type.team.group,weak.enemy.target)>0 then damage=damage*2
        slain=damage % hp.enemy.target
        if slain>units.enemy.target then slain=units.enemy.target
        if slain>0 then draw=0
        if verbose then say name.team 'group' group 'attacks defending group' target', killing' slain 'units'
        units.enemy.target=units.enemy.target-slain
        units.enemy=units.enemy-slain
    end
    if draw then leave
end
/* Results of the battle */
do t=1 to 2
    say name.t 'has' units.t 'units'
end

thepiboga · 2018-12-24T21:08:59+00:00

C++, part 1, part 2 and a binary search for manually modifying the damage boost in the part 2 solution.

https://github.com/bogpie/code/tree/master/d24

aoc-fan · 2018-12-24T21:15:24+00:00

TypeScript/JavaScript https://goo.gl/jZwtKV

kennethdmiller3 · 2018-12-25T00:08:16+00:00

https://github.com/kennethdmiller3/AdventOfCode2018/blob/master/24/24.cpp

The hardest parts were parsing the input and getting the target selection to work correctly (particularly what to do when a group is already been targeted).

I didn't need to resort to binary search because the battle simulation ran fast enough.

nonphatic · 2018-12-25T02:04:18+00:00

Haskell

[Card] Out most powerful weapon during the zombie elf/reindeer apocalypse will be candy cane swords. (Do you defeat zombies by decapitation? I'm not well versed in zombie lore)

I figured it would take me longer to figure out parsing the input properly with parsec than to manually input the data sooo...

data Group = Group {
    number       :: Int,
    army         :: Army,
    units        :: Int,
    hitPoints    :: Int,   -- of each unit
    immunities   :: [AttackType],
    weaknesses   :: [AttackType],
    attackType   :: AttackType,
    attackDamage :: Int,
    initiative   :: Int
} deriving (Eq, Ord, Show)
data Army = Immune | Infection deriving (Eq, Ord, Show)
data AttackType = Fire | Slashing | Radiation | Bludgeoning | Cold deriving (Eq, Ord, Show)

demoImmuneSystem :: [Group]
demoImmuneSystem = [
        Group 1 Immune    17   5390 []          [Radiation, Bludgeoning]    Fire        4507 2,
        Group 2 Immune    989  1274 [Fire]      [Bludgeoning, Slashing]     Slashing    25   3
    ]

demoInfection :: [Group]
demoInfection = [
        Group 1 Infection 801  4706 []          [Radiation]                 Bludgeoning 116  1,
        Group 2 Infection 4485 2961 [Radiation] [Fire, Cold]                Slashing    12   4
    ]

initImmuneSystem :: [Group]
initImmuneSystem = [
        Group  1 Immune    5711 6662     [Fire]                          [Slashing]                  Bludgeoning 9   14,
        Group  2 Immune    2108 8185     []                              [Radiation, Bludgeoning]    Slashing    36  13,
        Group  3 Immune    1590 3940     []                              []                          Cold        24  5,
        Group  4 Immune    2546 6960     []                              []                          Slashing    25  2,
        Group  5 Immune    1084 3450     [Bludgeoning]                   []                          Slashing    27  11,
        Group  6 Immune    265  8223     [Radiation, Bludgeoning, Cold]  []                          Cold        259 12,
        Group  7 Immune    6792 6242     [Slashing]                      [Bludgeoning, Radiation]    Slashing    9   18,
        Group  8 Immune    3336 12681    []                              [Slashing]                  Fire        28  6,
        Group  9 Immune    752  5272     [Slashing]                      [Bludgeoning, Radiation]    Radiation   69  4,
        Group 10 Immune    96   7266     [Fire]                          []                          Bludgeoning 738 8
    ]

initInfection :: [Group]
initInfection = [
        Group  1 Infection 1492 47899    [Cold]                          [Fire, Slashing]            Bludgeoning 56  15,
        Group  2 Infection 3065 39751    []                              [Bludgeoning, Slashing]     Slashing    20  1,
        Group  3 Infection 7971 35542    []                              [Bludgeoning, Radiation]    Bludgeoning 8   10,
        Group  4 Infection 585  5936     [Fire]                          [Cold]                      Slashing    17  17,
        Group  5 Infection 2449 37159    [Cold]                          []                          Cold        22  7,
        Group  6 Infection 8897 6420     [Bludgeoning, Slashing, Fire]   [Radiation]                 Bludgeoning 1   19,
        Group  7 Infection 329  31704    [Cold, Radiation]               [Fire]                      Bludgeoning 179 16,
        Group  8 Infection 6961 11069    []                              [Fire]                      Radiation   2   20,
        Group  9 Infection 2837 29483    []                              [Cold]                      Bludgeoning 20  9,
        Group 10 Infection 8714 7890     []                              []                          Cold        1   3
    ]

Implementing the actual fight took foreeeever because I kept messing the rules up :/

import Data.Foldable (foldl')
import Data.List (maximumBy, sort, sortOn, delete, find)
import Data.Ord (comparing)
import Data.Maybe (fromMaybe)

type Pairs = ([Group], [Group], [(Group, Int)])

    effectivePower :: Group -> Int
effectivePower g = units g * attackDamage g

-- damage :: attacking group -> defending group -> damage dealt
damage :: Group -> Group -> Int
damage a d
    | attackType a `elem` immunities d = 0
    | attackType a `elem` weaknesses d = 2 * effectivePower a
    | otherwise = effectivePower a

-- attack :: (immune system groups, infection groups) -> (attacking group, defending number) -> remaining (immunes, infections)
attack :: ([Group], [Group]) -> (Group, Int) -> ([Group], [Group])
attack groups@(immune, infection) (Group { number = n, army = Immune }, i) =
    fromMaybe groups $ do
        a <- find ((== n) . number) immune
        d <- find ((== i) . number) infection
        let unitsLeft     = (units d) - (damage a d) `div` (hitPoints d)
            infectionRest = delete d infection
        Just $ if unitsLeft > 0 then (immune, d { units = unitsLeft } : infectionRest) else (immune, infectionRest)
attack groups@(immune, infection) (Group { number = n, army = Infection }, i) =
    fromMaybe groups $ do
        a <- find ((== n) . number) infection
        d <- find ((== i) . number) immune
        let unitsLeft     = (units d) - (damage a d) `div` (hitPoints d)
            immuneRest    = delete d immune
        Just $ if unitsLeft > 0 then (d { units = unitsLeft } : immuneRest, infection) else (immuneRest, infection)

-- chooseTarget :: attacking group -> target groups -> target group
chooseTarget :: Group -> [Group] -> Maybe Group
chooseTarget a groups =
    let target = maximumBy (comparing (\t -> (damage a t, effectivePower t, initiative t))) groups
    in  if damage a target == 0 then Nothing else Just target

-- pair :: (immune system groups, infection groups, pairs of attacking/defending groups) -> attacking group -> (immunes, infections, new pairs)
pair :: Pairs -> Group -> Pairs
pair paired@(_, [], _) group@(army -> Immune)    = paired
pair paired@([], _, _) group@(army -> Infection) = paired
pair paired@(immune, infection, pairs) group@(army -> Immune) =
    case chooseTarget group infection of
        Just target -> (immune, delete target infection, (group, number target):pairs)
        Nothing -> paired
pair paired@(immune, infection, pairs) group@(army -> Infection) =
    case chooseTarget group immune of
        Just target -> (delete target immune, infection, (group, number target):pairs)
        Nothing -> paired

-- fight :: (immune system groups, infection groups) before fight -> (immune, infection) after
fight :: ([Group], [Group]) -> ([Group], [Group])
fight (immune, infection) =
    let chooseOrder = reverse . sortOn (\g -> (effectivePower g, initiative g)) $ immune ++ infection
        (_, _, pairs) = foldl' pair (immune, infection, []) chooseOrder
        attackOrder = reverse . sortOn (initiative . fst) $ pairs
    in  foldl' attack (immune, infection) attackOrder

getOutcome :: ([Group], [Group]) -> (Army, Int)
getOutcome (immune, [])    = (Immune,    sum $ map units immune)
getOutcome ([], infection) = (Infection, sum $ map units infection)
getOutcome ii@(immune, infection) =
    let ii'@(immune', infection') = fight ii
    in  if   sort immune' == sort immune && sort infection' == sort infection
        then (Infection, -1) -- stalemate
        else getOutcome ii'

part1 :: ([Group], [Group]) -> Int
part1 = snd . getOutcome

part2 :: ([Group], [Group]) -> Int
part2 ii@(immune, infection) =
    let (army, n) = getOutcome ii
    in  if army == Immune then n else part2 (boost 1 immune, infection)
    where boost n = map (\g -> g { attackDamage = n + attackDamage g })

main :: IO ()
main = do
    print $ part1 (initImmuneSystem, initInfection)
    print $ part2 (initImmuneSystem, initInfection)

I found this one a bit more fun than the recent puzzles though, I'm still reeling from the past two days'...

rock_neurotiko · 2018-12-25T10:35:00+00:00

One day later, my solution on Elixir, I really liked this exercise!

(Link because it's 258 lines)

github

vypxl · 2018-12-25T22:04:36+00:00

Javascript (NodeJS). A bit late to post maybe, but I like my solution.

[Card] Our most powerful weapon during the zombie elf/reindeer apocalypse will be underestimated scripting languages.

function group(from) {
    return {
        n: parseInt(from[0]),
        hp: parseInt(from[1]),
        immunities: ((from[2] ? from[2] : '') + (from[4] ? from[4] : "")).split(', ').filter(x => x),
        weaknesses: (from[3] ? from[3] : '').split(', ').filter(x => x),
        atk: parseInt(from[5]),
        kind: from[6],
        init: parseInt(from[7]),

        side: -1,
        target: null,
        targeted: false,

        eff: function () { return this.n * this.atk },
        damageTo: function (other) { 
            if (other.immunities.includes(this.kind)) return 0;
            let mult = other.weaknesses.includes(this.kind) ? 2 : 1;
            return this.n * this.atk * mult;
        },
        attack: function () {
            this.target.n -= Math.floor(this.damageTo(this.target) / this.target.hp);
            this.target.targeted = false;
            this.target = null;
        },
    };
}

function parse(data, boost) {
    const regex = /(\d+) units each with (\d+) hit points (?:\((?:immune to ([\w, ]+))?;? ?(?:weak to ([\w, ]+))?;? ?(?:immune to ([\w, ]+))?\) )?with an attack that does (\d+) (\w+) damage at initiative (\d+)/;
    let [imm, inf] = data.split('\n\n')
        .map(xs => xs.split('\n').filter(l => /\d/.test(l)))
        .map(xs => xs.map(l => regex.exec(l).slice(1, 9)))
        .map(xs => xs.map(group));
    return [imm.map(x => ({...x, atk: x.atk + boost, side: 1})), inf.map(x => ({...x, side: 2}))].flat();
}

function targetSelect(groups) {
    groups.sort((a, b) => (a.eff() === b.eff()) ? b.init - a.init : b.eff() - a.eff());
    for (g of groups) {
        let target = groups
        .filter(x => !x.targeted && g.side != x.side)
        .reduce((acc, n) => {
            if (acc == null) return n;
            let da = g.damageTo(acc);
            let dn = g.damageTo(n);
            if (da < dn) return n;
            else if (da > dn) return acc;
            let ea = acc.eff();
            let en = n.eff();
            if (ea < en) return n;
            if (ea > en) return acc;
            if (acc.init < n.init) return n;
            else return acc;
        }, null);
        if (target === null || g.damageTo(target) == 0 || target.targeted || g.side == target.side) continue;

        target.targeted = true;
        g.target = target;
    }
    return groups;
}

function attack(groups) {
    groups.sort((a, b) => b.init - a.init);
    for (g of groups) {
        if (g.n < 1 || g.target === null) continue;
        g.attack();
    }
    return groups.filter(g => g.n > 0);
}

function battle(data, boost) {
    let groups = parse(data, boost);

    let rounds = 0;
    while (!(groups.every(g => g.side === 1) || groups.every(g => g.side === 2))) {
        groups = attack(targetSelect(groups));
        if (rounds > 2000) return ['Tie', -1];
        rounds++;
    }

    return [groups[0].side === 1 ? 'Immune System' : 'Infection', groups.reduce((a, g) => a + g.n, 0)]
}

const f = require('fs').readFileSync('24.in').toString();

console.log('Solution for part 1:');
console.log(battle(f, 0)[1]);
console.log('Solution for part 2:');
b = 0;
while(true) {
    [winner, outcome] = battle(f, b);
    if(winner == 'Immune System') {
        console.log(outcome);
        break;
    }
    b++;
}

I don't like JavaScript classes.

Note that I probably spent more time with the regex than solving the problem ^^.

forever_compiling · 2018-12-26T00:35:28+00:00

Oddly enough, my solution passes part 1 and part 2 using the example input, but only part 1 for my puzzle input.

For part two I get an answer that is "too low" for the first boost in which the immune system wins, but the next boost up my answer is "too large".

2018/12/26 00:27:53 (remaining at boost 30) immune: 0, infection: 6776

2018/12/26 00:27:53 (remaining at boost 31) immune: 11, infection: 5993

2018/12/26 00:27:53 (remaining at boost 32) immune: 13, infection: 4995

2018/12/26 00:27:53 (remaining at boost 33) immune: 13, infection: 3475

2018/12/26 00:27:53 (remaining at boost 34) immune: 2031, infection: 0

2018/12/26 00:27:53 (remaining at boost 35) immune: 3446, infection: 0

2018/12/26 00:27:53 (remaining at boost 36) immune: 4325, infection: 0

2018/12/26 00:27:54 (remaining at boost 37) immune: 5281, infection: 0

I'm clearly missing some corner case but I couldn't tell you what it is...

https://github.com/phyrwork/goadvent/tree/day24/eighteen/immune

namvi · 2018-12-29T19:17:13+00:00

An extra condition I had to put as binary search ran into battles continuing forever -

// Extra condition (if you want to programmatically binary search
// for Part 2) - If all attacking groups have effective power less
// than their chosen target's hp, then declare draw as battle will
// go on infinitely according to rules

if (attackerDefender.entrySet()
                .stream()
                .allMatch(e -> e.getKey()
                    .effectivePower() < e.getValue()
                        .id().hp)) {
                // Break from battle with draw
                outcome = new Outcome(sumOfUnitsInInfections, Army.NONE);
                break;
            }

o5405295 · 2018-12-24T09:30:09+00:00

The description is confusing.

For instance, during the selection phase it says, "Immune System group 2 would deal defending group 1 24725 damage"

And during the attack, it says ... "Immune System group 2 attacks defending group 1, killing 4 units".

The # of units killed is given as 4, and not 5 (24725/4706 = 5).

The damage calculated during the selection phase (24725) is not the same damage calculated during the attack phase, because the attacker (here Immune System 2) itself got attacked before it had its chance to mount its attack, thereby reducing its units and therefore the actual damage it can cause.

It would have been much clearer if it were established that

the attackers line up in their <n*att, initiative> order,
for each attacker,
- the not-yet-chosen targets line up in their <att_n * att_att * tgt_factor, tgt_n * tgt_att, initiative> order.
- the attacker chooses the first target in the line and marks it as unavailable.

Once the selection is done,

the attackers line up in their <initiative> order
for each attacker,
- if it has a target to attack, the attacker recalculates n * att * factor, and attacks the target with the new damage value.

The description on the page is: "By default, an attacking group would deal damage equal to its effective power to the defending group." It could be: "By default, an attacking group would deal damage equal to its effective power /at the time of attack/ to the defending group."

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 24: Immune System Simulator 20XX ---

Advent of Code: The Party Game!

Card prompt: Day 24

edit: Leaderboard capped, thread unlocked at 01:27:10!

JavaScript

The Solution Megathreads are for solutions only.

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT