import numpy as np
import re
# K we gotta do some work to get these into nice arrays
particles = open('/Users/Sven/py_files/aoc_2017/d20_input.txt').readlines()
particles = [re.sub(r'p|v|a|=|\n', '', part) for part in particles]
particles[:5]
def vec_to_array(text):
text = re.sub(r'<|>', '', text)
vals = text.split(',')
vals = [int(val) for val in vals]
vals = np.array(vals)
return(vals)
particle_nums = [i for i in range(len(particles))]
positions = [vec_to_array(part.split('>, <')[0]) for part in particles]
velocities = [vec_to_array(part.split('>, <')[1]) for part in particles]
accelerations = [vec_to_array(part.split('>, <')[2]) for part in particles]
accelerations[:5]
So the difficult thing about this is that there is a bit of a vague definition of what the goal is. It just says which particle will be closest to <0, 0, 0> in the long run. I think maybe I can just do something where I increase the number of repetitions 10 fold and then wait until a single one is closest 5 times in a row or something like that.
Use this function to compute the distance from the origin:
def d_to_origin(pos):
return(sum([abs(x) for x in pos]))
I found that the np.array cannot take integers larger than 2^32-1 but I think that's okay for our purposes... We're not interested in the largest values.
This function will compute the sum of consecutive integers:
def consec(n):
if n == 0:
tot = 0
else:
tot = int(n*(n+1)/2)
return(np.array([tot for i in range(3)]))
And this function to take in a P-V-A and compute the position:
def move(p, v, a, n):
acc_mult = consec(n)
return(d_to_origin(p + v * n + a * acc_mult))
Kind of inefficient to call consec on every call of move. We could probably call consec once and then have it as an argument to move.
Now define the initial conditions and start looping until we reach 5 consecutive equal measures
closest_log = []
iteration = 0
while iteration < 5 or min(closest_log[-5:]) != max(closest_log[-5:]):
# I originally wanted to use zip here but it seems that map does not take kindly to that data type
distances = map(move, positions, velocities, accelerations, [10 ** iteration for i in range(len(positions))])
# Note that map returns a specific data type and that you have to coerce back to list:
distances = np.array(list(distances))
min_val = min(distances)
# if we find multiple values, put in negative iteration. This will cause us to not
# register these cases as the same vector being closest
# otherwise append the vector #
if sum(distances == min_val) > 1:
closest_log.append(-iteration)
else:
closest_log.append(distances.argmin())
iteration +=1
closest_log[-10:]
So we're getting some overflow warnings, undoubtedly due to the taxi cab distances but that's okay. The important part of this question is the smaller distances. I am a little unsure if this threshold of 5 in a row was a good idea though as you can see we hit 4 in a row prior to 831 interrupting this. Seems like we may have gotten a bit lucky here.
We're now asked about how many collisions will occur within the set of particles. This seems like a much tougher problem since theoretically, a collision could appear at any distance out in the future. I suspect that we can 'solve' this in a similar way where we just let it go for a long time but knowing for a fact that no future collisions will occur seems quite hard.
I suppose we could do something where we calculate the distance from each other particle and when a particle gets farther from each other one, we can drop it. My first attempt at this part involved calculating the number of unique positions the particles took at each point and then comparing it to the number of positions to determine if any collisions occurred. I now see that if I'm going to have to compute all the distances from each other point, we might as well use that to determine if collisions occur as well. I feel like this is actually a very computationally expensive problem and we may want to spend some time to speed it up. We previously went up to 10^15 iterations but that may not be necessary to determine this part.
Let's see what we can get with this pdist function to compute pairwise distances.
from scipy.spatial.distance import pdist, squareform
print(accelerations[:4], end = '\n\n')
print(pdist(accelerations[:4], 'cityblock'), end = '\n\n')
print(squareform(pdist(accelerations[:4], 'cityblock')), end = '\n\n')
np.where(pdist(accelerations[:4], 'cityblock') == 29)
So this function will get us the indices of the comparisons made by pdist.
This took me an embarrassingly long time to figure out but I think it works. You feed it the index along
pdist and also the number of particles comapared
# Can we come up with a function to figure out the indices of the particles that collide?
def where_zero(index, n):
# If we receive 5 comparisons, we'll look to the first 4 which means indices 0:3
n -= 1
position = n-1
# first particle index
i = 0
while index > position:
n -= 1
position += n
i += 1
# Now look for the second index:
if i == 0:
j = index
else:
position -= n
#print(position)
j = index % (position)
return([i, j + i])
where_zero(9, 6)
So now what we need to do is create a function that does this:
def check_dist(pos, vel, acc, i):
# compute distances
vel = np.add(vel, acc)
pos_next = np.add(pos, vel)
# We could use euclidean but I bet cityblock is faster
distances = pdist(pos_next, 'cityblock')
# If we find a pair with zero
if(max(distances == 0) == True):
# get the indices of the collisions
collision = []
for col in np.where(distances == 0)[0]:
#print(col)
collision.append(where_zero(col, len(pos)))
else:
collision = None
# We also want to check if the distances are going up every 10 calls
# or so
if i % 10 == 0:
distances_old = squareform(pdist(pos, 'cityblock'))
distances = squareform(distances)
# flag the ones that are at least as far from every other particle as they were before
far_out = np.where((distances_old <= distances).all(1))[0].tolist()
if len(far_out) == 0:
far_out = None
# Deal with the case where we're at one left:
if len(pos) == 1:
far_out = [0]
else:
far_out = None
# Return the next position, velocity, and (possible) collisions
return(pos_next, vel, collision, far_out)
Okay now we need to write our loop. Here's the pseudo:
check_distremaining = 0
i = 0
positions2 = positions.copy()
velocities2 = velocities.copy()
accelerations2 = accelerations.copy()
while len(positions2) > 0 :
i += 1
positions2, velocities2, collisions, far_out = check_dist(positions2, velocities2, accelerations2, i)
if not far_out is None:
remaining += len(far_out)
# Determine what we have to delete, if anything
if not collisions is None:
collisions = np.unique(np.array(collisions)).tolist()
if not far_out is None:
deletions = collisions.append(far_out)
else:
deletions = collisions
elif not far_out is None:
deletions = far_out
else:
deletions = []
positions2 = np.delete(positions2, deletions, axis = 0)
velocities2 = np.delete(velocities2, deletions, axis = 0)
accelerations2 = np.delete(accelerations2, deletions, axis = 0)
remaining
PHEW! That was pretty tricky. I learned quite a bit about how to find things within the np.arrays as well as how to modify them. I'm a bit surprised that you have to do so much to change the values. They also made this tricky because there were moments when multiple collisions occurred and points where my algorithm detected far out particles as well as collisions. WOOT