Advent of code 2018 day 23 part 2 visualization

This is a description of a correct algorithm that doesn't involve ILP and still runs reasonably fast on the problem input (few ms in C, few seconds in javascript). I'll describe it through a 2D version of the problem. The 3d version is the same but the splitting part creates 8 cubes rather than 4 squares.

In a previous version of this page I claimed that this is a pretty fast algorithm in general but a reddit user quickly pointed out that it is not the case and provided a testcase that pretty much kills this algorithm performance wise, see worstcase.input (yay, Cunningham's Law works). For reference here's the full thread: https://reddit.com/r/adventofcode/comments/a99n7x. Nevertheless, this is should be still a usable approach to solving the problem for the specific input from the puzzle.

The idea is to have 'searchsquares'. Each searchsquare has several properties:

bottom left corner of the square
size of the square (always power of two)
number of bots that have the square in range (in other words: number of bots whose range touches the square)
distance to origin

Then the algorithm is the following:

Create a searchsquare that covers all the bots.
Push that onto the work queue.
Loop {
  Pop a searchsquare from the queue that is:
    a) is in range for the most bots,
    b) in case of ties is closest to origin,
    c) in case of ties is the smallest.
  If the popped searchsquare has a size of 1 {
    Print the popped searchsquare's distance to origin.
    Exit.
  }
  Split it into 4 smaller searchsquares.
  Count the number of nanobots in each.
  Push the 4 smaller searchsquares to the work queue.
}

Here's a javascript demo that demonstrates how the algorithm's searchsquares slowly find the point of interest. It consists of two parts. In part 1 you add all the bots, then in part 2 you observe the simulation.

Part 1 controls:

left click: select bot
right click: put down a bot
middle click: adjust bot range
shift left click: delete a bot

In part 2 (the simulation part) all you need to is to spam the Step button and observe the behavior. In each step the algorithm pops the front of the queue, replaces it with 4 small squares (it omits empty squares though) and then highlights the new top of the queue. The top of the queue is always the searchsquare with most bots (or closest to origin in case of ties). You can click on the canvas to highlight other searchsquares to see where are they in the queue or what bots are they covering.

Work queue (binary heap order): ...

Processed searchsquares: ...

The indices here are searchsquares. Click in the searchsquares list to see a specific searchsquare visualised.

Result:

For reference here is a solver for the 3D case. Copy paste the problem's input and click solve.

Result: press solve first

Look for the solve() function in the source of this page to see the javascript version or look at 23.c to see the C version of this solver.