aspose file tools*
The moose likes Beginning Java and the fly likes finding all routes Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "finding all routes" Watch "finding all routes" New topic
Author

finding all routes

S Ali
Ranch Hand

Joined: Aug 23, 2009
Posts: 129
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.





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


SCJP 6
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36563
    
  16
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
Ranch Hand

Joined: Aug 23, 2009
Posts: 129

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

Joined: Jan 17, 2006
Posts: 1296
This seems like a perfect application for a recursive algorithm. Have you learned about recursion yet?


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
S Ali
Ranch Hand

Joined: Aug 23, 2009
Posts: 129
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
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
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:



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
Ranch Hand

Joined: Aug 23, 2009
Posts: 129
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
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: finding all routes
 
Similar Threads
Arrays
Wrapper class array and Garbage Collection
Sort the Array in reverse order
Parallel running quicksort
how to use array in array?