1

I'm studying basic Java and I there's a question on a programming assignment that I'm having a lot of trouble with concerning recursive overloading of sort of a search method. Here's what I'm being asked to do:

Write a method that accepts a two-dimensional int[][] array as the parameter and searches for legal "paths" through it, starting at [0][0] and ending at the end of the array. (For instance if the array is declared [5][5] then the end would be [4][4]).

In order for a path to be legal, "jumps" must be performed between the cells until the end of the array is reached. If a path doesn't end at the end of the array, it isn't legal. Here's an example:

EX

The logic here is that a "jump" can be performed either to the right by the 10s and down by the 1s place of the number in the cell or vice versa, and the goal of the method is to return the number of legal pathways that exist through the array.

This wouldn't really be so much of a problem if it wasn't for the fact that the professor has several requirements for the assignment:

1) Absolutely no loops - the method must be carried out completely through recursion. 2) No global or constant variables 3) No changing the contents of the array or duplicating it 4) No creating or using other methods - overloading is encouraged (and probably required at this point) but writing a new method to assist in the process is out of the question.

Here's what I have so far:

public class Question4 {
//step 1 - location: [0][0]
    public static int countPaths(int[][] mat) {
        int current = mat[0][0];
        //case 1: x < 10
        if(current < 10) {
            //check right
            if(current < mat.length-1) {
                return countPaths(mat, current, 0, 0);
            }
            //check left
            if(current < (mat[0].length-1)) {
                return countPaths(mat, 0, current, 0);
            }
        //case 2: x >= 10
        } else if(current >= 10) {
            int tens = (int)(Math.floor(current / 10));
            int ones = current % 10;

            //check down by 10s, right by 1s
                if(tens < mat.length-1 && ones < mat[0].length-1) {
                return countPaths(mat, tens, ones, 0);
            }

            //check right by 10s, down by 1s
            if(ones < mat.length-1 && tens < mat[0].length-1) {
                return countPaths(mat, ones, tens, 0);
            }
        }

        return 0;
    }

    //step 2 - two options: down by 10s, right by 1s / right by 10s, down by 1s
    public static int countPaths(int[][] mat, int r, int c, int paths) {
        //check if the end of the array has been reached
        if(r == mat.length-1 && c == mat[r].length-1) {
            return paths + 1;
        } else {
            int current = mat[r][c], tens = (int)Math.floor(current / 10), ones = current % 10;

            //check down by 10s, right by 1s
            if(r + tens < mat.length-1 && c + ones < mat[r].length-1) {
                return countPaths(mat, r + tens, c + ones, paths);
            }

            //check down by 1s, right by 10s
            if(r + ones < mat.length-1 && c + tens < mat[r].length-1) {
                return countPaths(mat, r + ones, c + tens, paths);
            } else {
                return paths;
        }
    }
  }
}

I do apologize for the long question - I've been stuck on this thing for a week and haven't been able to figure it out.

The array in the photo should give a result of 3 possible paths, but every time I run the method I get 0.

Any help at all would be greatly appreciated. Thank you :)

Improve this question

3 Answers 3

Reset to default
1

I fixed the code. Essentially I'd been going about the problem all wrong: I was missing a case check. What I mean is that there are four possible outcomes for each subsequent recursion of the method:

  1. The end of the array has been reached and the returned value should be 1.
  2. A jump that goes down by the tens place and right by the ones place is legal but the reverse is not true.
  3. A jump that goes down by the ones place and right by the tens place is legal but the reverse is not true.
  4. Both of the aforementioned jumps are legal.

All I had to do once I realized that was to write a series of cascading if statements, each of which return a different value for the recursive function. What I didn't understand before is that a return statement could contain more than one recursive call, which enables me to run the method again for each case simultaneously in a "divide-and-conquer" sort of way.

The resulting code is:

public class Paths {
public static int countPaths(int[][] a) {
    //declare method variables
    int start = a[0][0], tens = start / 10, ones = start % 10;
    boolean downByTens, downByOnes;

    //set the case booleans
    if(tens <= a.length-1 && ones <= a[tens].length-1) {
        downByTens = true;
    } else {
        downByTens = false;
    }

    if(ones <= a.length-1 && tens <= a[ones].length-1) {
        downByOnes = true;
    } else {
        downByOnes = false;
    }

    //check the cases, return the overloaded method
    if(downByTens) {
        if(downByOnes) {
            return countPaths(a, tens, ones) + countPaths(a, ones, tens);
        } else {
            return countPaths(a, tens, ones);
        }
    } else {
        if(downByOnes) {
            return countPaths(a, ones, tens);
        } else {
            return 0;
        }
    }
}

private static int countPaths(int[][] a, int row, int col) {
    //declare method variables
    int current = a[row][col], tens = current / 10, ones = current % 10, end = a[a.length-1][a[0].length-1];
    boolean downByTens, downByOnes;

    //set the case booleans
    if(row + tens <= a.length-1 && col + ones <= a[row + tens].length-1) {
        downByTens = true;
    } else {
        downByTens = false;
    }

    if(row + ones <= a.length-1 && col + tens <= a[row + ones].length-1) {
        downByOnes = true;
    } else {
        downByOnes = false;
    }

    //check to see if the end of the array has been reached
    if(current == end) {
        return 1;
    } else {
        //check the cases
        if(downByTens) {
            if(downByOnes) {
                return countPaths(a, row + tens, col + ones) + countPaths(a, row + ones, col + tens);
            } else {
                return countPaths(a, row + tens, col + ones);
            }
        } else {
            if(downByOnes) {
                return countPaths(a, row + ones, col + tens);
            } else {
                return 0;
            }
        }
    }
}
}

When I ran the method countPaths(int[][] array) on the array in the picture I posted in the original question, the returned result was 3, which is the correct answer.

Special thanks to Imchpers who helped me with this code two weeks ago. I hope this answer helps others who are struggling with these kinds of recursive functions in any language.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Why do you need all this code in the overload function? returning: countPaths(a,0,0) works just fine because 0 + tens/ones = tens/ones
0

here is my updated list of conflicts now that I've had time to review the code.

Your first problem as I discussed below is here:

        //check down by 10s, right by 1s
        if(r + tens < mat.length-1 && c + ones < mat[r].length-1) {
            return countPaths(mat, r + tens, c + ones, paths);
        }

        //check down by 1s, right by 10s
        if(r + ones < mat.length-1 && c + tens < mat[r].length-1) {
            return countPaths(mat, r + ones, c + tens, paths);
        } else {
            return paths;
        }

When your program goes from countPaths(mat) to countPaths(mat, r, c, paths), the initial location at this step is mat[1][2]. When you perform the second if condition after the first one returns paths = 1, this if condition fails to hold true (as it should) and it returns the else { return paths; }. Because the paths at this step still equals 0, this returns paths = 0 which overrides your previous work done in the previous recursive return.

Once this program finishes this step, it will return to countPaths(mat) which has the return value from countPaths(mat, r, c, paths) of 0. Because this method received a valid return, it will exit at this point and won't continue on to the next if condition here:

        //check down by 10s, right by 1s
            if(tens < mat.length-1 && ones < mat[0].length-1) {
            return countPaths(mat, tens, ones, 0);
        }

        //check right by 10s, down by 1s (this if condition)
        if(ones < mat.length-1 && tens < mat[0].length-1) {
            return countPaths(mat, ones, tens, 0);
        }

These are your two main problem areas which will require a bit of work to fix the code to solve. My first main suggestion is having ONE return in your countPaths(mat) function which will return countPaths(mat, ones, tens, 0) starting at the initial location instead of at mat[1][2]. Let your recursive function deal with all the jumps; don't try to do initial handling in the first function. Once you get that part refactored, I think everything else will fall into place and you can make progress in other small problem areas. Please feel free to come back here & edit your question and/or add a comment if you run into problems afterwards.

Good luck!

Improve this answer

8 Comments

Thank you for the speedy response. I don't think what you're saying makes a whole lot of sense since the values for ones and tens are determined by what's actually in the cell and not its index ([r][c]). For example: in the picture, the starting point is [0][0] and the value is 12, so current = 12, tens = 1, ones = 2.
Here's what I get for the first tracethrough using mat[0][0] as my initial value: current 12; tens = 1; ones = 2 countPaths(mat, 1, 2, 0) current = 21; tens = 2; ones = 1 r + tens = 1+2; c + ones = 2+1 countPaths(mat, 3, 3, 0) current = 20; tens = 2; ones = 0 r + tens = 3+2; c + ones = 3+0 countPaths(mat, 5, 3, 0) paths + 1 = 1 Assuming I did this right, your initial value should give a 1 as a return value. Can you confirm this? Also, I'm assuming there is an external class that is calling your functions? Right now it should stop as soon as it finds a single path.
Getting it to recognize that one path would be nice, but I'm still getting 0 as the return. And yes there is an external class calling the method but only as a test - all I have to hand in is the class itself.
Your problem is here: //check down by 1s, right by 10s if(r + ones < mat.length-1 && c + tens < mat[r].length-1) { return countPaths(mat, r + ones, c + tens, paths); } else { return paths; } After the first return statement that i traced through returns 1, it will go and execute this part of the code. But, you get a case here starting at [0][0] that causes the if to return a false, thus you return paths which is a 0 and causes the function to return a 0 overriding the 1.
Okay, but that doesn't solve the problem of not finding all the paths. Man, this is tough. I can't figure out how to get it to finish the path and then go back to the second or third recursion to find new paths after the first.
|
0 
 public static int countP(int a[][],int x,int y,int count)
 {
     if(row==(a.length-1) &&(cell==a[0].length-1)) {count++;
         return 1; }


if(x<a.length  && y<a[0].length )
         {
              System.out.println("cell ["+x+"]["+y+"]="+a[x][y]);

             int tmp1=a[x][y]%10;
             int tmp2=a[x][y]/10;
          return (countP(a,x+tmp1,y+tmp2,count) +countP(a, x+tmp2, t+tmp2, count));
        }    
     return 0;

 }

i see this question on programming course 20441 Intro to CS. i guess they many similar Recursive Question in the world

now days i finish project on "System Programming Laboratory
(C Unix Writing Compiler for Assembler ..(without linker) )

Liran Franco [email protected]

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.