Google Foobar L4: Bringing a gun to a trainer fight

Question

I started this problem a couple days ago (code below).

Bringing a Gun to a Trainer Fight
=================================

Uh-oh -- you've been cornered by one of Commander Lambdas elite bunny trainers! Fortunately, you grabbed a beam weapon from an abandoned storeroom while you were running through the station, so you have a chance to fight your way out. But the beam weapon is potentially dangerous to you as well as to the bunny trainers: its beams reflect off walls, meaning you'll have to be very careful where you shoot to avoid bouncing a shot toward yourself!

Luckily, the beams can only travel a certain maximum distance before becoming too weak to cause damage. You also know that if a beam hits a corner, it will bounce back in exactly the same direction. And of course, if the beam hits either you or the bunny trainer, it will stop immediately (albeit painfully). 

Write a function solution(dimensions, your_position, trainer_position, distance) that gives an array of 2 integers of the width and height of the room, an array of 2 integers of your x and y coordinates in the room, an array of 2 integers of the trainer's x and y coordinates in the room, and returns an integer of the number of distinct directions that you can fire to hit the elite trainer, given the maximum distance that the beam can travel.

The room has integer dimensions [1 < x_dim <= 1250, 1 < y_dim <= 1250]. You and the elite trainer are both positioned on the integer lattice at different distinct positions (x, y) inside the room such that [0 < x < x_dim, 0 < y < y_dim]. Finally, the maximum distance that the beam can travel before becoming harmless will be given as an integer 1 < distance <= 10000.

For example, if you and the elite trainer were positioned in a room with dimensions [3, 2], your_position [1, 1], trainer_position [2, 1], and a maximum shot distance of 4, you could shoot in seven different directions to hit the elite trainer (given as vector bearings from your location): [1, 0], [1, 2], [1, -2], [3, 2], [3, -2], [-3, 2], and [-3, -2]. As specific examples, the shot at bearing [1, 0] is the straight line horizontal shot of distance 1, the shot at bearing [-3, -2] bounces off the left wall and then the bottom wall before hitting the elite trainer with a total shot distance of sqrt(13), and the shot at bearing [1, 2] bounces off just the top wall before hitting the elite trainer with a total shot distance of sqrt(5).

Languages
=========

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Java cases --
Input:
Solution.solution([3,2], [1,1], [2,1], 4)
Output:
    7

Input:
Solution.solution([300,275], [150,150], [185,100], 500)
Output:
    9

-- Python cases --
Input:
solution.solution([3,2], [1,1], [2,1], 4)
Output:
    7

Input:
solution.solution([300,275], [150,150], [185,100], 500)
Output:
    9

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

I got both test cases to pass on my computer, but for some reason when I verify the code on the platform, only the second out of the two pass (the first one fails). In addition, the 4th, 5th, and 6th test cases pass (all hidden) and the rest (10 total) fail. Here is my code:

from math import sqrt, ceil, atan2

def solution(dimensions, your_position, trainer_position, distance):
    # calculate maximum repetiions of current room in mirrored room
    cp_x = int(ceil((your_position[0] + distance) / dimensions[0]))
    cp_y = int(ceil((your_position[1] + distance) / dimensions[1]))

    # generate all possible positions in q1
    q1_player = [your_position]
    q1_trainer = [trainer_position]
    for i in range(0, cp_x):
        for j in range(0, cp_y):
            if i == 0 and j == 0:
                continue
            else:
                temp_player = [your_position[0] + i * dimensions[0], your_position[1] + j * dimensions[1]]
                temp_trainer = [trainer_position[0] + i * dimensions[0], trainer_position[1] + j * dimensions[1]]
                if i % 2 != 0:
                    temp_player[0] = temp_player[0] - (2 * your_position[0]) + dimensions[0]
                    temp_trainer[0] = temp_trainer[0] - (2 * trainer_position[0]) + dimensions[0]
                if j % 2 != 0:
                    temp_player[1] = temp_player[1] - (2 * your_position[1]) + dimensions[1]
                    temp_trainer[1] = temp_trainer[1] - (2 * trainer_position[1]) + dimensions[1]
                q1_player.append(temp_player)
                q1_trainer.append(temp_trainer)

    # generate all possible positions in q2, q3, and q4
    q2_player = [[-x, y] for [x, y] in q1_player]
    q2_trainer = [[-x, y] for [x, y] in q1_trainer]
    q3_player = [[-x, -y] for [x, y] in q1_player]
    q3_trainer = [[-x, -y] for [x, y] in q1_trainer]
    q4_player = [[x, -y] for [x, y] in q1_player]
    q4_trainer = [[x, -y] for [x, y] in q1_trainer]

    # generate distances from original player
    player = [[x, y, dist(your_position, [x, y]), 1] for [x, y] in q1_player + q2_player + q3_player + q4_player]
    trainer = [[x, y, dist(your_position, [x, y]), 2] for [x, y] in q1_trainer + q2_trainer + q3_trainer + q4_trainer]
    corners = [[x, y, dist(your_position, [x, y]), 3] for [x, y] in [(0, 0), (dimensions[0], 0), (dimensions[0], dimensions[1]), (0, dimensions[1])]]

    # filter for distances that are too far away
    positions = filter(lambda x: x[2] <= float(distance), player + trainer + corners)
    positions = sorted(positions, key=lambda x: x[2]) # so least distance is always first


    # reduce list of lists with same angle but grab least distance
    angles = {}
    for pos in positions[1:]:
        agl = ang(your_position, [pos[0], pos[1]])
        if agl not in angles:
            angles[agl] = pos
            
    # uncomment to see the list of vectors
    # print([(pos[0] - your_position[0], pos[1] - your_position[1]) for pos in angles.values() if pos[4] == 2])

    # return number of times only trainer is hit
    return sum(1 for pos in angles.values() if pos[3] == 2)

def dist(p1, p2):
    return sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def ang(p1, p2):
    return atan2((p2[1] - p1[1]), (p2[0] - p1[0]))

I got a few extra test cases from online and by running other people's submitted code to check the answers:

def test():
    assert solution([3, 2], [1, 1], [2, 1], 4) == 7
    assert solution([2, 5], [1, 2], [1, 4], 11) == 27
    assert solution([23, 10], [6, 4], [3, 2], 23) == 8
    assert solution([1250, 1250], [1000, 1000], [500, 400], 10000) == 196
    assert solution([10, 10], [4, 4], [3, 3], 5000) == 739323
    assert solution([3, 2], [1, 1], [2, 1], 7) == 19
    assert solution([2, 3], [1, 1], [1, 2], 4) == 7
    assert solution([3, 4], [1, 2], [2, 1], 7) == 10
    assert solution([4, 4], [2, 2], [3, 1], 6) == 7
    assert solution([300, 275], [150, 150], [180, 100], 500) == 9
    assert solution([3, 4], [1, 1], [2, 2], 500) == 54243

Everything here passes except for the very last case, solution([3, 4], [1, 1], [2, 2], 500) == 54243, for which I actually get 54239.

I've been stuck on this for several hours and honestly can't figure out why a) I'm failing a visible test on the platform that I know passes quite quickly on my own machine (even though I'm using verified libraries and all that) and b) why I'm passing all other of my own test cases except the last one. I'm hoping this will also help me figure out why I fail the other hidden test cases on the platform.

Answer 1

In Python 2, / performs integer division. Thus, in code like

int(ceil((your_position[0] + distance) / dimensions[0]))

the ceil is useless, as the value has already been rounded down.

Floating-point arithmetic is not necessary for this calculation, and it's better to avoid floating-point for these cases for the usual reasons.

Instead, we'll use a function to get "ceiling integer division" results. The trick is to add to the numerator first, such that the value increases by 1 except when the numerator was already evenly divisible. The amount we need to add, then, is the denominator minus one.

This version should work the same way in both Python 2 and 3, as // performs floored division regardless (in 2, / is floored division for integers, but "true" division for floating-point values).

def ceil_div(quotient, divisor):
    return (quotient + divisor - 1) // divisor

And now we can do

def solution(dimensions, your_position, trainer_position, distance):
    # calculate maximum repetiions of current room in mirrored room
    cp_x = ceil_div((your_position[0] + distance), dimensions[0])
    cp_y = ceil_div((your_position[1] + distance), dimensions[1])

and it should work in either Python 2 or Python 3. We no longer need to coerce to int, because the inputs are integer and thus the floored division will also produce an integer.

Answer 2

I managed to figure out what I was missing — my solution was correct in Python 3, and I thought I had accounted for all the version differences in Python 2.7, but it turns out there's one more. I believe it had something to do with how range() works or how I calculated for cp_x and cp_y, the maximum number of copies in the first quadrant. Adding one to my iteration, such that:

# calculate maximum repetitions of current room in mirrored room
    cp_x = int(ceil((your_position[0] + distance) / dimensions[0]))
    cp_y = int(ceil((your_position[1] + distance) / dimensions[1]))

    # generate all possible positions in q1
    q1_player = [your_position]
    q1_trainer = [trainer_position]
    for i in range(0, cp_x + 1): # ADD ONE HERE
        for j in range(0, cp_y + 1): # ADD ONE HERE

fixed it.

Answer 3

I managed to figure out that test case 5 is this:

solution([1000,1000], [250,25], [257,49], 25) #=1

Because I had one code that passed all but test case 3 (because it was too slow), then one code that passed all but test case 5, so I combined them and said run through the first code if the distance is above a certain threshold and it worked, so I kept changing the distance value until it stopped working, then I could figure out the distance of test case 5, then I did the same for every other parameter. After I got the test case I could figure out where I went wrong and I finally passed it. If anyone wants some help on the code let me know. But my advice is:

Get the angles and distance for all the times you shoot yourself, and get the angles and distance for all the times you shoot the target. Do this with as minimal for loops as you can and use list comprehension if they are necessary. compile both into two seperate lists. Then use functions that handle the entire lists to deal with the rest from there. I don't want to give too much away but I will happily help if people want.