Когда приведенный ниже код генерирует исключение нулевого указателя? (Более эффективный альтернативный код также приветствуется)
Я только что провалил задание 4 уровня Google Coding на сайте foobar. Мой код работает большую часть времени, но выдает исключение нулевого указателя для определенного набора входных данных, о которых я не знаю. Если кто-то заинтересован в решении вопроса о кодировании головоломки, не могли бы вы помочь мне найти входные данные, для которых приведенное ниже решение заканчивается исключением из нулевого указателя? Я также приветствую комментарии к моему коду, когда он не соответствует нормам этикета или всего другого простого и более эффективного решения. Поблагодарить. (PS- Надеюсь, что я не нарушаю никаких правил и материалов, разделяя приведенный ниже вопрос, заданный в задаче Google Coding)
Постановка проблемы. Учитывая начальные номера комнат групп кроликов, номера комнат спасательных капсул и количество кроликов, которые могут проходить одновременно в каждом направлении каждого коридора между ними, определите, сколько кроликов может безопасно сделать это. к спасательным капсулам за раз на пике. Напишите ответ функции (входы, выходы, путь), который принимает массив целых чисел, обозначающих, где находятся группы собранных кроликов, массив целых чисел, обозначающих, где расположены escape-контейнеры, и массив массивов целых чисел коридоров, возвращает общее количество кроликов, которые могут пройти на каждом временном шаге, в виде целого числа. Входы и выходы не пересекаются и поэтому никогда не будут пересекаться. Элемент path path[A][B] = C описывает, что коридор, идущий от A до B, может вмещать кроликов C на каждом временном шаге. Существует не более 50 комнат, соединенных коридорами, и не более 2000000 кроликов, которые подойдут одновременно.
Например, если у вас есть:
entrances = [0, 1],
exits = [4, 5],
path = [,
# Room 0: Bunnies, [0, 0, 4, 6, 0, 0],
# Room 1: Bunnies, [0, 0, 5, 2, 0, 0],
# Room 2: Intermediate room, [0, 0, 0, 0, 4, 4],
# Room 3: Intermediate room [0, 0, 0, 0, 6, 6],
# Room 4: Escape pods, [0, 0, 0, 0, 0, 0],
# Room 5: Escape pods [0, 0, 0, 0, 0, 0]
]
Затем на каждом временном шаге может произойти следующее:
0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3
1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3
2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5
3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5
Таким образом, в общей сложности 16 кроликов могли добраться до спасательных капсул в 4 и 5 на каждом временном шаге. (Обратите внимание, что в этом примере комната 3 могла бы отправить любую вариацию из 8 кроликов в 4 и 5, например, 2/6 и 6/6, но окончательный ответ остается тем же.)
Контрольные примеры
Inputs:entrances = [0], exits = [3], path = [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]] then Output:6
Inputs:entrances = [0, 1], exits = [4, 5], path = [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0] Output: 16
Мое решение:
public class Answer {
public static void main(String[] args) {
//input 1
int[] entrances = {0, 1};
int[] exits = {4, 5};
int[][] path = {{1, 0, 4, 6, 0, 0},
{0, 1, 5, 2, 0, 0},
{0, 0, 1, 0, 4, 4},
{0, 0, 0, 1, 6, 6},
{0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 1}};
System.out.println("*****************************************for input 1:"+answer(entrances, exits, path));
//input 2
entrances = new int[]{0};
exits = new int[]{3};
path = new int[][]{ {0, 7, 0, 0},
{0, 0, 6, 0},
{0, 0, 0, 8},
{9, 0, 0, 0} };
System.out.println("*****************************************for input 2:"+answer(entrances, exits, path));
//input with loop 1
entrances = new int[]{0,2};
exits = new int[]{4};
path = new int[][]{ {0, 3, 0, 0, 0},
{0, 0, 2, 0, 5},
{0, 0, 0, 4, 0},
{0, 6, 0, 0, 0},
{0, 0, 0, 0, 0} };
System.out.println("*****************************************for input 3:"+answer(entrances, exits, path));
//input with loop 2
entrances = new int[]{0,1};
exits = new int[]{4,5};
path = new int[][]{ {0, 0, 10, 0, 0, 0},
{0, 0, 0, 8, 0, 0},
{0, 0, 0, 4, 6, 0},
{0, 0, 4, 0, 0, 12},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}};
System.out.println("*****************************************for input 4:"+answer(entrances, exits, path));
entrances = new int[]{0};
exits = new int[]{0};
path = new int[][]{ {0} };
System.out.println("*****************************************for input 5:"+answer(entrances, exits, path));
}
public static final int SOME_BIG_VALUE = 2146999999;
public static int answer(int[] entrances, int[] exits, int[][] path) {
if (path == null || entrances == null || exits == null){
return 0;
}
if(path.length<2 || entrances.length<1 || exits.length<1){
return 0;
}
//below makes difference with one test case
for (int i = 0; i < path.length; i++) {
for (int j = 0; j <path[i].length ; j++) {
if(i==j)
path[i][j]=0;
}
}
//creating all nodes
ArrayList<Node> nodes = new ArrayList<>();
for (int i = 0; i < path.length; i++) {
nodes.add(new Node(i));
}
Node.constructGraph(path, nodes);
int total = 0;
for(int src:entrances) {
//System.out.println("for src: "+ src);
Node start = nodes.get(src);
int pathCapacity = 0;
do {
if(start.discard)
break;
pathCapacity = findCapacityOfLoopLessPath(src, exits, nodes);
total = total + pathCapacity;
} while (pathCapacity != 0);
}
return total;
}
/**
*Returns >0 if valid path is found between src and one of the exits
* Returns 0 if valid path is not found between src and any of exits
* Apart, below function *overcomes the loop while finding the path
*alters graph as new paths are discovered
*removes dead-end path frm src to non-exit
*/
public static int findCapacityOfLoopLessPath(int src, int[] exits, ArrayList<Node> nodes) {
ArrayList<Node> path = new ArrayList<>();
Stack<Node> stack = new Stack<>();
Node start = nodes.get(src);
stack.push(start);
boolean reachedExit = modifiedDFS(path, stack, exits);
int smallestCorridorSizeInPath = 0;
if(!reachedExit){
return smallestCorridorSizeInPath;
}
else{
smallestCorridorSizeInPath = findSmallestCorridorSizeInPath(path);
if(smallestCorridorSizeInPath != SOME_BIG_VALUE) {
reduceCorridorSizeInPath(path, smallestCorridorSizeInPath, exits);
return smallestCorridorSizeInPath;
}
}
return smallestCorridorSizeInPath;
}
/**
* Does dfs until one of the exit is reached
* Parallelly putting nodes into path as they get discovered to reach the one of exits
*/
private static boolean modifiedDFS(ArrayList<Node> path, Stack<Node> stack, int[] exits) {
while(!stack.empty()) {
Node current = stack.pop();
if(Node.isNodeInPath(current, path)) {
return modifiedDFS(path,stack,exits);
}else {
path.add(current);
}
if(isNodeOneOfExits(current,exits)) {
return true;
}
HashMap<Node, Integer> corridorWeightToReachNextNode = current.getCorridorWeightToReachNextNode();
for(Node node:corridorWeightToReachNextNode.keySet()) {
if(!stack.contains(node) && !node.discard)
stack.push(node);
}
}
return false;
}
public static int findSmallestCorridorSizeInPath(ArrayList<Node> path) {
if(path.size() < 2){
return 0;//may be if exception is thrown then we can debug more easily
}
int smallestCorridorSizeInPath = SOME_BIG_VALUE;
//System.out.print("path : ");
for (int j = 0; j <path.size() ; j++) {
//System.out.print(path.get(j).toString()+", ");
}
int i;
for (i = 0; i < path.size()-1; i++) {
Node currentNode = path.get(i);
Node nextNode = path.get(i+1);
HashMap<Node, Integer> corridorWeightToReachNextNode = currentNode.getCorridorWeightToReachNextNode();
if(corridorWeightToReachNextNode.get(nextNode)<smallestCorridorSizeInPath) {
smallestCorridorSizeInPath = corridorWeightToReachNextNode.get(nextNode);
}
}
//System.out.println("shortest corridor size in the path:" + smallestCorridorSizeInPath);
return smallestCorridorSizeInPath;
}
/**
* reduce corridor size of each in path by smallestCorridorSizeInPath
* Removes the corresponding path with that smallest size from the graph
* by removing respective node with smallestCorridorSizeInPath from corridorWeightToReachNextNode
* Also, makes node.discard = true if node's nextNode list is empty
*/
public static void reduceCorridorSizeInPath(ArrayList<Node> path, int smallestCorridorSizeInPath, int[] exits) {
if(path == null || exits == null){
return;
}
if(path.size()<2 && exits.length==0)
return;
for (int i = 0; i < path.size()-1 ; i++) {
Node currentNode = path.get(i);
Node nextNode = path.get(i+1);
if(currentNode==null || nextNode==null){
return;
}
HashMap<Node, Integer> corridorWeightToReachNextNode = currentNode.getCorridorWeightToReachNextNode();
if(corridorWeightToReachNextNode==null || corridorWeightToReachNextNode.size()==0) {
return;
}
if(corridorWeightToReachNextNode.get(nextNode)==null) {
return;
}
int currentCorridorSize = 0;
currentCorridorSize = corridorWeightToReachNextNode.get(nextNode);
if(currentCorridorSize==0 || currentCorridorSize == SOME_BIG_VALUE){
return;
}
corridorWeightToReachNextNode.put(nextNode, (currentCorridorSize-smallestCorridorSizeInPath));
if(currentCorridorSize == smallestCorridorSizeInPath) {
corridorWeightToReachNextNode.remove(nextNode);
if(corridorWeightToReachNextNode.size()==0 && !isNodeOneOfExits(currentNode,exits)) {
currentNode.discard = true;
//System.out.println("discarded node:"+ currentNode.toString());
}
}
}
}
public static boolean isNodeOneOfExits(Node node, int[] exits) {
for (int i = 0; i < exits.length; i++) {
if(node.getIndex() == exits[i])
return true;
}
return false;
}}
class Node {
int index;
HashMap<Node, Integer> corridorWeightToReachNextNode = null;
Boolean discard = false;
public Node(int index) {
this.index = index;
corridorWeightToReachNextNode = new HashMap<>();
}
public int getIndex() {
return index;
}
public HashMap<Node, Integer> getCorridorWeightToReachNextNode() {
return corridorWeightToReachNextNode;
}
public static Node constructGraph(int[][] matrix, List<Node> nodes) {
for(int i = 0; i < matrix.length; i++) {
Node currentNode = nodes.get(i);
for(int j=0; j<matrix[i].length; j++) {
if(matrix[i][j] != 0) {
Node nextNode = nodes.get(j);
currentNode.corridorWeightToReachNextNode.put(nextNode,matrix[i][j]);
}
}
}
return nodes.get(0);
}
@Override
public boolean equals(Object obj) {
Node node = (Node)obj;
if(node.index == this.index)
return true;
return false;
}
@Override
public int hashCode() {
return index % 2;
}
@Override
public String toString() {
return Integer.toString(this.index);
}
public static boolean isNodeInPath(Node n, ArrayList<Node> path) {
if(path == null || n == null) {
return false;
}
boolean alreadyInPath = false;
for( Node nodeInPath : path) {
if(nodeInPath.equals(n))
return true;
}
return false;
}
}
1 ответ
Ваша проблема: созданный вами путь содержит узлы без выхода.
Следующий пример (найден случайной выборкой):
entrances = {0};
exits = {3};
path = {{0, 17, 6, 0},
{0, 0, 0, 0},
{0, 0, 0, 9},
{16, 0, 0, 0}};
Визуализация (создано с помощью graphonline.ru)
Ваш код начинается с (единственного) узла входа. Это добавляет все дочерние элементы к пути в порядке встречи. Затем он исследует каждого ребенка и добавляет своих детей на путь. В конце, перед оценкой, это дает путь 0->1->2->3 что явно неправильно. Единственный верный путь 0->2->3 как указано на рисунке.
Во время оценки пути вы запрашиваете узел 1вектор смежности для узла 2, Это где ваше NullPointerException происходит.
Код, который я использовал для генерации случайных выборок (генерирует 1000 выборок с воспроизводимыми результатами и один узел входа / выхода)
// My random samples
Random random = new Random(0L);
int pathSize = 4;
for (int i = 0; i < 1000; i++) {
entrances = new int[]{0};
//Arrays.setAll(entrances, j -> random.nextInt(0+1));
exits = new int[]{pathSize - 1};
//Arrays.setAll(exits, j -> random.nextInt(pathSize));
path = new int[pathSize][pathSize];
Arrays.setAll(path, j -> IntStream.generate(() -> random.nextInt(20)).limit(pathSize).toArray());
for (int j = 0; j < path.length; j++) {
path[j][j] = 0;
}
for (int j = 0; j < path.length; j++) {
for (int k = 0; k < path[j].length; k++) {
path[j][k] = random.nextDouble() < 0.75 ? 0 : path[j][k];
}
}
try {
answer(entrances, exits, path);
} catch (Exception e) {
System.err.println("[" + String.format("%02d", i) + "] Threw an exception for inputs " + Arrays.toString(entrances) + ", " + Arrays.toString(exits) + ", " + Arrays.deepToString(path));
e.printStackTrace();
}
}
Теперь немного случайного кода-обзора:
//below makes difference with one test case
for (int i = 0; i < path.length; i++) {
for (int j = 0; j < path[i].length; j++) {
if (i == j)
path[i][j] = 0;
}
}
Из того, что я вижу, path всегда квадратный массив Если это верно, вы можете удалить внутренний цикл.
У тебя есть SOME_BIG_VALUE, Почему бы не использовать Integer.MAX_VALUE? Вы не можете получить больше, чем это.