This week's book giveaway is in the Big Data forum. We're giving away four copies of Elasticsearch in Action and have Radu Gheorghe & Matthew Lee Hinman on-line! See this thread for details.

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 .

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

posted

0

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

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

posted

0

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

posted

0

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

posted

0

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

posted

0

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.