java - 谷歌 Foobar : Bringing a Gun to a Guard Fight

Question

我的情况

我断断续续地为这项挑战工作了大约 9 天，但我没有想法。到目前为止，我的解决方案通过了 9/10 个测试用例。我优化的解决方案运行得足够快，所以错误是实际的解决方案，而不是计算时间用完了。如果有人能告诉我我遗漏了什么或者我的算法没有真正解决给定的问题，我将不胜感激。此外，我意识到我的一些代码并不完美 - 我计划在找到可行的解决方案后修复所有问题。

问题

呃哦 - 你被 Lambda 指挥官的一名精英卫兵逼到了绝境!幸运的是，你在穿过车站时从一个废弃的哨所里捡到了一把光束武器，所以你有机会杀出一条血路。但是光束武器对你和精英守卫都有潜在的危险:它的光束会反射墙壁，这意味着你必须非常小心地射击，以免弹射到自己身上!

幸运的是，光束在变得太弱而无法造成损坏之前只能行进一定的最大距离。您还知道，如果光束击中一个角，它会以完全相同的方向反弹回来。当然，如果光束击中您或 guard ，它会立即停止(尽管很痛苦)。

写一个函数 answer(dimensions, your_position, guard_position, distance) 给出房间宽度和高度的 2 个整数数组，房间中 x 和 y 坐标的 2 个整数数组，守卫在房间中的 x 和 y 坐标的 2 个整数，并返回一个整数，表示您可以发射以击中精英守卫的不同方向的数量，给定光束可以传播的最大距离。

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

例如，如果你和精英守卫被安置在一个尺寸为 [3, 2]、you_position [1, 1]、guard_position [2, 1] 且最大射击距离为 4 的房间中，则你可以射击在七个不同的方向击中精英守卫(以你所在位置的 vector 方位角给出):[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<Double>> directions = new ArrayList<ArrayList<Double>>();
    ArrayList<ArrayList<Double>> sourceDirections = new ArrayList<ArrayList<Double>>();
    ArrayList<ArrayList<int[]>> sourceTracker = new ArrayList<ArrayList<int[]>>();
    
    for(int i = 0; i < 4; i++) {
        
        directions.add(new ArrayList<Double>());
        sourceDirections.add(new ArrayList<Double>());
        sourceTracker.add(new ArrayList<int[]>());
    }       
    
    ArrayList<ArrayList<int[]>> mirroredPlanes = MirroredPlanes(badguy_position, dimensions, new int[]{parallelDimensionX, parallelDimensionY});
    ArrayList<ArrayList<int[]>> 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 < parallelDimensionY / 2) || (sourceTracker.get(quadrant).get(sourceIndex)[0] > j && j > parallelDimensionY / 2)) {
                    
                    sourceTracker.get(quadrant).get(sourceIndex)[0] = j;
                }
                
                if((sourceTracker.get(quadrant).get(sourceIndex)[1] < i && i < parallelDimensionX / 2) || (sourceTracker.get(quadrant).get(sourceIndex)[1] > 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<int[]>> MirroredPlanes(int[] startingLocal, int[] planeDimensions, int[]mirrorDimensions) {
    
    ArrayList<ArrayList<int[]>> mirroredPlanes = new ArrayList<ArrayList<int[]>>();
    
    //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<int[]> curXList = new ArrayList<int[]>(); 
        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; 
}

我尝试过但目前不在代码中的事情

• 检查激光是否击中角落
• 检查激光是否先于 guard 击中队长

失败的测试用例

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，希望较小的测试可以帮助您发现错误。