benchmark/bm_so_fannkuch.rb


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# The Computer Language Shootout
# http://shootout.alioth.debian.org/
# Contributed by Sokolov Yura
# Modified by Ryan Williams

def fannkuch(n)
   maxFlips, m, r, check = 0, n-1, n, 0
   count = (1..n).to_a
   perm = (1..n).to_a

   while true
      if check < 30
         puts "#{perm}"
         check += 1
      end

      while r != 1
         count[r-1] = r
         r -= 1
      end

      if perm[0] != 1 and perm[m] != n
         perml = perm.clone #.dup
         flips = 0
         while (k = perml.first ) != 1
            perml = perml.slice!(0, k).reverse + perml
            flips += 1
         end
         maxFlips = flips if flips > maxFlips
      end
      while true
         if r==n then return maxFlips end
         perm.insert r,perm.shift
         break if (count[r] -= 1) > 0
         r += 1
      end
   end
end

def puts *args
end

N = 9 # (ARGV[0] || 1).to_i
puts "Pfannkuchen(#{N}) = #{fannkuch(N)}"