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