solve.py (3684B)
1import sys 2sys.path.append("../common") 3import aoc 4import math 5 6# nanobots consist of tuples containing: (position, radius) 7nanobots = list() 8 9# parse a line of input file 10def parse_entry(l): 11 s = l.split(">, ") 12 pos = [int(v) for v in s[0].split("=<")[1].split(",")] 13 radius = int(s[1].split("=")[1]) 14 nanobots.append((pos, radius)) 15 16data = [parse_entry(l) for l in aoc.data.split("\n") if len(l) != 0] 17 18# manhattan distance 19def dist(p1, p2): 20 xd = abs(p1[0] - p2[0]) 21 yd = abs(p1[1] - p2[1]) 22 zd = abs(p1[2] - p2[2]) 23 return xd + yd + zd 24 25# two nanobots range overlap 26def is_overlap(nb1, nb2): 27 return nb1[1] + nb2[1] >= dist(nb1[0], nb2[0]) 28 29# nanobots range completely inside anothers range 30def is_inside(nb1, nb2): 31 return dist(nb1[0], nb2[0]) <= nb2[1] - nb1[1] 32 33# check if range of nanobot is inside grid 34def tile_in_range(tile, nb, gridsize): 35 hgridsize = math.floor(gridsize / 2) # case gridsize = 1 => squares should have 0 width 36 nbp = nb[0] 37 ds = [abs(nbp[i] - tile[i]) for i in range(3)] 38 md = max(ds) 39 if md == 0: 40 return True 41 ds = [d * hgridsize / md for d in ds] # get distance along squares sides 42 return dist(nbp, tile) - sum(ds) <= nb[1] 43 44def solve1(args): 45 maxr = max(nanobots, key = lambda x : x[1]) 46 inrange = 0 47 for nb in nanobots: 48 if dist(nb[0], maxr[0]) <= maxr[1]: 49 inrange += 1 50 return inrange 51 52def solve2(args): 53 global nanobots 54 55 # use smaller getting grid like binary search to find position in range of most nanobots 56 minpx = min(nanobots, key = lambda x : x[0][0])[0][0] 57 minpy = min(nanobots, key = lambda x : x[0][1])[0][1] 58 minpz = min(nanobots, key = lambda x : x[0][2])[0][2] 59 minp = (minpx, minpy, minpz) 60 61 maxpx = max(nanobots, key = lambda x : x[0][0])[0][0] 62 maxpy = max(nanobots, key = lambda x : x[0][1])[0][1] 63 maxpz = max(nanobots, key = lambda x : x[0][2])[0][2] 64 maxp = (maxpx, maxpy, maxpz) 65 66 gridsize = max([maxp[i] - minp[i] for i in range(3)]) # largest dif dim to ensure all nanbots are in the grid 67 68 bestpos = None 69 while gridsize >= 1: 70 maxintile = 0 71 72 # traverse grid in steps of gridsize 73 xsteps = math.ceil((maxp[0] - minp[0]) / gridsize) + 1 74 ysteps = math.ceil((maxp[1] - minp[1]) / gridsize) + 1 75 zsteps = math.ceil((maxp[2] - minp[2]) / gridsize) + 1 76 for nx in range(xsteps): 77 for ny in range(ysteps): 78 for nz in range(zsteps): 79 x = minp[0] + nx * gridsize 80 y = minp[1] + ny * gridsize 81 z = minp[2] + nz * gridsize 82 intile = 0 83 for nb in nanobots: 84 # check if nanobots range intersects with tile 85 if tile_in_range((x, y, z), nb, gridsize): 86 intile += 1 87 if maxintile < intile: 88 maxintile = intile 89 bestpos = (x, y, z) 90 elif maxintile == intile: 91 dist = sum([abs(v) for v in (x, y, z)]) 92 bestdist = sum([abs(v) for v in bestpos]) 93 # if two gridtiles have the same count, 94 # choose the one closest to the origin 95 if maxintile == 0 or dist < bestdist: 96 bestpos = (x, y, z) 97 98 if gridsize == 1: 99 break 100 101 gridsize = math.floor(gridsize / 2) 102 103 minp = [v - gridsize for v in bestpos] 104 maxp = [v + gridsize for v in bestpos] 105 106 return sum(bestpos) 107 108aoc.run(solve1, solve2, sols=[573, 107279292])