aoc23.rb

require 'algorithms'
require 'matrix'

def run input
  input = input.split("\n")
  bots = input.map { |str|
    pos, r = str.split(', ')
    pos = Vector[*(pos[5..-2].split(',').map(&:to_i))]
    r = r.split('=').last.to_i
    [pos, r]
  }
  xmin, xmax = bots.map(&:first).map {|v| v[0] }.sort.values_at(0, -1)
  ymin, ymax = bots.map(&:first).map {|v| v[1] }.sort.values_at(0, -1)
  zmin, zmax = bots.map(&:first).map {|v| v[2] }.sort.values_at(0, -1)

  box_min = Vector[xmin, ymin, zmin]
  box_max = Vector[xmax, ymax, zmax]
  center = (box_max - box_min) / 2
  max_side = (box_max - box_min).max
  interval = 2
  interval <<= 1 until interval >= max_side
  box_min = center - (Vector[interval, interval, interval] / 2)

  pos, bot_count = octree_search box_min, interval, bots
  puts "#{bot_count} bots in range at #{pos}, score: #{pos.sum {|i| i.abs}}"
end

def octree_search box_min, size, bots
  queue = Containers::PriorityQueue.new
  queue.push [box_min, size], 0

  while !queue.empty?
    box_min, size = queue.pop

    if size == 1
      return box_min, intersect_count(box_min, size, bots)
    end

    octree_split(box_min, size, bots).each do |box_min, size|
      queue.push [box_min, size], [intersect_count(box_min, size, bots), -box_min.sum {|i| i.abs}]
    end
  end
end

def octree_split box_min, size, bots
  size >>= 1
  [0, size]
    .product([0, size], [0, size])
    .map { |offset| [box_min + Vector[*offset], size] }
end

def intersect_count box_min, size, bots
  bots.count { |sphere_pos, sphere_r|
    sphere_box_intersect? box_min, size, sphere_pos, sphere_r
  }
end

def sphere_box_intersect? box_min, size, sphere_pos, sphere_r
  box_min = box_min - sphere_pos
  distance = (0..2).sum do |i|
    min = box_min[i]
    max = min + size - 1
    if (min..max).cover? 0
      0
    elsif min > 0
      min.abs
    else
      max.abs
    end
  end
  distance <= sphere_r
end