How to find the shortest path in a puzzle with keys and doors

Question

I tried the below code, but it didn't give me the right answer.

Here is the problem statement.

Suppose you have a 2-D grid. Each point is either land or water. There is also a start point and a goal.

There are now keys that open up doors. Each key corresponds to one door.

Implement a function that returns the shortest path from the start to the goal using land tiles, keys and open doors.

Data Representation

The map will be passed as an array of strings.

A map can have the following tiles.

0 = Water 1 = Land 2 = Start 3 = Goal uppercase = door lowercase = key

The grid can be like this:

            {{'0', '2', '1', '1', '1'},
            {'0', '1', '0', '0', '1'},
            {'0', '0', '0', '0', '1'},
            {'0', '0', 'A', '0', '1'},
            {'1', '1', 'a', '1', '1'},
            {'1', 'b', '0', '0', 'B'},
            {'1', '1', '0', '0', '1'},
            {'0', '1', '0', '0', '3'}};

So the shortest path should be: 01->02->03->04->14->24->34->44->43->42->41->51->41->42->43->44->54->64->74

And my codes go like:

public class shortestPath {
    static int shortest = Integer.MAX_VALUE;
    static String path = "";
    static ArrayList<ArrayList<int[]>> res = new ArrayList<ArrayList<int[]>>();

    public static void main(String[] args) {
        char[][] board = {{'0', '2', '1', '1', '1'},
                {'0', '1', '0', '0', '1'},
                {'0', '0', '0', '0', '1'},
                {'0', '0', 'A', '0', '1'},
                {'1', '1', 'a', '1', '1'},
                {'1', 'b', '0', '0', 'B'},
                {'1', '1', '0', '0', '1'},
                {'0', '1', '0', '0', '3'}};
        System.out.println(findShortest(board));
        System.out.println(path);

    }

    public static int findShortest(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return 0;
        int row = board.length;
        int col = board[0].length;
        int[] start = new int[2];
        int[] end = new int[2];
        int[][] visited = new int[row][col];
        HashMap<Character, ArrayList<int[]>> hm = new HashMap<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == '2') {
                    start = new int[]{i, j};
                }
                if (board[i][j] == '3') {
                    end = new int[]{i, j};
                }
                if (Character.isUpperCase(board[i][j])) {
                    char key = Character.toLowerCase(board[i][j]);
                    if (hm.containsKey(key)) {
                        hm.get(key).add(new int[]{i, j});
                    } else {
                        ArrayList<int[]> al = new ArrayList<>();
                        al.add(new int[]{i, j});
                        hm.put(key, al);
                    }
                    board[i][j] = '0';
                }
            }
        }
        //HashSet<Character> hs = new HashSet<Character>();
        //helper2(board, hs, start[0], start[1], row, col, 0, visited, new StringBuilder(), new ArrayList<int[]>(), res);
        helper(board, hm, start[0], start[1], row, col, 0, visited, new StringBuilder());
        return shortest;
    }

    public static void helper(char[][] board, HashMap<Character, ArrayList<int[]>> hm, int r, int c, int row, int col, int count, int[][] visited, StringBuilder sb) {
        // System.out.println(r + " " + c);
        visited[r][c] = visited[r][c] + 1;
        sb.append(r).append(c).append("->");
        if (board[r][c] == '3') {
            System.out.println(count);
            if (shortest > count) {
                path = sb.deleteCharAt(sb.length() - 1).deleteCharAt(sb.length() - 1).toString();
                sb.append("->");
                shortest = count;
            }
            //return;
            //shortest = Math.min(shortest, count);
        }
        if (Character.isLowerCase(board[r][c])) {  // if this is the key;
            if (hm.containsKey(board[r][c])) {
                for (int[] i : hm.get(board[r][c])) {
                    board[i[0]][i[1]] = '1';
                }
            }
        }
        if (r + 1 < row && board[r + 1][c] != '0' && visited[r + 1][c] < 2) {
            helper(board, hm, r + 1, c, row, col, count + 1, visited, sb);
        }
        if (c + 1 < col && board[r][c + 1] != '0' && visited[r][c + 1] < 2) {
            helper(board, hm, r, c + 1, row, col, count + 1, visited, sb);
        }
        if (r - 1 >= 0 && board[r - 1][c] != '0' && visited[r - 1][c] < 2) {
            helper(board, hm, r - 1, c, row, col, count + 1, visited, sb);
        }
        if (c - 1 >= 0 && board[r][c - 1] != '0' && visited[r][c - 1] < 2) {
            helper(board, hm, r, c - 1, row, col, count + 1, visited, sb);
        }
        visited[r][c] = visited[r][c] - 1;
        sb.delete(sb.length() - 4, sb.length());
        if (Character.isLowerCase(board[r][c])) {  // if this is the key;
            if (hm.containsKey(board[r][c])) {
                for (int[] i : hm.get(board[r][c])) {
                    board[i[0]][i[1]] = '0';
                }
            }
        }
        return;
    }


}

Answer 1

Your problem is a combination of a bad implementation of the visited tracking and locked door tracking (managed by the hm variable, which is a very bad name, since the name doesn't help understand what the variable is/does).

Visited tracking

Your little robot is often walking back and forth over and over again. For example, if you insert a print statement for debugging to:

• Track and print the total number of forward steps tried
• Print the shortest path to goal whenever a shorter path is found
• Print the longest path attempted whenever a longer path is found

You get the following result, where ! means longer path walked, and * means shorter path to goal found:

     1: ! 01->
     2: ! 01->11->
     3: ! 01->11->01->
     4: ! 01->11->01->11->
     6: ! 01->11->01->02->03->
     7: ! 01->11->01->02->03->04->
     8: ! 01->11->01->02->03->04->14->
     9: ! 01->11->01->02->03->04->14->24->
    10: ! 01->11->01->02->03->04->14->24->34->
    11: ! 01->11->01->02->03->04->14->24->34->44->
    12: ! 01->11->01->02->03->04->14->24->34->44->34->
    13: ! 01->11->01->02->03->04->14->24->34->44->34->44->
    14: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->
    15: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->
    16: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->
    17: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->
    18: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->32->
    20: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->
    21: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->
    22: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->
    23: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->
    24: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->71->
    26: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->
    27: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->
    28: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->
    29: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->
    30: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->
    31: ! 01->11->01->02->03->04->14->24->34->44->34->44->43->42->43->42->41->51->61->71->61->51->41->40->50->60->50->60->
  9577: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->41->42->43->44->54->64->74->
  9611: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->
  9612: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
  9613: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
  9623: ! 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->34->24->14->04->03->02->
  9901: * 01->11->01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->
 19141: ! 01->11->01->02->03->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
 53941: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
 53942: ! 01->11->01->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
145776: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->
145777: ! 01->11->01->02->03->02->03->04->14->04->14->24->34->24->34->44->43->42->41->51->61->71->61->51->50->60->50->40->41->42->43->44->54->64->74->64->74->
158937: * 01->02->03->04->14->24->34->44->43->42->41->51->61->51->41->42->43->44->54->64->74->

Total number of forward steps taken: 390236

That longest path is going back and forth a lot:

01->11->
01->02->03->
    02->03->04->14->
            04->14->24->34->
                    24->34->44->43->42->41->51->61->71->61->
                                            51->50->60->
                                                50->40->41->42->43->44->54->64->74->
                                                                            64->74->

That's a lot of wasted walking.

Locked door tracking

Recap of your logic: You initially change all door to 0 (Water). When you encounter a key, you unlock all the doors that fit the key, by changing the board values to 1 (Land). When backtracking, you change all the doors back to 0 (Water).

Now look at the solution your code came up with:

01->02->03->04->14->24->34->44->43->42->41->51->61->
                                            51->41->42->43->44->54->64->74

Problem is that the key is at 51, so when the code backtracks from that solution over the second 51, it closes the door, so that when it gets back to the first 51 and attempts to walk directly to the goal from there, the door is closed, even though you have the key.

That is because you don't realize you have the key twice.

Solution

If you just fix the visited tracking, your code will work, since you won't step on the same key twice.

If you just fix the locked door tracking, i.e. track that you have multiple copies of the same key, your code will work, since you won't prematurely lock the doors again.

However, consider the following for your revised solution:

• What if there is actually more than one of the same key?
• Don't visit a location repeatedly, unless you've picked up a new key.
• Don't keep walking if you're on a path that's already longer than the shortest path-to-goal found so far.

So, one way to do this differently, is to think of how it would work in real life. You don't unlock a door when you find the key, because 1) you don't necessarily know where the door is yet, and 2) you can't reach the door from where you're standing.

Instead, keep a key ring. When you encounter a key you don't have, add it to the key ring. Adding a new key to the key ring also means that you can re-visit previously walked areas. When you encounter a door, you can walk through it if you have the key in the key ring.

Since there are 26 possible keys, an int value with 32 bits can be your key ring.

See IDEONE for sample implementation that only takes 90 steps (not the 390236 steps of your current code) to check all possible/relevant paths.