This is a problem that was presented to me through the google foobar challenge, but my time has since expired and they had decided that I did not complete the problem. I suspect a possible bug on their side, because I passed 9/10 test cases (which are hidden from me) but I'm unsure. I'd really like to know where or if I made a mistake, so I'll ask the problem here.
The problem is as follows: you are standing in a room with integer dimensions, where the left wall exists at $x=0$, and the right wall exists at $x=x_0$. Similarly, the bottom wall exists at $y=0$ and the top wall exists at $y=y_0$. Within this room, you and another individual (which we call a guard) stand on the integer lattice such that your coordinates are at $[x_{s}, y_{s}]$, and the guard stands at $[x_g, y_g]$, where
$$ 0<x_s<x_0 \\ 0<x_g<x_0 \\ 0<y_s<y_0 \\ 0<y_g<y_0 \\ y_s \neq y_g~\text{or}~x_s \neq x_g \\ $$
that is, neither you nor the guard is standing on a wall, and you occupy distinct positions in the room. If you have a bullet which can travel a total distance $d$, then determine the number of distinct directions in which you can fire the bullet such that it hits the other individual, travels a distance less than or equal to $d$, and it does not hit yourself in the process. This is written as a function:
solution(room_dimensions, your_position, guard_position, d)
What I had noticed in my solution was that the allowed directions can be written as a vector of the total distance traveled by the bullet in a specific dimension, where a negative sign indicates initial movement towards $x=0$ or $y=0$, and a positive sign indicates initial movement towards $x=x_0$ or $y=y_0$. Let's give an example of what this means.
Suppose the room has dimensions $[2, 3]$ and you stand at $[1, 2]$ and the guard stands at $[1, 1]$. Then, of course the bullet could go straight down: $[0, -1]$ is a valid bearing. However, we could bounce the bullet off of the left wall, and then have the bullet hit the guard: $[-2, -1]$. That $-2$ is valid because the total distance traveled is $2$: $1$ unit is traveled in moving from your position to the left wall, and an additional $1$ from moving back towards the guard. It is negative because we are moving towards the left wall $x=0$. This can be extended the any number of bounces off of each wall, and each dimension can be considered independently. So, for each dimension, I generate a list of the allowed distances (with sign indicating direction) which results in the bullet arriving at the same coordinate as the guard in that dimension.
If we generate the aforementioned lists (allowed_x, allowed_y) for the $x$ and $y$ dimensions, then $[X, Y]$ $X\in$ allowed_x, $Y\in$ allowed_y is a valid bearing which will take the bullet from you to the guard, with two created problems: 1) The bullet may first pass through you, and 2) Some of these bearings may point in the same direction and travel different distances.
If we determine all of the directions that result in you being hit by the bullet, we can see if a parallel direction exists in the list of directions which result in the guard being hit, and if it does and the path to you being hit is shorter, then that is not a valid direction as it requires the bullet to pass through you. This resolves 1).
2) Is resolved by checking to see if directions are parallel before counting them, and if they are, we record the shorter of the two distances. In this way, we only get distinct directions.
As I said, my code works for 9/10 tests, which are hidden from me. As a result, it is likely that the 1/10 case is specifically chosen to test an extreme which, at random, you would not encounter. I thoroughly tested my code, so I don't believe such an extreme exits, but I would be very relieved if someone could point out my oversight. Cheers!
I've attached my python 2.7.13 code below if anyone wants to get very involved.
from fractions import gcd
from random import randint
def get_1D_bearings(t, m, g, distance):
'''
Returns a list of the total distance travelled in 1D which results in the beam arriving at the guard's t-coordinate.
Parameters:
t(int): The length of this dimension.
m(int): The t-coodinate of the shooter (me).
g(int): The t-coordinate of the guard.
distance(int): The maximum allowed distance that the beam may travel.
'''
i = 0
bearings = []
path = g - m # Direct path from the shooter to the guard with no bounces.
if abs(path) <= distance:
bearings.append(path)
while True:
# Initial bounce off of the positive wall and final bounce off of the positive wall.
path = (t - m) + (t-g) + 2*i*t
if abs(path) <= distance:
bearings.append(path)
# Initial bounce off of the negative wall and final bounce off of the negative wall.
path = - (m+g+2*i*t)
if abs(path) <= distance:
bearings.append(path)
# Initial bounce off of the positive wall and final bounce off of the negative wall.
path = (t - m) + g + (2*i+1)*t
if abs(path) <= distance:
bearings.append(path)
# Initial bounce off of the negative wall and final bounce off of the positive wall.
path = - ( m + (t - g) + (2*i+1)*t)
if abs(path) <= distance:
bearings.append(path)
else:
break
i += 1
return bearings
def are_parallel(a, b):
'''
Returns if the bearings given by a and b are parallel vectors.
Parameters:
a(array-like): A 2D-array of integers.
b(array-like): A 2D-array of integers.
'''
x1, y1 = a
x2, y2 = b
div1 = abs(gcd(x1, y1))
div2 = abs(gcd(x2, y2) )
if div1 == 0 or div2 ==0:
if not div1 == 0 and div2 == 0:
return False
elif (x1 == 0 and x2 == 0) and (y1 // abs(y1) == y2 // abs(y2)):
return True
elif (y1 == 0 and y2 ==0) and (x1 // abs(x1) == x2 // abs(x2)):
return True
else:
return False
else:
if x1 // div1 == x2 // div2 and y1 // div1 == y2 // div2:
return True
else:
return False
class VectorsNotParallel(Exception):
'''Raise this exception when handling vectors which are assumed to be parallel but are not.'''
def __init__(self):
pass
def get_shorter_bearing(a, b):
'''
Returns the shorter vector of a and b. If they are not parallel, raises VectorsNotParallel.
Parameters:
a(array-like): A 2D-array of integers indicating a direction.
b(array-like): A 2D-array of integers indicating a direction.
'''
if not are_parallel(a, b):
raise VectorsNotParallel("These bearings point in different directions: " + str(a) + " and " + str(b))
x1, y1 = a
x2, y2 = b
if x1 == 0:
if abs(y1) < abs(y2):
return a
else:
return b
if y1 == 0:
if abs(x1) < abs(x2):
return a
else:
return b
div1 = abs(gcd(x1, y1))
div2 = abs(gcd(x2, y2) )
if div1 < div2:
return a
else:
return b
def get_all_bearings(dimensions, your_position, guard_position, distance):
'''
Combines the allowed distances from each of the two dimensions to generate a list of all of the
allowed directions that can be shot in which take a beam from your_position to guard_position
while not travelling further than the provided distance. Note that some of these directions include
passing through your_position.
Parameters:
dimensions(array-like): A 2D-array of integers indicating the size of the room.
your_position(array-like): A 2D-array of integers indicating your position in the room.
guard_position(array-like): A 2D-array of integers indicating the guard's position in the room.
distance(int): An integer indicating the maximum distance the beam can travel.
Returns:
bearings(array-like): An array of 2D-arrays indicating the bearings which move the beam from your_position
to guard_position.
'''
dx, dy= dimensions
sx, sy = your_position
gx, gy = guard_position
allowed_x = get_1D_bearings(dx, sx, gx, distance)
allowed_y = get_1D_bearings(dy, sy, gy, distance)
bearings = []
for x in allowed_x:
for y in allowed_y:
if x**2 + y**2 < 1 or x**2 + y**2 > distance **2:
continue
res = [x, y]
append = True # Do we need to append to the list of bearings or just update an existing one
for bearing in bearings:
if are_parallel(res, bearing):
append = False
res_2 = get_shorter_bearing(res, bearing)
bearing[0] = res_2[0]
bearing[1] = res_2[1]
if append:
bearings.append(res)
return bearings
def count_friendly_fires(friendly_bearings, guard_bearings):
'''
Returns the number of bearings which result in the guard being hit only after the beam
passes through the shooter (which is not allowed).
Parameters:
friendly_bearings(array-like): An array of 2D arrays which indicate bearings that reach the shooter.
guard_bearings(array-like): An array of 2D arrays which indicate bearings that reach the guard.
'''
count = 0
for f_bearing in friendly_bearings:
for g_bearing in guard_bearings:
if are_parallel(f_bearing, g_bearing):
if get_shorter_bearing(f_bearing, g_bearing) == f_bearing:
print(f_bearing, g_bearing)
count += 1
return count
def solution(dimensions, your_position, guard_position, distance):
'''
Returns the number of distinct directions that take a bullet from your_position to
guard_position within the allowed distance.
Parameters:
dimensions(array-like): A 2D-array of integers indicating the size of the room.
your_position(array-like): A 2D-array of integers indicating your position in the room.
guard_position(array-like): A 2D-array of integers indicating the guard's position in the room.
distance(int): An integer indicating the maximum distance the beam can travel.
'''
guard_hitting_bearings = get_all_bearings(dimensions, your_position, guard_position, distance)
self_hitting_bearings = get_all_bearings(dimensions, your_position, your_position, distance)
count = count_friendly_fires(self_hitting_bearings, guard_hitting_bearings)
return len(guard_hitting_bearings) - count
I have inspected your code thoroughly and cannot find any issue; it seems entirely robust to me, at least in terms of correctness. However, I am aware that Foobar imposes time limits on problems; I suspect that your code failed that one test case because it was too slow.
To be precise, let us define $B$ as the maximum product of the sizes of
allowed_xandallowed_y(in a vague sense, the maximum of the sizes ofguard_hitting_bearingsandself_hitting_bearings, although typically it will be much larger). We'll investigate the runtimes of each of the functions in your code, and provide a vague asymptotic bound.Firstly,
are_parallelis clearly $O(1)$, so we can just lump it in with the other constant time operations. The same goes forget_shorter_bearing.Now, for
get_all_bearings, we have an outer pair of loops that iterates through all $O(B)$ possibilities; and for each of the actually valid ones, it iterates through the entire list so far, for a total complexity of $O(B^2)$.Similarly, for
count_friendly_fires, we iterate over all pairs of bearings betweenfriendly_bearingsandguard_bearings, and thus again have a complexity of $O(B^2)$.Overall, this code is $O(B^2)$ (plus some other small stuff we don't particularly care about), and we can significantly improve on that. Additionally, and importantly, this quadratic upper bound can be forced by a sufficiently bad input; for instance, setting your initial position to $(1, 1)$, the guard position to $(2, 2)$, and the room dimensions to $p \times p$ for some prime $p$ should force the sizes of
guard_hitting_bearingsandself_hitting_bearingsto be at most a constant factor smaller than the product of the sizes ofallowed_xandallowed_y. I suspect the last test case was probably something to this effect, designed to break solutions which were too slow (you probably passed the other test cases because they all had lots of parallel vectors, so the sizes reduced significantly). In any case, it is clear that improvements will have to be made to the two $O(B^2)$ functions listed above.Looking at your code, a pattern emerges in the places that degenerate into $O(B^2)$: they all involve a naive parallel vector check, so optimising this is the key to making the code run faster. The key idea is as follows. Let $x \parallel y$ if and only if
are_parallel(x, y). This is an equivalence relation ($x \parallel x$ for all $x$, and $x \parallel y$ and $y \parallel z$ implies $x \parallel z$). Now define $r(v)$ to be the vector with smallest magnitude such that $r(v) \parallel v$; it is easy to see that this vector is uniquely defined, and a function to compute $r(v)$ in $O(1)$ can be obtained by a simple modification ofare_parallel. Now, since $r(v)$ is uniquely defined, we have the fact $$ x \parallel y \iff r(x) = r(y). $$ This is the key to optimising your solution. In particular, instead of arrays, we can use a dictionary indexed by $r(v)$.Instead of the $O(B)$ inner loop in
get_all_bearingsto check if the new vector is parallel with anything already inbearing, we simply check the element atbearing[r(v)](if such an element exists); this reduces the loop to a simple $O(1)$ dictionary lookup, and thus overallget_all_bearingsis reduced to $O(B)$. Similarly,count_friendly_firescan iterate over all key-value pairs infriendly_bearings, and simply look up the element ofguard_bearingsparallel to the current key (if such an element exists); again the $O(B)$ inner loop is reduced to $O(1)$, making the function $O(B)$ overall. Thus, with this simple modification, your code can be made to run quite significantly faster.Paul has some nice, readable code implementing this idea in another answer. His $r(v)$ is called
get_direction, for reference.