Turtle algorithm

[PJYelton]

Standard disclaimer: This is not for homework. I am studying for a programming competition and came across this problem that has truly stumped me and I was wondering if anyone had any ideas, not looking for code, just a push in the right direction.

Basically the problem is this: You are given a list of up to 200 turtle names who have been all stacked one on top of each other. You are also given a list of turtle names of how you WANT the turtles to be stacked. Now the only way for a turtle to change positions is for it to climb out of its spot and climb all the way to the top of the stack. Now the program is supposed to spit back the least amount of moves that it takes to reach the desired finish state as well as the list of moves.

The full problem statement can be found here: Turtle Problem

I've thought long and hard about this one but I can't seem to think of an algorithm that would solve this. The program must run within 10 seconds, and with 200 turtles then obviously brute force isn't an option, and a depth-first search will likewise time out with so many turtles. The best I can guess is a smart depth-first search which only picks from a small pool of candidates instead of the entire stack, but I can't figure out how to create this pool. The only way I can shorten the list to try is the obvious conclusion that a turtle never need move if he and all the turtles beneath him are in their correct spots.

Blech. Anyone have any ideas?

[VirtualAce]

You would need to check which turtles needed to move in reverse order so that the stack would end up like the desired stack. The reason it would be reverse is because each new turtle automatically goes to the top of the stack.

actual/desired
Ben Bob
Bob Billy
Billy Ben

Billy would move first

Billy
Ben
Bob

Bob would move next

Bob
Billy
Ben


Of course this is much simpler with 3 names as opposed to 200, but a similar algo should do the trick. It's basically a stack problem.

[PJYelton]

To be honest, I don't exactly see the algorithm you are proposing. Its real easy for me to look at a particular stack and realize what needs to be done, but I don't know how my program can figure out a generic case.

How does the program distiguish without trying every future possibility that Billy is the correct first move even though all three names are out of place? And I don't see where your example used any reverse ordering.

[PJYelton]

Oh, and one last thing (maybe this is what you were talking about), I know how to figure out what the last two moves always are because they obviously have to be the top two turtles on the finished stack. Its just past this that it gets tricky since you have to start taking into account where those top turtles came from...

[VirtualAce]

Scan through your desired stack and your current stack. If you need Billy on top, then Billy will be moved last, not first. So what you do is scan through the desired array from top to bottom, find that name in your current stack and save the location. What you will end up with is a list of indices that need to be moved to get to the desired stack - the list will be reverse of what the order is. You can't move the names in the order they appear in the desired stack or your stack will be exactly the reverse of the desired. You must work backwards so that if Billy is needed on top - he is the last turtle to be moved - otherwise when you move other turtles, they will be on top of Billy and he will no longer be on top. See?

The slow part of the algo would be in moving the turtles after each move of another turtle. The slowest method would be to reverse bubble sort them or turtle(i)=turtle(i+1) with turtle(0) being the one you just moved.

But finding the order in which they need to be moved should not take long at all. Just save all that in another array and iterate through it.

for (int i=0;i<turtlenum;i++)
{
   MoveTurtle(TurtleMoves[i]);
}

TurtleMoves[] holds the exact order in which the turtles need to be moved. Just iterate throught it, move the current turtle - which will then move all other turtles down one index, repeat until done.

So you don't figure out which turtles need to be moved on the fly. Figure that out before you start moving anything in memory. Once you have the correct order it is just a matter of moving the turtles in that order.

[PJYelton]

I think I understand what you are saying, but the problem is knowing when to stop since moving all the turtles starting with the bottom of the finished stack and moving up will definately solve the problem, but it isn't necessarily the shortest solution. So for example:

Start   End

Bob     Bret
Ben     Bill
Bill    Ben
Buck    Bob
Bret    Buck

So the answer of moving the turtles in reverse order of the finished stack Buck->Bob->Ben->Bill->Bret will definately solve it, but it isn't the shortest solution which is Bob->Ben->Bill->Bret

The way I am figuring it, I plan on popping the top of the result stack one at a time, then decide if the resulting stack is a subset of the starting stack and if it is, then the answer is the turtles I've popped in reverse order. Can't prove at the moment that this will always work though, but in my limited number of test cases it has...

[edit] Oops, my subset idea doesn't even work with the example above, oh well, I'm definately close though...

[VirtualAce]

You could work on only sections of the entire stack at once. You would decide which names go in which section and sort only that section. The sum total of all the sorted stack sections would be the sorted stack. In this manner you would 'know' the general area in the stack where each name needed to be based on the desired stack. Perhaps working on it sections at a time - even recursively on the sections - would be faster than looking at the whole stack each time.

Perhaps with this method you could get log(n) like a BSP tree. You could have multiple stack pointers working on multiple sections at a time. Half of the battle of the stack problem is elimination and deciding where each name goes. This is similar to the problem in 3D graphics. Half of the problem is deciding what to draw and not to draw. So using my method you could rule out several possibilities of which names need to be moved. It's much faster to work with 10 names than 200. So if you have 20 sections of 10 names, and 20 sections of 10 names in the desired stack - you could do this very very fast. Then your reverse bubble sort would only work on 10 names at any one time.

I will code some of this tonight to see what I can come up with.

[PJYelton]

I'd be really interested to see what you come up with. I'm not sure I completely follow, could you give an example with something like say 8-10 turtles?

I do have something that works now though, although I'm sure there is a more efficient way. Basically it does this: say the result stack is (top) A B C D E F etc (bottom), then on the start stack, move A to the top. Is it equal to the result stack? If yes then you are done, if not, then instead move turtle B then turtle A on the original start stack. Is it equal to result stacK? Yes, done. No, then instead move C then B then A, etc. Worst case scenario (as far as I can tell, I'm a newbie to analyzing algorithms) is that it runs in O(n^2) which for only 200 turtles should have no problem running in 10 seconds and I can't imagine it being incorrect. But now that I'm off to school I won't be able to verify that until tomorrow...

[slaveofthenet]

I've written a small program that should work. It fills a vector with 200 names, then fills another vector with the same names in a random order. It then goes through and moves each turtle to the top of the stack and eventually comes to the desired order. It's not the most efficient algorithm, but it works.

By the way, I used the numbers 0-199 for turtle names, but it could easily be substituted with 200 actual names.

[PJYelton]

Yeah, that program does what I mentioned above, moves ALL the turtles based off their position in the final stack. It does solve it but however it doesn't necessarily find the least amount of moves needed which is required by the problem. The most obvious example is this:

start     end

Bob       Bob
Ben       Ben

The answer is zero moves since the beginning is the same as the end, but your program will say the answer is to move Ben to the top and then Bob to the top resulting in two moves.

[Nutshell]

Hey PJ that problem sounds real interesting. What contest is that from? meh

[PJYelton]

Its not really from a contest, its from this site which has over a thousand problems to choose from and try, I'm just using it to practice for the ACM's and for the collegiate TopCoder competition.

I've finally figured out how to handle the turtle problem, and it turned out to be surprisingly easy. I realized that for N turtles, the most moves you would ever make is N since there is never a reason to move the same turtle twice. And if one could only figure out how many moves to make, even if it isn't obvious which moves those are - say x moves -, then its easy to figure out which ones to move just by looking at the finished stack and printing out the top x turtles in reverse order. So I spent all last night trying to figure out how one can look at the beginning stack and see which ones needed to be moved eventually or which ones never needed to be moved. It turns out it is obvious which ones never need move, its the ones that will fall into their natural place if all the incorrect ones are removed from beneath them. So if x turtles need not move, then (N-x) is the number that do move, so just print out the top (N-x) turtles from the final stack in reverse order and there you go.

An example:

start      end

Bill      Bob
Bob       Buck
Ben       Ben
Brett     Bill
Buck      Brett

Okay, so you move up the start stack and see which ones need not ever move. Buck needs to move. Brett need not ever move, because if you move all the incorrect ones beneath (Buck) then it falls to its correct place. Ben needs to move because if you remove all incorrects beneath, it falls to 4th which is incorrect. Bob is likewise incorrect when you remove Buck and Ben. But Bill is OK since removing Buck, Ben, and Bob will drop it to 4th which is where it wants to be. So total number of turtles to not move is 2, total number of turtles to move is 3, then just by looking at final stack take top 3 turtles in reverse order and the answer is (Ben->Buck->Bob). And sure enough thats the answer.

I haven't been able to fully prove why this always work, but so far it always has for me and it solves any problem quickly. Whew!

Thanks for the suggestions guys! It was a tremendous help, especially pointing out looking at it in reverse.