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?