## Flipping Pancakes

### April 7, 2009

Pity the poor waiter:

The chef in our place is sloppy, and when he prepares a stack of pancakes they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, down to the largest at the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary.

Your task is to write a function that sorts a list of unique positive integers into ascending order using the pancake-flipping algorithm. When you are finished, you can read or run a suggested solution, or post your solution or discuss the exercise in the comments below.

Pages: 1 2

### 12 Responses to “Flipping Pancakes”

1. FalconNL said

This Haskell solution does some unnecessary flips if the bottom of the current subset is already in the correct position, but then again if you want efficiency just do a merge- or quicksort :)

```main = print \$ pancakeSort [7,2,9,4,6,1,3,8,5]

pancakeSort :: (Ord a) => [a] -> [a]
pancakeSort xs = foldr sort' xs [1..length xs]

sort' :: (Ord a) => Int -> [a] -> [a]
sort' n xs = flip' n \$ flip' (snd . maximum . flip zip [1..] \$ take n xs) xs

flip' :: Int -> [a] -> [a]
flip' n = uncurry ((++) . reverse) . splitAt n
```
2. Ben Simon said

Man that Haskell solution is compact. It’s gorgeous. Too bad my Haskell is so rusty that it doesn’t mean anything to me.

3. ; Solution using fold

#lang scheme
(require srfi/1)

(define (flip n xs)
(let-values ([(top bottom) (split-at xs n)])
(append (reverse top) bottom)))

(define (find-max n xs)
(let ([m (apply max (take xs n))])
(list-index (λ (x) (= x m)) xs)))

(define (pancake xs)
(fold (λ (n xs) (flip n (flip (+ (find-max n xs) 1) xs)))
xs
(reverse (iota (length xs) 1))))

(pancake ‘(7 2 9 4 6 11 1 3 8 5 13))

4. ; Solution without fold.

#lang scheme
(require srfi/1)

(define (flip n xs)
(let-values ([(top bottom) (split-at xs n)])
(append (reverse top) bottom)))

(define (find-max n xs)
(let ([m (apply max (take xs n))])
(list-index (λ (x) (= x m)) xs)))

(define (nest f n base)
(if (= n 0)
base
(nest f (- n 1) (f n base))))

(define (pancake xs)
(nest (λ (n xs) (flip n (flip (+ (find-max n xs) 1) xs)))
(length xs)
xs))

(pancake ‘(7 2 9 4 6 11 1 3 8 5 10 ))

5. programmingpraxis said

Ben,

It’s not too hard to define Scheme functions so they resemble the curry-and-compose style of Haskell. I just uploaded a small library of higher-order functions to the Standard Prelude, including compose and define-curried; fold-right is already there. That’s most of what you need to replicate the Haskell solution.

6. I notice that the prelude contains this definition:

(define (second x y) y)

There is a strong tradition however to let second be:

(define (second xs) (list-ref xs 1))

I am not sure what the traditional name for
the projection is, but perhaps project2 ?

7. programmingpraxis said

I think an even older and stronger tradition is to spell your second “cadr”. I just looked; cadr appears on page 13 of the Lisp 1.5 Programmer’s Manual, in the definition of apply.

8. In modern times second is used instead of cadr to stress that one is working with lists. The operation cadr is used for trees built using conses.

Both in SRFI 1 and the Common Lisp HyperSpec second is used to access the second element of a list.

9. g said

here’s my python:

```def flipsort(pile):
for i in xrange(len(pile)):
max_index = pile.index(max(pile[i:]))
if max_index != i:
pile[max_index:] = pile[max_index:][::-1]
pile[i:] = pile[i:][::-1]
return pile```
10. g said

fixed to work with duplicates:

```def flipsort(pile):
for i in xrange(len(pile)):
slice = pile[i:]
max_index = slice.index(max(slice)) + i
if max_index != i:
step += 2
pile[max_index:] = pile[max_index:][::-1]
pile[i:] = pile[i:][::-1]
return pile```
11. g said

oops, `step += 2` shouldn’t be there