finding all routes

[S Ali]

Hi all,
I'm stuck with this problem trying to find an algorithm for it. I have a triangle like this:

1
1 2
1 2 3
1 2 3 4

I need to find all possible routes starting from the top of the triangle "1" till the bottom ,giving that I can only go left or right to the number.
For example the routes for the above triangle are:
1 1 1 1
1 1 1 2
1 1 2 2
1 2 2 2
1 2 2 3
1 2 3 3
1 2 3 4


what I did so far is implement the triangle in a two dimension array, and I did a for loop to get the following left or right number of each number of the array.
Please help I seem to be getting nowhere.

 
public class tri {
	public static void getRoutes (int [][] arr)
	{
		int leftInt=0;
		int rightInt=0;
		for(int i =0;i<arr.length;i++)
		{
		for (int j=0;j<arr[i].length;j++)
		{
		if(i<arr.length-1)
		{
		leftInt = arr[i+1][j];
		rightInt = arr[i+1][j+1];
		System.out.println(arr[i][j]+" ");
		System.out.println("left:"+ leftInt);
		System.out.println("right:"+rightInt);
		}
		}
		System.out.println("***********");
		}
		}
	
		
	
	
	public static void main(String[] args) {
		int [][] arr = new int[4][];
		arr[0]= new int []{1};
		arr[1]= new int []{1,2};
		arr[2]= new int []{1,2,3};
		arr[3]= new int []{1,2,3,4};
		getRoutes(arr);	
	}

}


   

P.S :The triangle is supposed to be in a triangle shape but it gets messed up when I post it .

[Campbell Ritchie]

What you have posted appears only to go down or right, not left or right.
You will have to be very specific about what you want; write down on a piece of paper exactly how you intend to traverse your triangle, then refine it until you have it all in very short words. Then you can try writing some code.

[S Ali]

I'm sorry it got messed up when I posted it, this is what I'm trying to achieve.

[Garrett Rowe]

This seems like a perfect application for a recursive algorithm. Have you learned about recursion yet?

[S Ali]

No sadly I've been trying to learn it for a couple of days now, I get confused and don't understand what to return and what to do. I would really appreciate it if you can guide me through it.

[Garrett Rowe]

To use the recursive algorithm, you'll have to adjust your method signature somewhat to pass in the 'root' element for each recursive call. And if you want to stick with the int[][] representation of the triangle you'll need to add some helper methods to help with some of the housekeeping. But the algorithm itself is simple:

public int[][] getRoutes(int rootX, int rootY, int[][] triangle) {
   int root = triangle[rootX][rootY];
   int lefts = prependAll(root, getRoutes(/*left subroot*/));
   int rights = prependAll(root, getRoutes(/*right subroot*/));
   return combine(lefts, rights);
}


//elsewhere
public static void main(String[] args) {
   printRoutes(getRoutes(0, 0, triangle));
}

Obviously there are some details left out here, like implementations of the prependAll(), combine() and printRoutes() methods. And you'll have to figure out how to handle the recursion base case. But basically that's the meat of the entire recursive algorithm.


Edit: changed addAll() to prependAll() to more clearly express intent.

[S Ali]

The thing is I would have to create a number of arrays representing the different routes, how can I pass them around inside the method to add to them without getting them confused .

[Garrett Rowe]

That's the thing, you don't have to create a bunch of arrays and keep track of them. The recursion does that for you. All you have to worry about is implementing the prependAll(int, int[][]) method. It won't be the most efficient algorithm, but it will be easy to understand. A Stack<Integer> would be slightly more efficient.