Burnt Pancake Problem

We consider here the burnt pancake problem. Remember that for the pancake sort algorithm we have to sort a certain number of elements only using inversions of positions [0,j) (as in a stack of pancakes). For the burnt pancake problem we have in addition the restriction that the pancakes have a burnt side, and all the pancakes must end with the burnt side down.

First consider the algorithm for the plain pancake problem (no burnt side). The algorithm is (Python)

%CODE{ lang="python" num="1" }% for k in range(N,0,-1): j = amax(pancakes,k) invert(pancakes,j+1) invert(pancakes,k+1) %ENDCODE%

Where the function invert(w,n) inverts range [0,n) in list w. And the function amax(w,k) returns the position kmax of the maximum element of w in absolute value.

We first look for the largest pancake N-1, which is in position j. Then we invert the range [0,j] so that this pancake gets into the first position 0. Then we invert the whole stack so that pancake N-1 goes to the bottom. One we have put the largest pancake at the bottom, we proceed in the same way for the N-1 pancakes up in the stack, and so on.

Now, for considering the burnt pancake problem (as described in Wikipedia here) you just need to reverse the pancake when it is at the top, (only if it is needed, that is, if the pancake is burnt side down). I use a Python list and negative numbers means that the pancake is burnt side up. Position 0 is the top of the stack. So we start with a a random permutation of [1,N] with some of the pancakes burnt side up (denoted by negative numbers).

The algorithm is now

%CODE{ lang="python" num="1" }% for k in range(N,0,-1): j = amax(pancakes,k) invert(pancakes,j+1) if pancakes[0]>0: pancakes[0] *= -1 invert(pancakes,k) %ENDCODE%

The function invert(w,j) not only inverts the [0,j) range but also is in charge of changing the sign of the elements that inverts (so that it reflects the fact that the pancakes are reversed).

The Python code is here:

%CODE{ lang="python" num="1" }% #!/usr/bin/env python

import time import random import sys import os # from np import * import numpy as np import vtk

N = 10 pancakes = [] for k in range(0,N): x = random.randint(1,5*N) ## Random flip x *= 2*random.randint(0,1)-1 pancakes.append(x)

## Find kmax the position of the minimum of |w| ## in range [0,m) def amax(w,m): N = len(w) assert(m<=N) assert(m>0) kmax = 0 for k in range(1,m): if abs(w[k])>abs(w[kmax]): kmax = k return kmax

# invert range [0,j) (change sign because # burnt side is inverted def invert(w,j): v = list(w) for k in range(0,j): w[k] = -v[j-k-1]

print "initial pancakes position (<0 means burnt upside)" print pancakes for k in range(N,0,-1): j = amax(pancakes,k) print "max found at position %d, inverting [0,%d]" % (j,j) invert(pancakes,j+1) print pancakes if pancakes[0]>0: print "first pancake is burnt downside, reverting" pancakes[0] *= -1 print pancakes print "inverting [0,%d]" % (k-1) invert(pancakes,k) print pancakes %ENDCODE%

A typical run with 10 pancakes goes like this

%STARTCONSOLE% [mstorti@galileo animstb]$ ./pancakeb.py initial pancakes position (<0 means burnt upside) [-50, -41, -9, 7, 14, -42, -5, -24, 44, 8] max found at position 0, inverting [0,0] [50, -41, -9, 7, 14, -42, -5, -24, 44, 8] first pancake is burnt downside, reverting [-50, -41, -9, 7, 14, -42, -5, -24, 44, 8] inverting [0,9] [-8, -44, 24, 5, 42, -14, -7, 9, 41, 50] max found at position 1, inverting [0,1] [44, 8, 24, 5, 42, -14, -7, 9, 41, 50] first pancake is burnt downside, reverting [-44, 8, 24, 5, 42, -14, -7, 9, 41, 50] inverting [0,8] [-41, -9, 7, 14, -42, -5, -24, -8, 44, 50] max found at position 4, inverting [0,4] [42, -14, -7, 9, 41, -5, -24, -8, 44, 50] first pancake is burnt downside, reverting [-42, -14, -7, 9, 41, -5, -24, -8, 44, 50] inverting [0,7] [8, 24, 5, -41, -9, 7, 14, 42, 44, 50] max found at position 3, inverting [0,3] [41, -5, -24, -8, -9, 7, 14, 42, 44, 50] first pancake is burnt downside, reverting [-41, -5, -24, -8, -9, 7, 14, 42, 44, 50] inverting [0,6] [-14, -7, 9, 8, 24, 5, 41, 42, 44, 50] max found at position 4, inverting [0,4] [-24, -8, -9, 7, 14, 5, 41, 42, 44, 50] inverting [0,5] [-5, -14, -7, 9, 8, 24, 41, 42, 44, 50] max found at position 1, inverting [0,1] [14, 5, -7, 9, 8, 24, 41, 42, 44, 50] first pancake is burnt downside, reverting [-14, 5, -7, 9, 8, 24, 41, 42, 44, 50] inverting [0,4] [-8, -9, 7, -5, 14, 24, 41, 42, 44, 50] max found at position 1, inverting [0,1] [9, 8, 7, -5, 14, 24, 41, 42, 44, 50] first pancake is burnt downside, reverting [-9, 8, 7, -5, 14, 24, 41, 42, 44, 50] inverting [0,3] [5, -7, -8, 9, 14, 24, 41, 42, 44, 50] max found at position 2, inverting [0,2] [8, 7, -5, 9, 14, 24, 41, 42, 44, 50] first pancake is burnt downside, reverting [-8, 7, -5, 9, 14, 24, 41, 42, 44, 50] inverting [0,2] [5, -7, 8, 9, 14, 24, 41, 42, 44, 50] max found at position 1, inverting [0,1] [7, -5, 8, 9, 14, 24, 41, 42, 44, 50] first pancake is burnt downside, reverting [-7, -5, 8, 9, 14, 24, 41, 42, 44, 50] inverting [0,1] [5, 7, 8, 9, 14, 24, 41, 42, 44, 50] max found at position 0, inverting [0,0] [-5, 7, 8, 9, 14, 24, 41, 42, 44, 50] inverting [0,0] [5, 7, 8, 9, 14, 24, 41, 42, 44, 50] [mstorti@galileo animstb]$ %ENDCONSOLE%

-- MarioStorti - 2014-09-05