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.
CodePudding user response：
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.
CodePudding user response：
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.