[Haskell-cafe] Progress on shootout entries

Iavor Diatchki iavor.diatchki at gmail.com
Tue Jan 3 19:05:17 EST 2006

Here is a short (16 lines) and readable Haskell'98 solution.
I haven't optimized it or tested it much.
When compiled with ghc(6.4.1) -O2, it takes about 10s to compute the
answer for 9,
on my P3 366MHz machine.  It seems to use about 16K of memory.

import System(getArgs)

flop xs@(x:_) = reverse (take x xs) ++ drop x xs
flops xs      = takeWhile ((1 /=) . head) (iterate flop xs)

perms xs      = foldr (concatMap . ins) [[]] xs

ins x []      = [[x]]
ins x (y:ys)  = (x:y:ys) : map (y:) (ins x ys)

pfannkuchen x = maximum (map (length . flops) (perms [1..x]))

main          = do a:_ <- getArgs
                   let n = read a :: Int
                   putStrLn (unlines (map show (take 30 (perms [1..n]))))
                   print (pfannkuchen n)

More information about the Haskell-Cafe mailing list