From 87ab487d59fa85dbe2afa55cc841b02805ae42ca Mon Sep 17 00:00:00 2001 From: Louis Burda Date: Fri, 7 Apr 2023 17:18:18 -0400 Subject: Reorder days into src --- src/24/input | 23 +++++++ src/24/part1 | 199 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/24/part2 | 186 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/24/solve.py | 127 ++++++++++++++++++++++++++++++++++++ 4 files changed, 535 insertions(+) create mode 100644 src/24/input create mode 100644 src/24/part1 create mode 100644 src/24/part2 create mode 100644 src/24/solve.py (limited to 'src/24') diff --git a/src/24/input b/src/24/input new file mode 100644 index 0000000..969be90 --- /dev/null +++ b/src/24/input @@ -0,0 +1,23 @@ +Immune System: +2728 units each with 5703 hit points (weak to fire) with an attack that does 18 cold damage at initiative 12 +916 units each with 5535 hit points (weak to bludgeoning) with an attack that does 55 slashing damage at initiative 20 +2255 units each with 7442 hit points (weak to radiation) with an attack that does 31 bludgeoning damage at initiative 8 +112 units each with 4951 hit points (immune to cold) with an attack that does 360 fire damage at initiative 9 +7376 units each with 6574 hit points (immune to cold, slashing, fire) with an attack that does 7 bludgeoning damage at initiative 4 +77 units each with 5884 hit points (weak to slashing) with an attack that does 738 radiation damage at initiative 6 +6601 units each with 8652 hit points (weak to fire, cold) with an attack that does 11 fire damage at initiative 19 +3259 units each with 10067 hit points (weak to bludgeoning) with an attack that does 29 cold damage at initiative 13 +2033 units each with 4054 hit points (immune to cold; weak to fire, slashing) with an attack that does 18 slashing damage at initiative 3 +3109 units each with 3593 hit points with an attack that does 9 bludgeoning damage at initiative 11 + +Infection: +1466 units each with 57281 hit points (weak to slashing, fire) with an attack that does 58 slashing damage at initiative 7 +247 units each with 13627 hit points with an attack that does 108 fire damage at initiative 15 +1298 units each with 41570 hit points (immune to fire, bludgeoning) with an attack that does 63 fire damage at initiative 14 +2161 units each with 40187 hit points (weak to fire) with an attack that does 33 slashing damage at initiative 5 +57 units each with 55432 hit points (weak to cold) with an attack that does 1687 radiation damage at initiative 17 +3537 units each with 24220 hit points (weak to cold) with an attack that does 11 fire damage at initiative 10 +339 units each with 44733 hit points (immune to cold, bludgeoning; weak to radiation, fire) with an attack that does 258 cold damage at initiative 18 +1140 units each with 17741 hit points (weak to bludgeoning; immune to fire, slashing) with an attack that does 25 fire damage at initiative 2 +112 units each with 44488 hit points (weak to bludgeoning, radiation; immune to cold) with an attack that does 749 radiation damage at initiative 16 +2918 units each with 36170 hit points (immune to bludgeoning; weak to slashing, cold) with an attack that does 24 radiation damage at initiative 1 diff --git a/src/24/part1 b/src/24/part1 new file mode 100644 index 0000000..80675fb --- /dev/null +++ b/src/24/part1 @@ -0,0 +1,199 @@ +--- Day 24: Immune System Simulator 20XX --- + +After a weird buzzing noise, you appear back at the man's cottage. He seems relieved to see his +friend, but quickly notices that the little reindeer caught some kind of cold while out exploring. + +The portly man explains that this reindeer's immune system isn't similar to regular reindeer immune +systems: + +The immune system and the infection each have an army made up of several groups; each +group consists of one or more identical units. The armies repeatedly fight until only one army has +units remaining. + +Units within a group all have the same hit points (amount of damage a unit can take before it is +destroyed), attack damage (the amount of damage each unit deals), an attack type, an +initiative (higher initiative units attack first and win ties), and sometimes +weaknesses or immunities. Here is an example group: + +18 units each with 729 hit points (weak to fire; immune to cold, slashing) + with an attack that does 8 radiation damage at initiative 10 + +Each group also has an effective power: the number of units in that group multiplied by their attack +damage. The above group has an effective power of 18 * 8 = 144. Groups never have zero or negative +units; instead, the group is removed from combat. + +Each fight consists of two phases: target selection and attacking. + +During the target selection phase, each group attempts to choose one target. In decreasing order of +effective power, groups choose their targets; in a tie, the group with the higher initiative chooses +first. The attacking group chooses to target the group in the enemy army to which it would deal the +most damage (after accounting for weaknesses and immunities, but not accounting for whether the +defending group has enough units to actually receive all of that damage). + +If an attacking group is considering two defending groups to which it would deal equal damage, it +chooses to target the defending group with the largest effective power; if there is still a tie, it +chooses the defending group with the highest initiative. If it cannot deal any defending groups +damage, it does not choose a target. Defending groups can only be chosen as a target by one +attacking group. + +At the end of the target selection phase, each group has selected zero or one groups to attack, and +each group is being attacked by zero or one groups. + +During the attacking phase, each group deals damage to the target it selected, if any. Groups attack +in decreasing order of initiative, regardless of whether they are part of the infection or the +immune system. (If a group contains no units, it cannot attack.) + +The damage an attacking group deals to a defending group depends on the attacking group's attack +type and the defending group's immunities and weaknesses. By default, an attacking group would deal +damage equal to its effective power to the defending group. However, if the defending group is +immune to the attacking group's attack type, the defending group instead takes no damage; if the +defending group is weak to the attacking group's attack type, the defending group instead takes +double damage. + +The defending group only loses whole units from damage; damage is always dealt in such a way that it +kills the most units possible, and any remaining damage to a unit that does not immediately kill it +is ignored. For example, if a defending group contains 10 units with 10 hit points each and receives +75 damage, it loses exactly 7 units and is left with 3 units at full health. + +After the fight is over, if both armies still contain units, a new fight begins; combat only ends +once one army has lost all of its units. + +For example, consider the following armies: + +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 + +If these armies were to enter combat, the following fights, including details during the target +selection and attacking phases, would take place: + +Immune System: +Group 1 contains 17 units +Group 2 contains 989 units +Infection: +Group 1 contains 801 units +Group 2 contains 4485 units + +Infection group 1 would deal defending group 1 185832 damage +Infection group 1 would deal defending group 2 185832 damage +Infection group 2 would deal defending group 2 107640 damage +Immune System group 1 would deal defending group 1 76619 damage +Immune System group 1 would deal defending group 2 153238 damage +Immune System group 2 would deal defending group 1 24725 damage + +Infection group 2 attacks defending group 2, killing 84 units +Immune System group 2 attacks defending group 1, killing 4 units +Immune System group 1 attacks defending group 2, killing 51 units +Infection group 1 attacks defending group 1, killing 17 units + +Immune System: +Group 2 contains 905 units +Infection: +Group 1 contains 797 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 184904 damage +Immune System group 2 would deal defending group 1 22625 damage +Immune System group 2 would deal defending group 2 22625 damage + +Immune System group 2 attacks defending group 1, killing 4 units +Infection group 1 attacks defending group 2, killing 144 units + +Immune System: +Group 2 contains 761 units +Infection: +Group 1 contains 793 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 183976 damage +Immune System group 2 would deal defending group 1 19025 damage +Immune System group 2 would deal defending group 2 19025 damage + +Immune System group 2 attacks defending group 1, killing 4 units +Infection group 1 attacks defending group 2, killing 143 units + +Immune System: +Group 2 contains 618 units +Infection: +Group 1 contains 789 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 183048 damage +Immune System group 2 would deal defending group 1 15450 damage +Immune System group 2 would deal defending group 2 15450 damage + +Immune System group 2 attacks defending group 1, killing 3 units +Infection group 1 attacks defending group 2, killing 143 units + +Immune System: +Group 2 contains 475 units +Infection: +Group 1 contains 786 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 182352 damage +Immune System group 2 would deal defending group 1 11875 damage +Immune System group 2 would deal defending group 2 11875 damage + +Immune System group 2 attacks defending group 1, killing 2 units +Infection group 1 attacks defending group 2, killing 142 units + +Immune System: +Group 2 contains 333 units +Infection: +Group 1 contains 784 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 181888 damage +Immune System group 2 would deal defending group 1 8325 damage +Immune System group 2 would deal defending group 2 8325 damage + +Immune System group 2 attacks defending group 1, killing 1 unit +Infection group 1 attacks defending group 2, killing 142 units + +Immune System: +Group 2 contains 191 units +Infection: +Group 1 contains 783 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 181656 damage +Immune System group 2 would deal defending group 1 4775 damage +Immune System group 2 would deal defending group 2 4775 damage + +Immune System group 2 attacks defending group 1, killing 1 unit +Infection group 1 attacks defending group 2, killing 142 units + +Immune System: +Group 2 contains 49 units +Infection: +Group 1 contains 782 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 181424 damage +Immune System group 2 would deal defending group 1 1225 damage +Immune System group 2 would deal defending group 2 1225 damage + +Immune System group 2 attacks defending group 1, killing 0 units +Infection group 1 attacks defending group 2, killing 49 units + +Immune System: +No groups remain. +Infection: +Group 1 contains 782 units +Group 2 contains 4434 units + +In the example above, the winning army ends up with 782 + 4434 = 5216 units. + +You scan the reindeer's condition (your puzzle input); the white-bearded man looks nervous. As it +stands now, how many units would the winning army have? + + diff --git a/src/24/part2 b/src/24/part2 new file mode 100644 index 0000000..2cf3f09 --- /dev/null +++ b/src/24/part2 @@ -0,0 +1,186 @@ +--- Part Two --- + +After careful analysis, one thing is certain: you have no idea where all these bugs are coming +from. + +Then, you remember: Eris is an old Plutonian settlement! Clearly, the bugs are coming from +recursively-folded space. + +This 5x5 grid is only one level in an infinite number of recursion levels. The tile in the middle of +the grid is actually another 5x5 grid, the grid in your scan is contained as the middle tile of a +larger 5x5 grid, and so on. Two levels of grids look like this: + + | | | | + | | | | + | | | | +-----+-----+---------+-----+----- + | | | | + | | | | + | | | | +-----+-----+---------+-----+----- + | | | | | | | | + | |-+-+-+-+-| | + | | | | | | | | + | |-+-+-+-+-| | + | | | |?| | | | + | |-+-+-+-+-| | + | | | | | | | | + | |-+-+-+-+-| | + | | | | | | | | +-----+-----+---------+-----+----- + | | | | + | | | | + | | | | +-----+-----+---------+-----+----- + | | | | + | | | | + | | | | + +(To save space, some of the tiles are not drawn to scale.) Remember, this is only a small part of +the infinitely recursive grid; there is a 5x5 grid that contains this diagram, and a 5x5 grid that +contains that one, and so on. Also, the ? in the diagram contains another 5x5 grid, which itself +contains another 5x5 grid, and so on. + +The scan you took (your puzzle input) shows where the bugs are on a single level of this structure. +The middle tile of your scan is empty to accommodate the recursive grids within it. Initially, no +other levels contain bugs. + +Tiles still count as adjacent if they are directly up, down, left, or right of a given tile. Some +tiles have adjacent tiles at a recursion level above or below its own level. For example: + + | | | | + 1 | 2 | 3 | 4 | 5 + | | | | +-----+-----+---------+-----+----- + | | | | + 6 | 7 | 8 | 9 | 10 + | | | | +-----+-----+---------+-----+----- + | |A|B|C|D|E| | + | |-+-+-+-+-| | + | |F|G|H|I|J| | + | |-+-+-+-+-| | + 11 | 12 |K|L|?|N|O| 14 | 15 + | |-+-+-+-+-| | + | |P|Q|R|S|T| | + | |-+-+-+-+-| | + | |U|V|W|X|Y| | +-----+-----+---------+-----+----- + | | | | + 16 | 17 | 18 | 19 | 20 + | | | | +-----+-----+---------+-----+----- + | | | | + 21 | 22 | 23 | 24 | 25 + | | | | + + + - Tile 19 has four adjacent tiles: 14, 18, 20, and 24. + + - Tile G has four adjacent tiles: B, F, H, and L. + + - Tile D has four adjacent tiles: 8, C, E, and I. + + - Tile E has four adjacent tiles: 8, D, 14, and J. + + - Tile 14 has eight adjacent tiles: 9, E, J, O, T, Y, 15, and 19. + + - Tile N has eight adjacent tiles: I, O, S, and five tiles within the sub-grid marked ?. + + +The rules about bugs living and dying are the same as before. + +For example, consider the same initial state as above: + +....# +#..#. +#.?## +..#.. +#.... + +The center tile is drawn as ? to indicate the next recursive grid. Call this level 0; the grid +within this one is level 1, and the grid that contains this one is level -1. Then, after +ten minutes, the grid at each level would look like this: + +Depth -5: +..#.. +.#.#. +..?.# +.#.#. +..#.. + +Depth -4: +...#. +...## +..?.. +...## +...#. + +Depth -3: +#.#.. +.#... +..?.. +.#... +#.#.. + +Depth -2: +.#.## +....# +..?.# +...## +.###. + +Depth -1: +#..## +...## +..?.. +...#. +.#### + +Depth 0: +.#... +.#.## +.#?.. +..... +..... + +Depth 1: +.##.. +#..## +..?.# +##.## +##### + +Depth 2: +###.. +##.#. +#.?.. +.#.## +#.#.. + +Depth 3: +..### +..... +#.?.. +#.... +#...# + +Depth 4: +.###. +#..#. +#.?.. +##.#. +..... + +Depth 5: +####. +#..#. +#.?#. +####. +..... + +In this example, after 10 minutes, a total of 99 bugs are present. + +Starting with your scan, how many bugs are present after 200 minutes? + + diff --git a/src/24/solve.py b/src/24/solve.py new file mode 100644 index 0000000..fc89c84 --- /dev/null +++ b/src/24/solve.py @@ -0,0 +1,127 @@ +import sys +sys.path.append("../common") +import aoc + +immunesys = 0 +infection = 1 +ctype = 0 + +# parse input from file +def parse_input(): + groups = list() + for l in aoc.data.split("\n"): + pl = parse_entry(l) + if pl != None: + groups.append(pl) + return groups + +# parse line of input +def parse_entry(line): + global ctype + group = None + if "Immune" in line: + ctype = immunesys + elif "Infection" in line: + ctype = infection + elif line != "": + ls = line.split() + group = dict() + group["type"] = ctype + group["units"] = int(ls[0]) + group["unithp"] = int(ls[4]) + group["initiative"] = int(ls[-1]) + group["weak"] = list() + group["immune"] = list() + if "(" in line: + parenthstr = line.split("(")[1].split(")")[0] + traits = parenthstr.split(";") + for traitstr in traits: + info = traitstr.split() + group[info[0]] = [v.replace(",","") for v in info[2:]] + dmginfo = line.split("does")[1].split("damage")[0].split() + group["dmg"] = int(dmginfo[0]) + group["dmgtype"] = dmginfo[1] + return group + +def effective_power(g): + return g["units"] * g["dmg"] + +def damage(attacker, defender): + dmg = effective_power(attacker) + dmg *= (0 if attacker["dmgtype"] in defender["immune"] else 1) + dmg *= (2 if attacker["dmgtype"] in defender["weak"] else 1) + return dmg + +groups = parse_input() + +def fight(): + global groups + + lunits = 0 + + immalive = len([g for g in groups if g["type"] == immunesys]) + infalive = len([g for g in groups if g["type"] == infection]) + + while immalive > 0 and infalive > 0: + # target selection + attacked = list() + attackpairs = list() + groups = sorted(groups, key = lambda x : (effective_power(x), x["initiative"]), reverse = True) + for group in groups: + # choose group of other army, which is not already being attacked and sort appropriately + enemies = [g for g in groups if g["type"] != group["type"] and g not in attacked] + if len(enemies) == 0: + continue + target = max(enemies, key = lambda x : \ + (damage(group, x), effective_power(x), x["initiative"])) + if damage(group, target) != 0: # enemies which arent immune + attacked.append(target) + attackpairs.append((groups.index(group), groups.index(target))) + + # attacking phase + attackpairs = sorted(attackpairs, key = lambda x : groups[x[0]]["initiative"], reverse = True) + + for ap in attackpairs: + attacker = groups[ap[0]] + attacked = groups[ap[1]] + # if attacker or defender is dead, no need to attack + if attacker["units"] > 0 and attacked["units"] > 0: + dmg = damage(attacker, attacked) + # remove whole numbers of units + attacked["units"] = max(0, attacked["units"] - dmg // attacked["unithp"]) + + groups = [g for g in groups if g["units"] > 0] + immalive = sum([g["units"] for g in groups if g["type"] == immunesys]) + infalive = sum([g["units"] for g in groups if g["type"] == infection]) + units = immalive + infalive + if units == lunits: + return units + lunits = units + + return units + +def solve1(args): + return fight() + +def solve2(args): + global groups + + immunewin = False + boost = 1 + while not immunewin: + groups = parse_input() + for g in groups: + if g["type"] == immunesys: + g["dmg"] += boost + + fight() + + immunewin = (sum([0 if g["type"] == immunesys else 1 for g in groups]) == 0) + + boost += 1 + + aoc.debug("boost:", boost) + + return sum([v["units"] for v in groups]) + +aoc.run(solve1, solve2, sols=[10538, 9174]) -- cgit v1.2.3-71-gd317