15.py
1 from lib import * 2 3 input = read_input(2018, 15) 4 5 lines = input.splitlines() 6 7 8 def adj(x, y): 9 return [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] 10 11 12 entities = {} 13 walls = set() 14 idx = 0 15 for i, line in enumerate(lines): 16 for j, c in enumerate(line): 17 if c == "#": 18 walls.add((j, i)) 19 elif c != ".": 20 entities[(j, i)] = (idx, c == "E", 200) 21 idx += 1 22 23 rnd = 0 24 while True: 25 done = False 26 orig = entities.copy() 27 for x, y in sorted(entities, key=lambda a: a[::-1]): 28 if (x, y) not in entities: 29 continue 30 idx, elf, hp = entities[(x, y)] 31 if idx != orig[(x, y)][0]: 32 continue 33 if not any(q[1] != elf for q in entities.values()): 34 done = True 35 break 36 37 in_range = [(p, q) for p in adj(x, y) if (q := entities.get(p)) and q[1] != elf] 38 if not in_range: 39 queue = [(0, x, y)] 40 visited = set() 41 dist = None 42 nearest = [] 43 while queue: 44 d, p, q = queue.pop(0) 45 if (p, q) in visited: 46 continue 47 48 visited.add((p, q)) 49 if any(e[1] != elf for r in adj(p, q) if (e := entities.get(r))): 50 if dist is None: 51 dist = d 52 elif d > dist: 53 break 54 nearest.append((p, q)) 55 56 for r in adj(p, q): 57 if r in walls: 58 continue 59 if (e := entities.get(r)) and e[1] == elf: 60 continue 61 queue.append((d + 1, *r)) 62 63 if not nearest: 64 continue 65 66 target = min(nearest, key=lambda a: a[::-1]) 67 queue = [(0, *target)] 68 visited = set() 69 dist = None 70 nearest = [] 71 while queue: 72 d, p, q = queue.pop(0) 73 if (p, q) in visited: 74 continue 75 76 visited.add((p, q)) 77 if (x, y) in adj(p, q): 78 if dist is None: 79 dist = d 80 elif d > dist: 81 break 82 83 nearest.append((p, q)) 84 85 for r in adj(p, q): 86 if r in walls: 87 continue 88 if (e := entities.get(r)) and e[1] == elf: 89 continue 90 91 queue.append((d + 1, *r)) 92 93 if not nearest: 94 continue 95 96 g = min(nearest, key=lambda a: a[::-1]) 97 entities[g] = entities.pop((x, y)) 98 x, y = g 99 100 in_range = [(p, q) for p in adj(x, y) if (q := entities.get(p)) and q[1] != elf] 101 102 if in_range: 103 in_range.sort(key=lambda a: (a[1][2], a[0][::-1])) 104 p, (idx2, elf2, hp2) = in_range[0] 105 hp2 -= 3 106 if hp2 <= 0: 107 entities.pop(p) 108 else: 109 entities[p] = idx2, elf2, hp2 110 111 if done: 112 break 113 114 rnd += 1 115 116 print(rnd * sum(e[2] for e in entities.values())) 117 118 119 def simulate(ap): 120 entities = {} 121 walls = set() 122 idx = 0 123 for i, line in enumerate(lines): 124 for j, c in enumerate(line): 125 if c == "#": 126 walls.add((j, i)) 127 elif c != ".": 128 entities[(j, i)] = (idx, c == "E", 200) 129 idx += 1 130 131 rnd = 0 132 while True: 133 done = False 134 135 orig = entities.copy() 136 for x, y in sorted(entities, key=lambda a: a[::-1]): 137 if (x, y) not in entities: 138 continue 139 140 idx, elf, hp = entities[(x, y)] 141 if idx != orig[(x, y)][0]: 142 continue 143 144 if not any(q[1] != elf for q in entities.values()): 145 done = True 146 break 147 148 in_range = [(p, q) for p in adj(x, y) if (q := entities.get(p)) and q[1] != elf] 149 if not in_range: 150 queue = [(0, x, y)] 151 visited = set() 152 dist = None 153 nearest = [] 154 while queue: 155 d, p, q = queue.pop(0) 156 if (p, q) in visited: 157 continue 158 159 visited.add((p, q)) 160 if any(e[1] != elf for r in adj(p, q) if (e := entities.get(r))): 161 if dist is None: 162 dist = d 163 elif d > dist: 164 break 165 nearest.append((p, q)) 166 for r in adj(p, q): 167 if r in walls: 168 continue 169 if (e := entities.get(r)) and e[1] == elf: 170 continue 171 172 queue.append((d + 1, *r)) 173 174 if not nearest: 175 continue 176 177 target = min(nearest, key=lambda a: a[::-1]) 178 queue = [(0, *target)] 179 visited = set() 180 dist = None 181 nearest = [] 182 while queue: 183 d, p, q = queue.pop(0) 184 if (p, q) in visited: 185 continue 186 187 visited.add((p, q)) 188 if (x, y) in adj(p, q): 189 if dist is None: 190 dist = d 191 elif d > dist: 192 break 193 nearest.append((p, q)) 194 195 for r in adj(p, q): 196 if r in walls: 197 continue 198 if (e := entities.get(r)) and e[1] == elf: 199 continue 200 queue.append((d + 1, *r)) 201 202 if not nearest: 203 continue 204 205 g = min(nearest, key=lambda a: a[::-1]) 206 entities[g] = entities.pop((x, y)) 207 x, y = g 208 209 in_range = [(p, q) for p in adj(x, y) if (q := entities.get(p)) and q[1] != elf] 210 if in_range: 211 in_range.sort(key=lambda a: (a[1][2], a[0][::-1])) 212 p, (idx2, elf2, hp2) = in_range[0] 213 hp2 -= ap if elf else 3 214 if hp2 <= 0: 215 if elf2: 216 return -1 217 218 entities.pop(p) 219 else: 220 entities[p] = idx2, elf2, hp2 221 222 if done: 223 break 224 225 rnd += 1 226 227 return rnd * sum(e[2] for e in entities.values()) 228 229 230 ap = 4 231 while (res := simulate(ap)) < 0: 232 ap += 1 233 print(res)