谷歌Foobar：把枪带到警卫队

我的情况

我现在已经开始和关闭这个挑战大约9天了，而且我没有想法。 到目前为止，我的解决方案通过了9/10的测试用例。 我的优化解决方案运行得足够快，因此错误是实际的解决方案，而不是计算时间不足。 如果有人能告诉我我缺少什么，或者我的算法实际上没有解决问题，我将不胜感激。 此外，我意识到我的一些代码并不完美 – 我计划在我有一个可行的解决方案之后解决所有问题。

问题

呃 – 哦 – 你已被一名指挥官Lambdas精英守卫逼入绝境！ 幸运的是，当你穿过火车站时，你从一个废弃的护柱上抓起了一把光束武器，所以你有机会战胜你的出路。 但是光束武器对你和精英守卫都有潜在的危险：它的光束会reflection到墙壁上，这意味着你必须非常小心地射击，以避免向自己弹射！

幸运的是，光束在变得太弱而不会造成损坏之前只能行进一定的最大距离。 你也知道如果一个光束撞到一个角落，它将以完全相同的方向反弹。 当然，如果光束击中你或守卫，它会立即停止（虽然很痛苦）。

写一个函数答案（尺寸，your_position，guard_position，distance），它给出了房间宽度和高度的2个整数数组，房间中x和y坐标的2个整数数组，2个整数的数组考虑到光束可以传播的最大距离，守卫在房间内的x和y坐标，并返回可以射击以击中精英守卫的不同方向的数量的整数。

房间有整数尺寸[1 <x_dim <= 1000,1 <y_dim <= 1000]。 您和精英守卫都位于房间内不同的不同位置（x，y）的整数格上，使得[0 <x <x_dim，0 <y <y_dim]。 最后，光束在变为无害之前可以行进的最大距离将以1 <距离<= 10000的整数给出。

例如，如果你和精英守卫被放置在一个尺寸为[3,2]，你有_1 [1,1]，guard_position [2,1]和最大射击距离为4的房间里，你可以用七种不同的方式射击击中精英守卫的方向（从您的位置给出矢量方位）：[1,0]，[1,2]，[1，-2]，[3,2]，[3，-2]，[ – 3,2]和[-3，-2]。 作为具体的例子，轴承[1,0]的镜头是距离为1的直线水平镜头，轴承[-3，-2]的镜头在击中精英后卫之前从左墙和底壁反弹。总射门距离为sqrt（13），并且在击中精英后卫之前，轴承[1,2]的射击仅在顶壁反弹，总射击距离为sqrt（5）。

我未完成的解决方案（Java）

public class Answer { public static int answer(int[] dimensions, int[] captain_position, int[] badguy_position, int distance) { int parallelDimensionX = (2 * (distance / dimensions[0])) + 1; int parallelDimensionY = (2 * (distance / dimensions[1])) + 1; int numDirections = 0; int distanceSquared = (int) Math.pow(distance, 2); ArrayList<ArrayList> directions = new ArrayList<ArrayList>(); ArrayList<ArrayList> sourceDirections = new ArrayList<ArrayList>(); ArrayList<ArrayList> sourceTracker = new ArrayList<ArrayList>(); for(int i = 0; i < 4; i++) { directions.add(new ArrayList()); sourceDirections.add(new ArrayList()); sourceTracker.add(new ArrayList()); } ArrayList<ArrayList> mirroredPlanes = MirroredPlanes(badguy_position, dimensions, new int[]{parallelDimensionX, parallelDimensionY}); ArrayList<ArrayList> mirroredSources = MirroredPlanes(captain_position, dimensions, new int[]{parallelDimensionX, parallelDimensionY}); for(int i = 0; i < parallelDimensionX; i++) { for(int j = 0; j < parallelDimensionY; j++) { int[] sourcePoint = mirroredSources.get(j).get(i); if(sourcePoint[0] == captain_position[0] && sourcePoint[1] == captain_position[1]) { continue; } int[] vecA = new int[] {sourcePoint[0] - captain_position[0], sourcePoint[1] - captain_position[1]}; double direction = Math.atan2(vecA[1], vecA[0]); int quadrant = 0; if(vecA[0] < 0) { quadrant++; } if(vecA[1] < 0) { quadrant += 2; } if(!sourceDirections.get(quadrant).contains(direction)) { sourceDirections.get(quadrant).add(direction); sourceTracker.get(quadrant).add(new int[]{j, i}); } else { int sourceIndex = sourceDirections.get(quadrant).indexOf(direction); if((sourceTracker.get(quadrant).get(sourceIndex)[0] < j && j  j && j > parallelDimensionY / 2)) { sourceTracker.get(quadrant).get(sourceIndex)[0] = j; } if((sourceTracker.get(quadrant).get(sourceIndex)[1] < i && i  i && i > parallelDimensionX / 2)) { sourceTracker.get(quadrant).get(sourceIndex)[1] = i; } } } } for(int i = 0; i < parallelDimensionX; i++) { for(int j = 0; j < parallelDimensionY; j++) { int[] currPoint = mirroredPlanes.get(j).get(i); if(captain_position[0] == badguy_position[0] && currPoint[0] == captain_position[0] && currPoint[1] != badguy_position[1]) { continue; } if(captain_position[1] == badguy_position[1] && currPoint[1] == captain_position[1] && currPoint[0] != badguy_position[0]) { continue; } if(Math.pow(currPoint[0] - captain_position[0], 2) + Math.pow(currPoint[1] - captain_position[1], 2) <= distanceSquared) { int [] vecA = new int[] {currPoint[0] - captain_position[0], currPoint[1] - captain_position[1]}; double direction = Math.atan2(vecA[1], vecA[0]); int quadrant = 0; if(vecA[0] < 0) { quadrant++; } if(vecA[1] < 0) { quadrant += 2; } if(directions.get(quadrant).contains(direction)) { continue; } else { directions.get(quadrant).add(direction); } if(sourceDirections.get(quadrant).contains(direction)) { int index = sourceDirections.get(quadrant).indexOf(direction); int[] sourceIndex = sourceTracker.get(quadrant).get(index); int[] sourcePoint = mirroredSources.get(sourceIndex[0]).get(sourceIndex[1]); if(Math.pow(sourcePoint[0], 2) + Math.pow(sourcePoint[1], 2) < Math.pow(currPoint[0], 2) + Math.pow(currPoint[1], 2)) { continue; } } numDirections++; } } } return numDirections; } public static ArrayList<ArrayList> MirroredPlanes(int[] startingLocal, int[] planeDimensions, int[]mirrorDimensions) { ArrayList<ArrayList> mirroredPlanes = new ArrayList<ArrayList>(); //int[][int[][]] mirroredPlanes = new int[mirrorDimensions[0]][mirrorDimensions[1]]; int middleX = mirrorDimensions[0] / 2; int middleY = mirrorDimensions[1] / 2; for(int i = 0; i < mirrorDimensions[1]; i++) { ArrayList curXList = new ArrayList(); mirroredPlanes.add(curXList); for(int j = 0; j < mirrorDimensions[0]; j++) { int[] curY = new int[2]; int[] tempLocal = new int[]{startingLocal[0], startingLocal[1]}; int modX = j - middleX; int modY = i - middleY; if(modX % 2 != 0) { tempLocal[0] = planeDimensions[0] - startingLocal[0]; } curY[0] = tempLocal[0] + (modX * planeDimensions[0]); if(modY % 2 != 0) { tempLocal[1] = planeDimensions[1] - startingLocal[1]; } curY[1] = tempLocal[1] + (modY * planeDimensions[1]); curXList.add(curY); } } return mirroredPlanes; } 

}

我尝试过的东西目前不在代码中

• 检查是否激光击中角落
• 在警卫面前检查激光是否击中了机长

测试用例失败

 int[] dimensions = new int[] {42, 59}; int[] captain_position = new int [] {34, 44}; int[] badguy_position = new int[] {6, 34}; int distance = 5000; //Desired Output: ??? (Unknown) //Actual Output: 31694 (Incorrect) 

Answer 1

 int[] dimensions = new int[] {2, 5}; int[] captain_position = new int [] {1, 2}; int[] badguy_position = new int[] {1, 4}; int distance = 11; 

对于此测试，您的代码返回35，并且我接受（从今天起）代码返回27，希望较小的测试可以帮助您发现错误。

Answer 2

在这里你需要一些测试用例

 dimensions = [10,10] captain_position = [4, 4] badguy_position = [3,3] distance = 5000 

我没有使用java（我不讨厌）。 我不喜欢太多的规则。 顺便说一下ans = 739323

 dimensions = [23,10] captain_position = [6, 4] badguy_position = [3,2] distance = 23 ans = 8 

我不会发布代码或逻辑。 提示：你能看到阴影背后的敌人吗？ 环顾四周

Answer 3

我没有通过的唯一测试是测试10，我发现错误是在我的代码中测试了一个镜头是否会在坏人面前击中队长，所以开始调试那个区域。 为了给你一个测试案例，MWaw的例子

 int[] dimensions = new int[] {2, 5}; int[] captain_position = new int [] {1, 2}; int[] badguy_position = new int[] {1, 4}; int distance = 11; 

给了我这个问题与射击角度（作为向量）

 [-6, -3] [-4, -5] [-6, 5] [-4, -7]