Advent of Code 2018, Day 23Published on 2019-01-03
For the last three years, Eric Wastl has celebrated the holidays by releasing the Advent of Code, which is a series of 25 holiday-themed coding challenges. They start simple, but by the end they're pretty damned interesting. I highly recommend giving the series a shot. Rather than going over the solution to every day, I want to talk about my favorite puzzle: Day 23.
You're given a list of coordinates representing a cloud of drones in 3D space, and each drone has a variable signal signal strength represented by the radius in which a drone can communicate. Your job is to find the point in the cloud where you can communicate with the most drones. The input looks something like this, with 1000 distinct drones in the list:
pos=<-13227272,16297847,20713224>, r=74781821 pos=<-13506391,-11400225,79194067>, r=98387056 pos=<51916866,7859874,63870681>, r=67604198 pos=<6053871,-6125982,40030492>, r=58607212
A couple of things jump out. First, the ranges are HUGE. The search area will be gigantic. Second, the signal strength of each drone is ALSO very large; we're going to see a ton of overlap. Here we see the drones represented with and without their signals. (For the rest of the images I'm going to hide the radius, because it's visually noisy.)
An initial failure
The first thing I tried is starting in the middle of the cloud of drones, searching near that point to find the point with the most drones, then repeating from that new point. My implementation was to throw out a big sphere, pick the best point, throw out a slightly smaller sphere from that new point, and repeat until we'd converged on an area with a lot of drones. (Why a sphere? Well, because it sounded cool. I ended up tossing it for a cube.) This solution sort of worked, but it ended up getting stuck in local maxima that it was unable to escape. This is a similar to problems of gradient descent; the algorithm can settle into a low point, but not the lowest point.
Here's an abbreviated version of that first attempt:
def most_central_location(self): step_size = 10000000 mean_point = (avg_x, avg_y, avg_z) best_point = mean_point most_bots, best_dist = point_score(mean_point) while step_size >= 1: points = points_on_sphere(100, best_point, step_size) for point in points: bots, avg_dist = point_score(point) # avg_dist ignores signal strength if bots > most_bots or bots == most_bots and avg_dist < best_dist: best_point = point most_bots = bots best_dist = avg_dist step_size //= 2 return best_point
A working answer
Clearly we need to be able to path through areas with fewer drones if the right path is on the other side. It's too optimistic to assume that you can just cleanly walk from your starting point towards the neighboring areas with the most drones. In order to fix this we need a way to track a number of different potential areas, and resume our search from the one we think is most promising. Enter the heap! We'll pop things off of the heap in the order of how good we think they might be. We want a couple of things from our search areas; we want a lot of drones, and we want a small search area.
Here is the core of the working algorithm:
def most_central_location(self): mean_point = (avg_x, avg_y, avg_z) search_area = SearchArea( center=mean_point, bots_in_range=self.bots_in_range(mean_point, size), search_size=size) heap = [search_area] while heap: area: SearchArea = heappop(heap) if area.search_size == 0: return area points = BotSwarm.octants(area.search_size, area.center) for point in points: bots = self.bots_in_range(point, area.search_size // 2) new_area = SearchArea(center=point, bots_in_range=bots, search_size=area.search_size // 2) heappush(heap, new_area) return None
Okay, perfect, this works for the puzzle input! Let's watch it in action.
So, will our algorithm work for all problems of this type? It will not! Someone created a neat adversarial input for this puzzle, and it causes my solution to take an unreasonable amount of time. Let's check it out.
pos=<1000000,-1000000,0>, r=1499999 pos=<1500000,-1500000,0>, r=1499999 pos=<2000000,-2000000,0>, r=1499999 pos=<2500000,-2500000,0>, r=1499999
Uh oh. This looks like evenly spaced points with an identical radius for every drone. Every search area is going to be nearly identical. Lets watch the algorithm choke:
Welp. As you can see, Eric was nice enough that the bot formation he chose for the problem was solvable in a reasonable time with this kind of pathfinding type approach.
The Advent of Code subreddit thread on Day 23 was full of great discussion. Many people solved this problem with a solution similar to the one I used, and some used other techniques.
Z3 SMT Solver
A popular path was to use the Z3 SMT solver, and if you have no idea what that is then we're on the same page. My fuzzy understanding after a quick read is that you give it constraints and a pile of data, and it tells you if the data can satisfy those constraints.