My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import re
2import copy
3import fileinput
4
5from utils import parse_line, parse_nums
6
7
8class Group:
9 def __init__(self, is_infection, num, _count, hp, weaknesses, immunities, dmg, type, initiative):
10 self.alliance = 'Infection' if is_infection else 'Immune System'
11 self.is_infection = is_infection
12 self.num = num
13 self.count = _count
14 self.hp = hp
15 self.weaknesses = weaknesses
16 self.immunities = immunities
17 self.dmg = dmg + (0 if self.is_infection else BOOST)
18 self.type = type
19 self.initiative = initiative
20
21 @property
22 def power(self):
23 return self.count * self.dmg
24
25 def calc_dmg(self, other):
26 if self.type in other.immunities:
27 return 0
28 elif self.type in other.weaknesses:
29 return 2 * self.power
30 else:
31 return self.power
32
33 def deal_dmg(self, other):
34 dmg = self.calc_dmg(other)
35 units_lost = min(dmg // other.hp, other.count)
36 other.count -= units_lost
37 return units_lost
38
39
40def setup_simulation():
41 immune = {}
42 infect = {}
43 groups = []
44
45 for i, line in enumerate(IMMUNE):
46 g = Group(False, i, *line)
47 immune[i] = g
48 groups.append(g)
49
50 for i, line in enumerate(INFECT):
51 g = Group(True, i, *line)
52 infect[i] = g
53 groups.append(g)
54
55 return immune, infect, groups
56
57
58# Read problem input
59IMMUNE = []
60INFECT = []
61BOOST = 0
62DEBUG = False
63
64on_infection = False
65
66for i, line in enumerate(fileinput.input()):
67 line = line.strip()
68
69 if line == 'Infection:':
70 on_infection = True
71 continue
72
73 try:
74 _count, hp, dmg, initiative = parse_nums(line, negatives=False)
75 except Exception:
76 continue
77 clauses = next(iter(re.findall(r'(\(.+\))', line)), None)
78 type = re.findall(r'(\S+) damage', line)
79 type = next(iter(type), None)
80
81 parts = (clauses or '').replace(',', '').replace('(', '').replace(')', '').split(';')
82 weaknesses = []
83 immunities = []
84
85 if parts[0] != '':
86 for part in parts:
87 things = part.split()
88 if things[0] == 'weak':
89 weaknesses = things[2:]
90 else:
91 immunities = things[2:]
92
93 group = (_count, hp, weaknesses, immunities, dmg, type, initiative)
94
95 if on_infection:
96 INFECT.append(group)
97 else:
98 IMMUNE.append(group)
99
100
101def simulate(boost=0):
102 global BOOST
103 BOOST = boost
104 immune, infection, groups = setup_simulation()
105
106 last_infcount = None
107 last_imscount = None
108
109 while True:
110 # Target selection
111 targets = {}
112
113 if DEBUG:
114 for alliance, group in [("Immune System", immune), ("Infection", infection)]:
115 print "{}:".format(alliance)
116 for n, g in group.items():
117 if g.count > 0:
118 print "Group {} contains {} units".format(n, g.count)
119
120 print
121
122 for g in sorted(groups, key=lambda g: (g.power, g.initiative), reverse=True):
123 if g.count == 0:
124 continue
125
126 other = immune if g.is_infection else infection
127
128 target_num = None
129
130 for h in (z for z in groups if z.alliance != g.alliance):
131 if h.count == 0:
132 continue
133
134 leave = False
135 for a, b in targets.items():
136 if a[0] == g.alliance and h.num == b:
137 leave = True
138 break
139
140 if leave:
141 continue
142
143 if DEBUG:
144 print "{} group {} would deal defending group {} {} damage".format(g.alliance, g.num, h.num, g.calc_dmg(h))
145
146 if g.calc_dmg(h) > 0:
147 if target_num is None:
148 target_num = h.num
149 else:
150 poss = other[target_num]
151 if g.calc_dmg(h) > g.calc_dmg(poss):
152 target_num = h.num
153 elif g.calc_dmg(h) == g.calc_dmg(poss):
154 if h.power > poss.power:
155 target_num = h.num
156 elif h.power == poss.power:
157 if h.initiative > poss.initiative:
158 target_num = h.num
159
160 targets[g.alliance, g.num] = target_num
161
162 if DEBUG:
163 print
164
165 # Attack
166 for g in sorted(groups, key=lambda g: g.initiative, reverse=True):
167 other = immune if g.is_infection else infection
168 h = other.get(targets.get((g.alliance, g.num), None), None)
169 if h is None:
170 continue
171 killed = g.deal_dmg(h)
172
173 if DEBUG:
174 print "{} group {} attacks defending group {}, killing {} units".format(g.alliance, g.num, h.num, killed)
175
176 if DEBUG:
177 print
178 print
179
180 infcount = 0
181 imscount = 0
182 for g in groups:
183 if g.is_infection:
184 infcount += g.count
185 else:
186 imscount += g.count
187
188 if infcount == 0:
189 return True, imscount
190 elif imscount == 0:
191 return False, infcount
192 elif infcount == last_infcount and imscount == last_imscount:
193 return False, None
194
195 last_infcount = infcount
196 last_imscount = imscount
197
198print "Units in the winning army:", simulate()[1]
199
200lo = 0
201hi = 1000
202
203while lo < hi:
204 mid = (lo + hi) // 2
205 res, count = simulate(mid)
206 if not res:
207 lo = mid + 1
208 else:
209 hi = mid
210
211print "Immune system units after smallest boost ({}): {}".format(mid + 1, simulate(mid + 1)[1])