user
Adrian Monk has problems and an assistant, Sharona Fleming. Sharona can deal with most of Adrian's problems except his lack of punctuality paying her remuneration. Two pay checks down and she prepares him pancakes for breakfast. Knowing that he will be unable to eat them unless they are stacked in ascending order of size she leaves him only a skillet which he can insert at any point in the pile and flip all the above pancakes, repeating until the pile is sorted. Sharona has left the pile of n pancakes such that the maximum number of flips is required. Adrian is determined to do this in as few flips as possible. This sequence n->p(n) is known as the Pancake numbers.

The task is to determine p(n) for n = 1 to 9, and for each show an example requiring p(n) flips.

Sorting\_algorithms/Pancake\_sort actually performs the sort some giving the number of flips used. How do these compare with p(n)?

Few people know p(20), generously I shall award an extra credit for anyone doing more than p(16).

Warning
:   It is known that p(19) is 22 (see in particular the discussion at A058986); thus any algorithm that claims otherwise must be treated with caution.
:   Note that the original "cheeky partial answer" of Phix has since been updated (5/12/2020), and/but just that, with no examples as asked for, *will* get your entry marked as incomplete.

References

1. Bill Gates and the pancake problem
2. A058986
assistant
### Maximum number of flips only

**Translation of**: Phix

This is the translation of the second version (5th dec 2020). It differs from the first version for p(19).

```
# Updated: 20240901 Raku programming solution

sub pancake(Int $n) {
   loop ( my ($gap, $pg, $sum_gaps, $adj) = <2 1 2 -1> ; ; $sum_gaps += $gap ) {
      $sum_gaps < $n ?? ( $adj += 1 ) !! return $n + $adj;
      ($pg, $gap) = ($gap, $gap + $pg)
   }
}

for (1..20).rotor(5) { @_».&{printf "p(%2d) = %2d   ",$_,pancake $_} and say() }

```

Output:

```
p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  4   p( 5) =  5
p( 6) =  7   p( 7) =  8   p( 8) =  9   p( 9) = 10   p(10) = 11
p(11) = 13   p(12) = 14   p(13) = 15   p(14) = 16   p(15) = 17
p(16) = 18   p(17) = 19   p(18) = 20   p(19) = 22   p(20) = 23
```

You may Attempt This Online!

### Maximum number of flips plus examples using exhaustive search

**Translation of**: Go

```
sub pancake(\n) {
   my @goalStack = (my \numStacks = $ = 1)..n ; 
   my %newStacks = my %stacks = @goalStack.Str, 0 ;
   for 1..1000 -> \k { 
      my %nextStacks = (); 
      for %newStacks.keys».split(' ') X 2..n -> (@arr, \pos) {
         given flat @arr[0..^pos].reverse, @arr[pos..*-1] {
            %nextStacks{$_.Str} = k unless %stacks{$_.Str}:exists
         }
      }
      %stacks ,= (%newStacks = %nextStacks);
      my $perms    = %stacks.elems;
      my %inverted = %stacks.antipairs;      # this causes loss on examples 
      my \max_key  = %inverted.keys.max;     # but not critical for our purpose
      $perms == numStacks ?? return %inverted{max_key}, k-1 !! numStacks=$perms
   }
   return '', 0
}

say "The maximum number of flips to sort a given number of elements is:";
for 1..9 -> $j { given pancake($j) { say "pancake($j) = $_[1] example: $_[0]" }}

```

Output:

```
The maximum number of flips to sort a given number of elements is:
pancake(1) = 0 example: 1
pancake(2) = 1 example: 2 1
pancake(3) = 3 example: 1 3 2
pancake(4) = 4 example: 2 4 1 3
pancake(5) = 5 example: 5 1 3 2 4
pancake(6) = 7 example: 5 3 6 1 4 2
pancake(7) = 8 example: 1 5 3 7 4 2 6
pancake(8) = 9 example: 6 1 8 3 5 7 2 4
pancake(9) = 10 example: 3 6 9 2 5 8 4 7 1
```