This program will solve the "pancake sorting problem". This problem is when you have a stack of pancakes with varying sizes and you want to sort them into a stack with the smallest on top, largest on the bottom. The only tool you have to do this is a spatula, with which you can pick a pancake, and reverse that pancake and all of the pancakes above it on the top of the stack.

Feel free to copy this source code to try out and/or experiment with.

Note: You can find this code in a file named "pancakes.pl" in the directory http://www.csc.liv.ac.uk/~martin/teaching/comp519/PERL and a sample input file in the same directory where this HTML file is located, stored under the name "pancakes.in".

 #!/usr/bin/perl -w
 #
 #  This program will compute a sequence of flips to
 # turn a stack of pancakes so that they sit from smallest
 # to largest (i.e. smallest on top).
 #
 #  Input will be read from a file, consisting of one
 # or more sequences of pancakes, each one on a separate line
 # of the file.  It is assumed that the pancake sizes are
 # given in order (left-to-right) starting from the top of
 # the stack, and are separated by spaces in the input.
 #
 #  Output will echo the original sequence of sizes for each
 # stack and will then indicate the sequence of flips.  Flips are
 # indicated by integers, which represent a pancake who's
 # position is indicated from the *top* of the stack.
 # A flip consists of turning over the pancake at some
 # position i, and all of the pancakes above
 # it (positions i-1, i-2, ..., 1).
 #
 # A "0" indicates that no more flips are necessary for that stack.
 #
 #  As stated above, the program is designed to read data from
 # a file (or several files).   In other words, to
 # use this program it should be invoked with a command like
 #      ./pancakes.pl pancakes.in
 # where the file "pancakes.in" contains the input as described above,
 # namely each line contains a single stack of pancakes given in
 # order from top to bottom of the stack.


 use strict;

   my ($n, @pancakes, @sorted, $bottom, $i, $index, $max_so_far, @temp);

   print "\n";
   while (<>)  #  While there is still input from the file(s), process it.
    {
       chomp;
       @pancakes = split;  #  The default for the "split" function is to
                           #  split a sting on whitespace (spaces, tabs,
                           #  newlines, etc.)
                           #  So that line is the same as
                           #         @pancakes = split/\s+/, $_;
       $n = @pancakes;
       if ($n)             #  Skip over empty lines in the file.
          {
             print "@pancakes \nFlip sequence: ";
    #        @sorted = sort { $a <=> $b } @pancakes;  #  only used when
                                                      # testing program
             for ($bottom = $n - 1; $bottom > 0; $bottom--)
                 {
                    ($max_so_far, $index) = ($pancakes[$bottom], $bottom);
                    for ($i = 0; $i <= $bottom - 1; $i++)  #  find the max of
                                                     #  the short stack on top
                        {
                           if ($pancakes[$i] > $max_so_far)
                              {
                                   ($max_so_far, $index) = ($pancakes[$i], $i);
                              }
                        }
                    if ($index != $bottom)  #  if we have to flip anything...
                       {
                          if ($index != 0)   #  if we have to flip something
                                             #  other than the one on top...
                             {  print $index+1, " ";  }
                          print $bottom+1, " " ;  # then we flip this one

                          #  now construct the new stack by taking the relevant
                          #   pieces in the right order (after doing either one
                          #   or two flips, check that this works..., recall that
                          #   "push" adds items to the end of an array)

                          @temp = ();     #  start with empty array
                          for ($i = $bottom; $i > $index; $i--)
                               {  push (@temp, $pancakes[$i]);  }
                          for ($i = 0; $i < $index; $i++)
                              {  push (@temp, $pancakes[$i]);  }
                          push (@temp, $pancakes[$index]);
                          for ($i = $bottom + 1; $i < $n; $i++)
                              {  push (@temp, $pancakes[$i]);  }
                          @pancakes = @temp;
                       }
                 }
             print "0 \n\n";  #  we're done, so print out a "0"
          }

    }   #  end of "while" loop