benchmark/so_fannkuch.rb

   1 # The Computer Language Shootout
   2 # http://shootout.alioth.debian.org/
   3 # Contributed by Sokolov Yura
   4 # Modified by Ryan Williams
   5
   6 def fannkuch(n)
   7    maxFlips, m, r, check = 0, n-1, n, 0
   8    count = (1..n).to_a
   9    perm = (1..n).to_a
  10
  11    while true
  12       if check < 30
  13          puts "#{perm}"
  14          check += 1
  15       end
  16
  17       while r != 1
  18          count[r-1] = r
  19          r -= 1
  20       end
  21
  22       if perm[0] != 1 and perm[m] != n
  23          perml = perm.clone #.dup
  24          flips = 0
  25          while (k = perml.first ) != 1
  26             perml = perml.slice!(0, k).reverse + perml
  27             flips += 1
  28          end
  29          maxFlips = flips if flips > maxFlips
  30       end
  31       while true
  32          if r==n then return maxFlips end
  33          perm.insert r,perm.shift
  34          break if (count[r] -= 1) > 0
  35          r += 1
  36       end
  37    end
  38 end
  39
  40 def puts *args
  41 end
  42
  43 N = 9 # (ARGV[0] || 1).to_i
  44 puts "Pfannkuchen(#{N}) = #{fannkuch(N)}"
  45