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)

    1for k in range(N,0,-1):
    2    j = amax(pancakes,k)
    3    invert(pancakes,j+1)
    4    invert(pancakes,k+1)

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

    1for k in range(N,0,-1):
    2    j = amax(pancakes,k)
    3    invert(pancakes,j+1)
    4    if pancakes[0]>0:
    5        pancakes[0] *= -1
    6    invert(pancakes,k)

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:

    1#!/usr/bin/env python
    2
    3import time
    4import random
    5import sys
    6import os
    7# from np import *
    8import numpy as np
    9import vtk
   10
   11N = 10
   12pancakes = []
   13for k in range(0,N):
   14    x = random.randint(1,5*N)
   15    ## Random flip
   16    x *= 2*random.randint(0,1)-1
   17    pancakes.append(x)
   18
   19## Find kmax the position of the minimum of |w|
   20## in range [0,m) 
   21def amax(w,m):
   22    N = len(w)
   23    assert(m<=N)
   24    assert(m>0)
   25    kmax = 0
   26    for k in range(1,m):
   27        if abs(w[k])>abs(w[kmax]):
   28            kmax = k
   29    return kmax
   30
   31# invert range [0,j) (change sign because
   32# burnt side is inverted
   33def invert(w,j):
   34    v = list(w)
   35    for k in range(0,j):
   36        w[k] = -v[j-k-1]
   37
   38print "initial pancakes position (<0 means burnt upside)"
   39print pancakes
   40for k in range(N,0,-1):
   41    j = amax(pancakes,k)
   42    print "max found at position %d, inverting [0,%d]" \
   43        % (j,j)
   44    invert(pancakes,j+1)
   45    print pancakes
   46    if pancakes[0]>0:
   47        print "first pancake is burnt downside, reverting"
   48        pancakes[0] *= -1
   49        print pancakes
   50    print "inverting [0,%d]" % (k-1)
   51    invert(pancakes,k)
   52    print pancakes

A typical run with 10 pancakes goes like this

[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]$ 

-- MarioStorti - 2014-09-05

Topic revision: r6 - 2016-03-30 - 11:12:38 - MarioStorti
 

TWIKI.NET
This site is powered by the TWiki collaboration platformCopyright � by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback