Reorder days into src

1 files changed, 108 insertions, 0 deletions

diff --git a/src/23/solve.py b/src/23/solve.py
new file mode 100644
index 0000000..f78dd94
--- /dev/null
+++ b/src/23/solve.py
@@ -0,0 +1,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])