recursion problem

Hi guys (and girls too)

During my coding for this contest, I came across a problem which has bugged me since I started programming. Whenever I'm dealing with trees (read: recursion), I often have the same trouble. I have stuck the source code example at the end of this post. It should fit in ok on the web page; if not, perhaps an administrator can copy it to a source-file on the webserver and link to it.

Basically, the code below finds the minimum moves for a stack. It does this by trying all combinations of flips, and uses static variables to store data. Notice the static $min. $min is the maximum depth the tree can go. The static $level gets incremented for each recursive level. If a solution is found, and $level < $min, then $min is lowered, so that in future, the program doesn't search to deep. The problem, if I set $min to 15, and lets say the stack concerned can be sorted in 7 moves, the program wastes time searching 15 levels deep for a long time, before slowly finding better solutions. Eventually it finds the 7 move solution, and ends soon after (obviously).

What I've been doing is starting with a low $min, and running the sort over and over, incrementing $min each time. The first few times, it finds no solution, but runs extremely fast anyway. When I reach 7, it finds the best solution. Obviously I could code a simple for loop to do this, and it would be automatic.

My question is, does anybody know any other way to do this? Obviously, pre-order and such doesn't apply, because the action happens at the leaf nodes. Or perhaps there is a much better way to do this without even using recursion. Obviously, I am referring to the way a recursive funtion recurses as a tree. I can picture it easier as a tree. Since the nth level takes a large degree longer than the (n-1)th level, this solution could be acceptable as is.

As I said, I've wondered about this before, in other recursive solutions. Obviously, this problem is not PHP specific, in fact, this contest is the first time I am using a recursive function in PHP.

This post is rather long, I hope its OK, Matt. (Or someone with authority >= Matt->authority; Gee, I think all this coding has gone to my head).

In this way, it's impossible to solve anything... Have in mind that the number of positions you're trying to look at is about n**m (n=number of discs, m=depth).

If n=500, you will not get past depth 3 or so.. Especially in PHP

So, the first thing you should do is limit the number of possible moves in each position. For this particular problem, I only considered:
- flipping the whole unsolved stack (especially if the biggest disc is on top)
- flipping so that the biggest unsolved disc gets on top
- flipping so that the disc that is on top becomes a neighbour of one-bigger or one-smaller disc (or duplicate, if applicable)

But even this didn't help.. Consider a position of 250 1s and 250 2s. Even if you use the trivial algorithm (largest to top, then to bottom), it's hard to tell which of the biggest to flip to top.

So, I assigned weights to each case and chose a random move, and ran through the solution as long as the time allowed. Even with such a simple algorithm, with 500 discs I only got 6 runs...

I took the easy way out; didn't use recursion :/ Fleshed out a different iteration algorithm than flipping "biggest to top, then bottom", although it might seem a little similar.

It figures anywhere from 1.8N to 3N depending on the order of numbers and some luck, heh heh heh... (helps if some of the numbers are in order already ;p)

I'm too lazy for recursion

Come on guys, do you seriously think this is my solution to this contest? Please, I only wrote this after the deadline, and only to find the best solution for small stacks. I wrote it in 5 minutes.

My code for the contest doesn't even remotely resemble this.

What I am asking is, when you have a function such as this, and you want to find the least moves, you can't search too deep, because you waste time. That is why I increment $min each time.

I could have asked this in another forum, because it isn't directly related to this contest. But I assumed anybody submitting for the contest had to be good coders. So, guys, surely some of you have had exactly the same issue with recursion before. Is there any other way to do it?.

I have also wrote the function iteratively, ie. without recursive calls, just a while loop. But the execution still follows a tree type pattern.

Please guys, look closely at my previous post, to understand what I am asking. I am 95% sure there is no better way, but I thought maybe somewhere out there there was some freak-of-nature uber-coder who knew some other way to do this which would not search redundant combos.

Please, -vertigo-, look closely at MY previous post

There's nothing you can do that will make going through a gazillion positions considerably faster (except through optimization, but that will still only be a constant factor). You have to reduce the number of positions or be very slow.

It doesn't matter whether your code is recursive or iterative or whatever. What matters is
- reducing the number of moves considered in each position
- choosing the most favorable move in each position, if you're going depth-first

What I tried to say with my post is that this is a particularly difficult problem, because there are positions where you can hardly reduce the number of moves, and there are positions where it's hard to tell which of the possible moves looks most promising.

xs0: I know what you are saying, that its stupid to even try to go through all combos in the first place. Its just that when I was studying, the lectures treated recursion like it was god's gift to coding, but in reality it is often not very beneficial.

You are right that sorting through heaps of searches is never going to get much faster. I just wanted to know if it could be made any faster at all. But I really knew all along that it coudn't.

So how did coding go for you?

I agree with what xs0 said, the only thing I'll add is a suggestion on how to reduce the number of moves by choosing the most favorable moves.
No idea if this is right - just the first thing I thought of: Instead of trying the flips at every single number, would flipping above and below the numbers next in the sequence be better?

For instance for numbers 53423, look at the top number (5) and flipping at pos 2 and pos 4. Maybe even detect it is the largest and include flipping the entire stack. I suggest this because I can't think of a situation when it beneficial to do any other moves.

The only reason I ever use recursion is when it makes the code easier to read, as it did for two of the algorithms in my entry.
Also, I'd imagine a recursive function may use more memory or something?

Finally forgive me if i've missed something but why does it do a flip and then flip back again?

JRA - the two flips are each side of the recursive call. If it chooses to flip the top 2 for instance, it does the flip, then calls itself. The new level again performs various flips in order. When that level is completed, it returns. Then the same flip is done to undo it, because flipping the top 2 twice undoes it. When each level ends, the previous flip is undone. This is because a global array is used, rather than a local one. Local arrays would be a huge waste of time.

I could have used a static array too.

All becomes clear