FULL CODE IN PYTHON

Flipping Pancakes

You are cooking pancakes but no matter how hard you try they do not come out the same size. So now you have a stack of pancakes of different diameters. You do want to present the pancakes in a neat pile - with the biggest pancake at the bottom and the smallest on the top. All you have is a flat spatula. And there is just one operation you can do - you can insert the spatula anywhere in the pile of pancakes and flip the pancakes on the top. Find an algorithm that allows you to sort the pancakes by diameter with a minimum number of flips.

Sorting the stack of pancakes is done by a sequence of flips. A flip consists of inserting the spatula anywhere in the stack and flipping (reversing) all the panckaes on top of the spatula (reversing the sub-stack). A flip is specified by giving the position of the pancake on the bottom of the sub-stack to be flipped relative to the entire stack. The bottom pancake has position 1, while the top pancake on a stack of n pancakes has position n.

A stack is specified by giving the diameter of each pancake in the stack in the order in which the pancakes appear. For example, consider the three stacks of pancakes below in which pancake of diameter 8 is the top-most pancake of the left stack.

 8 7 2 4 6 5 6 4 8 7 8 4 5 5 6 2 2 7 

The stack on the left can be transformed to the stack in the middle via flip(3). The middle stack can be transformed into the right stack via flip(1).

Input: You will read your input from a file called pancake.txt. In the input file you will be given a sequence of stacks of pancakes. Each line in the input file corresponds to a stack of pancakes. Each stack will consist anywhere between 1 and 30 pancakes and each pancake will have an integer diameter between 1 and 100. The top pancake on a stack appears first on a line and the bottom pancake appears last on the line, and all the pancakes are separated by a space.

1 2 3 4 5 5 4 3 2 1 5 1 2 3 4 

Output: For each stack of pancakes, your program should echo the orginal stack on one line, followed by a sequence of flips that results in sorting the stack of pancakes so that the largest pancake is on the bottom and the smallest on top. the sequence of flips for each stack should be terminated by a 0, indicating no more flips are necessary. Once a stack is sorted, no more flips should be made.

1 2 3 4 5 0 5 4 3 2 1 1 0 5 1 2 3 4 1 2 0