3
\$\begingroup\$

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game.

I am representing the board as a matrix as follows. If the value at a cell is 0, you could go to any of the next 6 places using your magic die. If the value at a cell is non-zero, you compulsorily have to go to the cell that is represented by the value (think there is a snake or ladder at that cell which is taking you to the cell represented by the value). For example, if you land at (0,1), you are forced to go to 11, which is (2,1).

int[][] a = {
                     {0,11,0,0,0},
                     {0,0,0,0,0},
                     {0,0,1,23,0},
                     {0,0,4,0,0},
                     {10,0,0,0,0}
        };

Background

I have implemented this using Depth First Search / Recursion. Someone who reviewed my code said this solution is incorrect, and this problem is not a good candidate for Depth First Search / Recursion, and can only be done by using Breadth First Search, the reason being that, there are cells which are interdependent on each other. For example, this is a valid path, (0,0) -> (0,1) -> (2,1) -> (2,2) -> (0,1). However, you are trying to find the minimum number of hops from each cell, and here, (0,1) depends on (2,1) which in turn depends on (0,1).

I am not completely sure this is a valid argument, since if you go from (0,1) to (2,1), there is no reason, to go back to (0,1) since it anyways cannot be the shortest path, since if you go back, you're basically going back to a point you previously were in except that you have made two more hops. So, this is not useful, and I have handled this by using a visited[][] state to capture that.

public class SnakesAndLadders {

    /**
     * @param args
     */
    public static void main( String[] args ) {
        // TODO Auto-generated method stub
        int[][] a = {
                     {0,11,0,0,0},
                     {0,0,0,0,0},
                     {0,0,1,23,0},
                     {0,0,4,0,0},
                     {10,0,0,0,0}
        };
        boolean[][] visited = new boolean[a.length][a[0].length];

        System.out.println( shortestPath( a, 0, 0, visited ) );
    }

    static int shortestPath(int[][] a, int i, int j, boolean[][] visited)
    {
        if(i >= a.length || j >= a[0].length)
            return Integer.MAX_VALUE-100;

        if( i == a.length-1 && j == a[0].length-1)
            return 0;

        if(visited[i][j] == true )
            return Integer.MAX_VALUE-100;

        visited[i][j] = true;
        int min = Integer.MAX_VALUE-100;
        if(a[i][j] == 0)
        {
            int pos = i*a[0].length + j;    
            for(int k = pos+1;k<=pos+6;k++)
            {
                min = Math.min( min, shortestPath( a, k/a[0].length, k%a[0].length, visited ) + 1) ;
            }

        }
        else
            return shortestPath( a, a[i][j]/a[0].length, a[i][j]%a[0].length, visited ) + 1;

        visited[i][j] = false;
        return min;
    }
}

Please review my code, and give me your thoughts on whether this would work, or if depth first search cannot be used for this class of problems where you could go back to a previous recursion state.

\$\endgroup\$
  • \$\begingroup\$ "and give me your thoughts on whether this would work" Did you try? Did it work? \$\endgroup\$ – Mast Nov 24 '16 at 8:00
1
\$\begingroup\$

I don't believe your depth-first approach is incorrect, as far as I can tell your visited variable does its job. However, there is room for improvement.

General improvents to readability
Firstly, this game's board can be represented by a linear tape of cells, rather than a two-dimensional grid. Using a one-dimensional array greatly simplifies the code. Only one position variable will be passed around instead of two. Additionally, the translation steps between coordinate systems that you're currently making (e.g.: int pos = i*a[0].length + j;) are eliminated.

Likely bugs
The aim is to count the minimum number of dice rolls, but you're also incrementing min when you use a snake or ladder. I think you should remove the + 1 in the else branch.

You're currently using the magic number 100, here: Integer.MAX_VALUE-100. There is no explanation as to where this 100 comes from, why it needs to be exactly that number. I assume it's to prevent interger wrapping when taking a sum. However, this exposes you to bugs. What if you use this program on a larger board that has paths longer than a 100 rolls? Your program now thinks the most optimum route is done in negative two billion rolls.

The current implementation assigns a special meaning to the value zero (no snake or ladder). However, position zero is a valid cell. This means that there is no way for a snake to point towards the cell at zero! One workaround would be to change the default value to -1.

Nitpicks
I recommend always using brackets with conditional blocks, even if there's just one line. Read this for more information.

\$\endgroup\$
  • \$\begingroup\$ @A Boschman thanks for reviewing my code. All suggestions taken, but I have a follow up question. You're correct in understanding my thought process behind using the magic number, Integer.MAX_VALUE-100, cuz sometimes I do Integer.MAX_VALUE + 1, which becomes Integer.MIN_VALUE, which can never be beaten for minimum. How do you suggest I fix this for this problem, and similar recursion/DP problems where I assign min to be positive infinity initially? \$\endgroup\$ – learningboy Nov 24 '16 at 15:57
  • \$\begingroup\$ @learningboy The simplest way I can think of is just to return MAX_VALUE and make it part of the method specification. Then you can check for that value before incrementing. Also, I'm starting to doubt whether the solution is correct after all. You don't set visited back to false after you use a snake or ladder. \$\endgroup\$ – A Boschman Nov 25 '16 at 9:52
  • \$\begingroup\$ @learningboy If you're interested, another really cool way of looking at this problem is too see each cell on the board as a node that is connected to up to six other nodes. Then you can use Dijkstra's algorithm to determine the shortest path between the starting and ending node. en.wikipedia.org/wiki/Dijkstra's_algorithm \$\endgroup\$ – A Boschman Nov 25 '16 at 10:13
  • \$\begingroup\$ @A Boschman I don't think we need dijsktra's algorithm here, since all edges are unweighted. \$\endgroup\$ – learningboy Nov 25 '16 at 16:24
  • \$\begingroup\$ @learningboy It's probably overkill, and I'm by no means an expert on the subject. But a snake/ladder edge could have a weight/cost of zero and a dice edge a weight of 1, if that's what you meant. \$\endgroup\$ – A Boschman Nov 26 '16 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.