Date: Thu, 15 Jul 2000 17:15:45 -0700 (PDT)
From: Jacob Mandelson
While flipping the largest pancake to the top and then the bottom will always solve the puzzle, it won't always give the quickest solution. Consider the initial position 165432. It can be solved in three flips (234561, 654321, 123456), but the "largest first" method takes four flips (615432, 234516, 543216, 123456).
A method that seems to work out better is to make flips such that the count of pancakes adjacent to neighbors in size is increased. (Consider there to be a phantom pancake one size larger than the largest below the pile.) However, for all the variations on this method I've tried, I've been able to come up with an example stack of pancakes for which there's a faster solution.
71542589