23-part-two.py

#!/usr/bin/env python3
import re, sys
from heapq import heapify, heappush, heappop

class Bot:
    def __init__(self, x, y, z, r):
        self.x = x
        self.y = y
        self.z = z
        self.r = r

    def range_clips_with_cube(self, x1, y1, z1, x2, y2, z2):
        # Does the octahedron defined by this bot
        # overlap with the cube (x1,y1,z1)-(x2,y2,z2)?
        assert x1 <= x2 and y1 <= y2 and z1 <= z2
        dist = 0
        if self.x < x1:   dist += x1 - self.x
        elif self.x > x2: dist += self.x - x2
        if self.y < y1:   dist += y1 - self.y
        elif self.y > y2: dist += self.y - y2
        if self.z < z1:   dist += z1 - self.z
        elif self.z > z2: dist += self.z - z2
        return dist <= self.r

bots = [Bot(*map(int, re.findall(r'-?\d+', line, re.ASCII)))
        for line in sys.stdin]

min_x = min(b.x for b in bots)
max_x = max(b.x for b in bots)
min_y = min(b.y for b in bots)
max_y = max(b.y for b in bots)
min_z = min(b.z for b in bots)
max_z = max(b.z for b in bots)

s = 1  # size of the cube, a power of two
while s < max(max_x - min_x, max_y - min_y, max_z - min_z):
    s *= 2

q = []  # min-heap

def add(x1, y1, z1):
    x2 = x1 + s - 1
    y2 = y1 + s - 1
    z2 = z1 + s - 1
    in_range = 0
    for b in bots:
        if b.range_clips_with_cube(x1, y1, z1, x2, y2, z2):
            in_range += 1
    if in_range > 0:
        # Distance from (0,0,0) to the closest corner of the cube
        dist = (min(abs(x1), abs(x2))
                + min(abs(y1), abs(y2))
                + min(abs(z1), abs(z2)))
        heappush(q, (-in_range, dist, s, x1, y1, z1))

add(min_x, min_y, min_z)
while q:
    score, dist, s, x, y, z = heappop(q)
    if s == 1:
        print("best location:", (x, y, z))
        print("bots in range:", -score)
        print("distance from origin:", dist)
        break

    s //= 2
    add(x, y, z)
    add(x, y, z+s)
    add(x, y+s, z)
    add(x, y+s, z+s)
    add(x+s, y, z)
    add(x+s, y, z+s)
    add(x+s, y+s, z)
    add(x+s, y+s, z+s)

oops! copy+paste error. everything works fine

It seems to work fine for me, both for my input, and for the problem statement short example:
`$ cat ~/adventofcode2018/day23/example2.input ; echo ; cat ~/adventofcode2018/day23/example2.input | time ~/adventofcode2018/tmp/day23.cube_subdivision.very_fast.under_1_second.py
pos=<10,12,12>, r=2
pos=<12,14,12>, r=2
pos=<16,12,12>, r=4
pos=<14,14,14>, r=6
pos=<50,50,50>, r=200
pos=<10,10,10>, r=5

best location: (12, 12, 12)
bots in range: 5
distance from origin: 36
0.02user 0.00system 0:00.03elapsed 100%CPU (0avgtext+0avgdata 10028maxresident)k
0inputs+0outputs (0major+1226minor)pagefaults 0swaps
`

For my input, it takes ~0.80s , which is very impressive indeed (especially when z3 runs for 74s for the same input).

@oatmeal Very strange, I can't reproduce that. I get the expected output for that input.