You are here: TWiki> Cimec Web>MarioStorti>SomeVTKExamples>BurntPancakeProblem (2016-03-30, MarioStorti)

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)

1forkinrange(N,0,-1):2j = amax(pancakes,k)3invert(pancakes,j+1)4invert(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

1forkinrange(N,0,-1):2j = amax(pancakes,k)3invert(pancakes,j+1)4ifpancakes[0]>0:5pancakes[0] *= -16invert(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 python23importtime4importrandom5importsys6importos7# from np import *8importnumpy as np9importvtk1011N = 1012pancakes = []13forkinrange(0,N):14x = random.randint(1,5*N)15## Random flipx *= 2*random.randint(0,1)-11617pancakes.append(x)1819## Find kmax the position of the minimum of |w|20## in range [0,m)21defamax(w,m):22N = len(w)23assert(m<=N)24assert(m>0)25kmax = 026forkinrange(1,m):27ifabs(w[k])>abs(w[kmax]):28kmax = k29returnkmax3031# invert range [0,j) (change sign because32# burnt side is inverted33definvert(w,j):34v = list(w)35forkinrange(0,j):36w[k] = -v[j-k-1]3738"initial pancakes position (<0 means burnt upside)"3940forkinrange(N,0,-1):41j = amax(pancakes,k)42"max found at position %d, inverting [0,%d]"\43% (j,j)44invert(pancakes,j+1)4546ifpancakes[0]>0:47"first pancake is burnt downside, reverting"48pancakes[0] *= -14950"inverting [0,%d]"% (k-1)51invert(pancakes,k)52

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

**Cimec Web**

- Cimec Web Home
- Personal CIMEC
- Investigación
- Asistencia técnica
- Becas
- Clusters HPC
- Enlaces
- Servicios CIMEC
- Software CIMEC

- Algoritmos y Estructuras de Datos
- Cálculo Numérico
- Cálculo Paralelo
- CFD
- HPC en MC
- Cálculo Tensorial en Mec. del Cont.
- Computación Gráfica
- Programación en C++ para Ciencia e Ingeniería
- Introducción al MEF
- Mecánica del Continuo
- Mecánica Computacional
- Mecánica de Sólidos
- Mecánica Racional
- Métodos Iterativos
- Teoría de la Computación

**Navegación**

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

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback