Google Foobar L4：带枪去训练师打架
Google Foobar L4: Bringing a gun to a trainer fight
我几天前开始遇到这个问题（下面的代码）。
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.
我让两个测试用例都通过了我的计算机，但由于某种原因，当我在平台上验证代码时，两次中只有第二次通过（第一个失败）。此外，第 4、5 和 6 个测试用例通过（全部隐藏），其余（总共 10 个）失败。这是我的代码：
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]))
我从网上和运行其他人提交的代码中得到了一些额外的测试用例来检查答案：
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
除了最后一个案例solution([3, 4], [1, 1], [2, 2], 500) == 54243，这里的一切都通过了，我实际上得到了 54239。
我已经在这个问题上停留了几个小时，老实说我不明白为什么 a) 我在平台上的可见测试失败了，我知道在我自己的机器上通过得很快（即使我' m 使用经过验证的库和所有这些) 和 b) 为什么我要通过除最后一个之外的所有其他我自己的测试用例。我希望这也能帮助我弄清楚为什么我无法通过平台上的其他隐藏测试用例。
我设法弄清楚我遗漏了什么 — 我的解决方案在 Python 3 中是正确的，而且我认为我已经解决了 Python 2.7 中的所有版本差异，但事实证明还有一个。我相信这与 range() 的工作方式或我计算 cp_x 和 cp_y 的方式有关，即第一象限中的最大副本数。在我的迭代中添加一个，这样：
# 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
已修复。
在Python2、/performs integer division。因此，在
这样的代码中
int(ceil((your_position[0] + distance) / dimensions[0]))
ceil 没有用，因为该值已经向下舍入了。
此计算不需要 Floating-point 算法，对于 the usual reasons.
这些情况最好避免 floating-point
相反，我们将使用一个函数来获得“上限整数除法”结果。诀窍是先对分子进行加法运算，使值增加 1，除非分子已经被整除。那么，我们需要添加的数量是分母减去一。
此版本在 Python 2 和 3 中的工作方式应该相同，因为 // 无论如何执行底除法（在 2 中，/ 是整数的底除法，但是“ floating-point 值的真"除法）。
def ceil_div(quotient, divisor):
return (quotient + divisor - 1) // divisor
现在我们可以做到
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])
它应该在 Python 2 或 Python 3 中工作。我们不再需要强制转换为 int，因为输入是整数，因此 floored 除法也将产生一个整数。
我几天前开始遇到这个问题（下面的代码）。
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.
我让两个测试用例都通过了我的计算机，但由于某种原因，当我在平台上验证代码时，两次中只有第二次通过（第一个失败）。此外，第 4、5 和 6 个测试用例通过（全部隐藏），其余（总共 10 个）失败。这是我的代码：
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]))
我从网上和运行其他人提交的代码中得到了一些额外的测试用例来检查答案：
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
除了最后一个案例solution([3, 4], [1, 1], [2, 2], 500) == 54243，这里的一切都通过了，我实际上得到了 54239。
我已经在这个问题上停留了几个小时，老实说我不明白为什么 a) 我在平台上的可见测试失败了，我知道在我自己的机器上通过得很快（即使我' m 使用经过验证的库和所有这些) 和 b) 为什么我要通过除最后一个之外的所有其他我自己的测试用例。我希望这也能帮助我弄清楚为什么我无法通过平台上的其他隐藏测试用例。
我设法弄清楚我遗漏了什么 — 我的解决方案在 Python 3 中是正确的，而且我认为我已经解决了 Python 2.7 中的所有版本差异，但事实证明还有一个。我相信这与 range() 的工作方式或我计算 cp_x 和 cp_y 的方式有关，即第一象限中的最大副本数。在我的迭代中添加一个，这样：
# 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
已修复。
在Python2、/performs integer division。因此，在
int(ceil((your_position[0] + distance) / dimensions[0]))
ceil 没有用，因为该值已经向下舍入了。
Floating-point 算法，对于 the usual reasons.
这些情况最好避免 floating-point相反，我们将使用一个函数来获得“上限整数除法”结果。诀窍是先对分子进行加法运算，使值增加 1，除非分子已经被整除。那么，我们需要添加的数量是分母减去一。
此版本在 Python 2 和 3 中的工作方式应该相同，因为 // 无论如何执行底除法（在 2 中，/ 是整数的底除法，但是“ floating-point 值的真"除法）。
def ceil_div(quotient, divisor):
return (quotient + divisor - 1) // divisor
现在我们可以做到
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])
它应该在 Python 2 或 Python 3 中工作。我们不再需要强制转换为 int，因为输入是整数，因此 floored 除法也将产生一个整数。