`[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-05This topic: Main/Cimec > MarioStorti > SomeVTKExamples > BurntPancakeProblem

Topic revision: 30 Mar 2016, MarioStorti

Topic revision: 30 Mar 2016, MarioStorti

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding Foswiki? Send feedback

Ideas, requests, problems regarding Foswiki? Send feedback