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