Pancake sorting

This webpage contains data and source codes of programs mentioned in the paper "On average and highest number of flips in pancake sorting". A preprint of the paper can be found at arxiv.

See wikipedia for definitions and related works.

All the programs are under GPL. See comments in each of the source files for more information on their usage and on how they work. Most of the compiled files will also provide usage instructions when run without paramaters. Some notes about compilation.

Unburnt pancakes

• Program Manysteps was used to find all unburnt stacks of size 17 that require 19 flips. It was run with parameters "17 19 20 10000 x" with 'x' ranging from 0 to 9999. The actual source code used had much fewer comments and not so nice variable and function names.
  The accumulated running time was 5133,24 days (on a single core), but the parts were run on a plethora of processors. My guess based on the parts ran on my home computer is that it would take roughly 4438 days using one core of Athlon X2 3800+@2,1Ghz.
  Most (~90%) of the calculations took place on the computers of the Metacentrum grid. The rest was run on computers of our department and on my home computer.
• Program Onestep continued to stacks of size 18 and showed that none of them needs 21 flips. Then it found 219 of the stacks in U(19,22) listed in the table below. These together took only about a week on a single core of Athlon X2 3800+@2,1Ghz. The source code is not well documented. Its only differences from the Manysteps program are that it takes files created by Manysteps or Onestep as input instead of generating all stacks and generates only stacks one larger than the input stacks.
• For smaller stack sizes, program BFS-unb can be used to generate lists of stacks of a given number of pancakes requiring given number of flips. It is limited by RAM size and on a current typical computer (as of 2011) can be used for stacks of at most 13 pancakes (this requires ~1.5GB RAM). The reason why the program does not store its data on a hard disk is that the program in its current form requires lots of random reads and writes, which are slow on hard disks. However, there are clever techniques that are able to overcome this limitation and allowed to continue up to 15 pancakes. See the paper: Richard Korf, Minimizing Disk I/O in Two-Bit Breadth-First Search, In: AAAI, 2008.

Numbers of stacks of n unburnt pancakes requiring m flips to sort:

The .txt files contain stacks one on each line, each line lists the pancakes from top to bottom. Empty field in the table means that no such stack exists.

* You will need 7zip to unpack the archive. One of the unpacked files will be Readme.txt with the instructions on how to obtain a file in a human-readable format. The resulting file will have ~2,6 GB.

** The file contains just every 100^th of the stacks generated from U(17,19) by program onestep.

*** Stacks generated from the incomplete U(18,20) and also e.g. by trying all stacks with chunks of size (8,6,5).

Burnt pancakes

• All stacks of 9 burnt pancakes were solved by a breadth-first search program. The program creates file burnt9.binf. Several .tmp files totalling almost 2 GB are also created, but these can be deleted after the program has finished.
• Program burquery looks up the number of flips required to sort given stacks using data from a .binf file. See an example of a query file. Program burextract extracts all the stacks from a .binf requiring a prescribed number of flips to stdout.
• The data in the table below were generated using programs Manysteps-b and Onestep-b, that are the "burnt" analogues of the "unburnt" programs above. Unlike the unburnt case, these programs encountered stacks for which it took a lot of time and memory to find the exact number of flips and so more sophisticated lower bounds are used. Both programs need file burnt9.binf from which they read numbers of flips for stacks of 9 pancakes, that is then used in the A*-search.
• Program Onestack-b contains even more sophisticated lower bound and with this program, the upper bounds on the number of flips for stacks J_n, Y_n and F_n with n up to 20 were determined. An example of its input file.

Numbers of stacks of n burnt pancakes requiring m flips to sort:

The .txt files contain stacks one on each line, each line lists the pancakes from top to bottom, '-' after a pancake means that the pancake is burnt side up. Empty field in the table means that no such stack exists.

Fixed onestep-b.c and onestack-b.c, which expected burnt9.bin file, while only burnt9.binf is available here (.bin was an earlier format).

update Nov 25, 2011

Added bfs-unb.c, Readme.txt and fixed bur-binfout.c which could crash sometimes (closing file that was not open).