Advent of code 2018 day 23

def process1(s, part2=False):
  # Divide-and-conquer using octree decomposition, adapted from
  # https://github.com/wimglenn/advent-of-code-wim/blob/master/aoc_wim/aoc2018/q23.py.
  # Improved to be robust (not assuming cubes with power-of-two dimensions).
  pattern = r'pos=<([0-9-]+),([0-9-]+),([0-9-]+)>, r=(\d+)'
  data = np.array([list(map(int, re.fullmatch(pattern, line).groups()))
                   for line in s.strip('\n').split('\n')])
  xs, rs = data[:, :-1], data[:, -1]
  if not part2:
    i = rs.argmax()
    return (abs(xs - xs[i]).sum(axis=1) <= rs[i]).sum()

  xl, xh = xs.min(axis=0), xs.max(axis=0)
  pq = [(0, (xh - xl).max(), abs(xl).sum(), tuple(xl), tuple(xh))]
  while pq:
    n_out, s, d, xl, xh = heapq.heappop(pq)
    if s == 0:
      return d
    xm = (np.array(xl) + xh) // 2  # Partition into up to 8 octree child cells.
    for child_min_max in itertools.product(
        *(((l, m), (m + 1, h)) if m < h else ((l, h),)
          for l, m, h in zip(xl, xm, xh))):
      xl, xh = np.array(child_min_max).T
      n_out = ((np.maximum(xl - xs, 0) + np.maximum(xs - xh, 0)).sum(axis=1)
               > rs).sum()  # Maximize num in-range = minimize num out-of-range.
      heapq.heappush(
          pq, (n_out, (xh - xl).max(), abs(xl).sum(), tuple(xl), tuple(xh)))