Advent of Code 2018 day 23 solution to handle adversarial input
# AOC 2018 day 23 solution to defeat adversarial input (python3) | |
# Adversarial input sample can be found https://pastebin.com/raw/9eJQN836 | |
# This will try to open the file given as the first command line argument | |
# or "aoc23.in.txt" if no argument is given. | |
# This solution transforms the given coordinates in x-y-z space into 4D | |
# coordinates in a space I call s-t-u-v space, even though I never actually | |
# deal with 's', 't', 'u', or 'v' directly. | |
import itertools | |
import numpy as np | |
import sys | |
import re | |
import heapq | |
# Global setup for interesting_points, below | |
# The idea is that I'm creating matrices that can later find me the | |
# intersection in x-y-z space of three planes drawn from the collection of | |
# eleven planes given by the eight planes that define a given box in s-t-u-v | |
# space and the three planes x=0, y=0, and z=0. The closest point to the | |
# origin within the box must be at such an intersection. | |
choose_src = np.array( | |
[[-1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], | |
[1, -1, 1, 0, 1, 0, 0, 0, 0, 0, 0], | |
[1, 1, -1, 0, 0, 1, 0, 0, 0, 0, 0], | |
[1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0], | |
[-1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0], | |
[1, -1, 1, 0, 0, 0, 0, 0, 1, 0, 0], | |
[1, 1, -1, 0, 0, 0, 0, 0, 0, 1, 0], | |
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1], | |
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], | |
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]] | |
) | |
# Note that choose_src is 11 x 11. | |
# I'm going to take three rows at a time from choose_src, then split | |
# the result into a 3x3 matrix on the left, and a 3x8 matrix on the | |
# right. (call them L and R) I'm then later going to want to find | |
# the vector xyz such that: | |
# L @ xyz == R @ box_bounds_stuv | |
# where box_bounds_stuv is the eight numbers that define the 4D box in | |
# s-t-u-v space: [min_x, min_t, min_u, min_v, max_s, max_t, max_u, max_v] | |
# | |
# To do that easily later, here I remember the matrix | |
# matr = inv(L) @ R | |
interesting_matrices = [] | |
for rows in itertools.combinations(range(11), 3): | |
sub = choose_src[rows, :] | |
if np.linalg.det(sub[:3, :3]) == 0.0: | |
continue | |
matr = np.linalg.inv(sub[:3, :3]) @ sub[:3, 3:] | |
if all((matr != m).any() for m in interesting_matrices): | |
# we haven't seen matr before | |
# yeah, repeated linear scan over interesting_matrices, but we | |
# have fewer than 165 (11 choose 3, but some have det == 0.0) | |
# possibilities, so it's not a big deal | |
interesting_matrices.append(matr) | |
interesting_matrices = np.array(interesting_matrices) | |
def which_bots(box0, box1): | |
box4_within = ((box0 <= bot_max) & (box1 > bot_min)) | |
return box4_within.all(axis=1) | |
def interesting_points(box0, box1): | |
""" | |
Return points inside the four-dimensional box that might have the | |
smallest distance-to-origin. That'll be any point that corresponds | |
to a corner of the box or to the intersection of one or more | |
bounding planes of the box and one of the x=0, y=0, or z=0 planes. | |
To guard against possible off-by-one errors introduced by float->int | |
conversion, we perturb each xyz coordinate by up to one in each | |
direction before converting back to stuv-coordinates and checking | |
membership in the box. | |
""" | |
box_coords = (np.array([box0, box1]) - [[0], [1]]).reshape((8, 1)) | |
interesting_xyz = (interesting_matrices @ box_coords).astype(int) | |
interesting_xyz = interesting_xyz.reshape( | |
interesting_xyz.shape[0], 1, 3, 1) | |
add_array = np.array(list(itertools.product( | |
(-1, 0, 1), (-1, 0, 1), (-1, 0, 1)))).reshape(27, 3, 1) | |
all_xyz = (add_array + interesting_xyz).reshape( | |
27*(interesting_xyz.shape[0]), 3, 1) | |
all_stuv = np.array([[-1, 1, 1], | |
[1, -1, 1], | |
[1, 1, -1], | |
[1, 1, 1]]) @ all_xyz | |
all_stuv = all_stuv.reshape(all_stuv.shape[0], 4) | |
valid = ((np.array(box0) <= all_stuv) & | |
(all_stuv < np.array(box1))).all(axis=1) | |
return sorted(set(tuple(x) for x in all_stuv[valid])) | |
def min_distance_to_origin(box0, box1): | |
interesting = interesting_points(box0, box1) | |
if not interesting: | |
# Can happen if box is such that there are no | |
# points in it with s % 2 == t % 2 == u % 2 | |
# and v = s + t + u | |
return None | |
else: | |
return min(abs(c[0]+c[1])//2 + | |
abs(c[1]+c[2])//2 + | |
abs(c[0]+c[2])//2 | |
for c in interesting) | |
if __name__ == '__main__': | |
with open('aoc23.in.txt' if len(sys.argv) < 2 else sys.argv[1]) as f: | |
data = list(f) | |
bots = [tuple(map(int, list(re.findall(r'-?\d+', ln)))) for ln in data] | |
maxrad = max(r for (x, y, z, r) in bots) | |
maxradbot = [n for (n, b) in enumerate(bots) if b[3] == maxrad][0] | |
bot_coords = np.array([[-1, 1, 1], | |
[1, -1, 1], | |
[1, 1, -1], | |
[1, 1, 1]]) @ ( | |
np.array([b[0:3] for b in bots]).transpose()) | |
bot_coords = bot_coords.transpose() | |
bot_radii = np.array([b[3] for b in bots]).reshape((len(bots), 1)) | |
bot_max = bot_coords + bot_radii | |
bot_min = bot_coords - bot_radii | |
#print(bot_coords.shape) | |
#print(bot_radii.shape) | |
maxradbot_max = bot_max[maxradbot, :] | |
maxradbot_min = bot_min[maxradbot, :] | |
print("bots in range of maxrad bot", | |
( | |
(bot_coords >= maxradbot_min) & (bot_coords <= maxradbot_max) | |
).all(axis=1).astype(int).sum()) | |
# Find a box big enough to contain everything in range | |
maxabscord = max(abs(bot_max).max(), abs(bot_min).max()) + maxrad | |
workheap = [] | |
corner0 = tuple([-maxabscord] * 4) | |
corner1 = tuple([maxabscord] * 4) | |
workheap.append( | |
(-len(bots), 0, 16*(maxabscord**4), (corner0, corner1))) | |
# Set up heap to work on boxes | |
# | |
# The idea is that we first work on a box with the most bots in range. | |
# In the event of a tie, work on the one with the lowest estimate for | |
# "distance to origin of intersection". In case that still ties, use | |
# the smallest box. | |
# | |
# These rules mean that if I get to where I'm processing a 1x1x1 box, | |
# I know I'm done: | |
# - no larger box can intersect more bots' ranges than what I'm working on | |
# - no other box intersecting the same number of bots can be as close | |
# | |
# Getting this right depends crucially on the fact that the estimate | |
# of distance can never overestimate, only underestimate, and also that | |
# it's guaranteed accurate for a 1x1x1 box. | |
# remember heapq.heappop pulls the smallest off the heap, so negate | |
# the two things I want to pull by largest (reach of box, boxsize) and | |
# do not negate distance-to-origin, since I want to work on smallest | |
# distance-to-origin first | |
print_bots = False # Change this to see the bots in range | |
i = 0 | |
while workheap: | |
i += 1 | |
(negreach, dist_to_orig, sz, box) = heapq.heappop(workheap) | |
box0 = np.array(box[0]) | |
box1 = np.array(box[1]) | |
if sz == 1: | |
print("Found closest at %s dist %s (%s bots in range)" % | |
(str(box[0]), dist_to_orig, -negreach)) | |
print("Normal coords", | |
((box[0][0]+box[0][1])//2, | |
(box[0][2]+box[0][1])//2, | |
(box[0][0]+box[0][2])//2)) | |
if print_bots: | |
print("bots:") | |
mine = which_bots(box[0], box[1]) | |
for c in np.flatnonzero(mine): | |
print(c+1, ':', data[c].strip(), bot_min[c], bot_max[c]) | |
break | |
# Debugging/tuning: | |
print(-negreach, sz, dist_to_orig, i, len(workheap), end='') | |
mybots = which_bots(box0, box1) | |
subboxes = [] | |
for axis in (0, 1, 2, 3): | |
arange = (box0[axis], box1[axis]) | |
division_points = (set(arange) | set(bot_min[mybots, axis]) | |
| set(bot_max[mybots, axis] + 1)) | |
division_points = list(x for x in division_points if x >= arange[0] | |
and x <= arange[1]) | |
if len(division_points) >= 3: | |
division_points.sort() | |
for (lo, hi) in ((division_points[ndx], division_points[ndx+1]) | |
for ndx in range(len(division_points)-1)): | |
newbox0 = list(box[0]) | |
newbox1 = list(box[1]) | |
newbox0[axis] = lo | |
newbox1[axis] = hi | |
subboxes.append((tuple(newbox0), tuple(newbox1))) | |
print(f' (axis {axis})') | |
break | |
else: | |
# Everything is now in the same bots' ranges. Therefore only the | |
# interesting points matter: | |
ip = interesting_points(box0, box1) | |
if ip: | |
print(f' (interesting points: {box})') | |
for pt in ip: | |
subboxes.append((pt, tuple(np.array(pt) + 1))) | |
else: | |
print(' (backup halving)') | |
# halve in each dimension | |
halfway = tuple((box[0][i] + box[1][i]) // 2 | |
for i in (0, 1, 2, 3)) | |
for octant in itertools.product((0, 1), (0, 1), (0, 1), (0, 1)): | |
newbox0 = tuple(halfway[i] if octant[i] else box[0][i] | |
for i in (0, 1, 2, 3)) | |
newbox1 = tuple(box[1][i] if octant[i] else halfway[i] | |
for i in (0, 1, 2, 3)) | |
subboxes.append((newbox0, newbox1)) | |
for (newbox0, newbox1) in subboxes: | |
if newbox0[3] < sum(newbox0[0:3]): | |
newbox0 = newbox0[0:3] + (sum(newbox0[0:3]),) | |
if newbox1[3] > sum(newbox1[0:3]): | |
newbox1 = newbox1[0:3] + (sum(newbox1[0:3]),) | |
sz_box = (int(newbox1[0] - newbox0[0]), | |
int(newbox1[1] - newbox0[1]), | |
int(newbox1[2] - newbox0[2])) | |
newsz = (sz_box[0] * sz_box[1] * sz_box[2]) | |
if newsz <= 0: | |
continue | |
newreach = which_bots(newbox0, newbox1).astype(int).sum() | |
if newreach > 0: | |
d_t_o = min_distance_to_origin(newbox0, newbox1) | |
if d_t_o is not None: | |
heapq.heappush(workheap, (-newreach, d_t_o, newsz, | |
(newbox0, newbox1))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment