OpenEuphoria

Fannkuch

Fannkuch Euphoria

-- fannkuch.ex 
 
-- original:  
--  The Computer Language Benchmarks Game 
-- http://shootout.alioth.debian.org/ 
-- contributed by Mike Pall 
 
-- converted by Tom Ciplijauskas 
 
--local function fannkuch(n) 
function fannkuch( integer n ) 
   integer temp 
   sequence p, q, s    
   integer sign = 1  --aka odd 
   integer maxflips = 0 
   atom sum = 0 
 
   p = repeat( 0, n )   
   for i=1 to n do 
      p[i] = i 
      end for 
 
   q = p   
   s = p       
   
    while 1 do      -->> Copy and flip. 
       integer q1 = p[1] 	-->> Cache 1st element. 
       if q1 != 1 then 
           q = p   -->> work on a copy   
           integer flips = 1 
           integer qq 
	   while 1 do 
              qq = q[q1]    
	    if qq = 1 then				-->> ... until 1st element is 1. 
	       sum = sum + sign*flips 
               if flips > maxflips then maxflips = flips end if -->> New maximum? 
                 exit  
                 end if 
	      q[q1] = q1 
	     if q1 >= 4 then 
               integer i = 2 
     	       integer j = q1 - 1 
               loop do 
                  temp = q[i] 
                  q[i] = q[j] 
                  q[j] = temp  
                  i = i + 1 
                  j = j - 1 
                  until i >= j 
                  end loop   
              end if 
           q1 = qq 
           flips = flips + 1 
          end while 
    end if 
 
 
                                      -- Permute. 
    if sign = 1 then 
         temp = p[2] 
         p[2] = p[1] 
         p[1] = temp 
         sign = -1 
    else 
	-->> Rotate 1<-2 and 1<-2<-3. 
        temp = p[2] 
        p[2] = p[3] 
        p[3] = temp 
        sign = 1  
        for i=3 to n do 
    	      integer sx = s[i] 
         	if sx != 1 then  
               	   s[i] = sx-1 
                   exit -- break  
                   end if 
         	if i = n then  
                   return {sum, maxflips}  
                   end if	-->> Out of permutations. 
	        s[i] = i 
	      -->> Rotate 1<-...<-i+1. 
	    integer t = p[1] 
             for j=1 to i do  
                 p[j] = p[j+1]  
                 end for 
                p[i+1] = t 
           end for 
 
    end if 
end while 
 
end function 
 
include std/get.e 
include std/console.e 
procedure main(sequence argv) 
    object N 
    if length(argv) >= 3 then 
        N = value(argv[3]) 
        N = N[2] 
    else 
        N = 1 
    end if 
  display( N ) 
  display( fannkuch(N) )  
end procedure  
 
main( command_line() ) 

Fannkuch Python

#    The Computer Language Benchmarks Game 
#    http://shootout.alioth.debian.org/ 
 
#    contributed by Isaac Gouy 
#    converted to Java by Oleg Mazurov 
#    converted to Python by Buck Golemon 
#    modified by Justin Peel 
 
def fannkuch(n): 
    maxFlipsCount = 0 
    permSign = True 
    checksum = 0 
 
    perm1 = list(range(n))   
    count = perm1[:] 
    rxrange = range(2, n - 1) 
#    print rxrange 
    nm = n - 1 
    while 1: 
        k = perm1[0] 
#       print k 
        if k: 
            perm = perm1[:] 
 #           print perm 
            flipsCount = 1 
            kk = perm[k] 
  #          print kk 
            while kk: 
   #             print perm 
    #            print perm[:k+1] 
     #           print perm[k::-1] 
                perm[:k+1] = perm[k::-1] 
      #          print "----" 
                flipsCount += 1 
                k = kk 
                kk = perm[kk] 
#                print "==done=="  
            if maxFlipsCount < flipsCount: 
                maxFlipsCount = flipsCount 
            checksum += flipsCount if permSign else -flipsCount 
 
        # Use incremental change to generate another permutation 
        if permSign: 
            perm1[0],perm1[1] = perm1[1],perm1[0] 
            permSign = False 
        else: 
            perm1[1],perm1[2] = perm1[2],perm1[1] 
            permSign = True 
  #          print "rxrange" 
   #         print rxrange 
            for r in rxrange: 
     #           print "r" 
      #          print r 
                if count[r]: 
                    break 
                count[r] = r 
                perm0 = perm1[0] 
                perm1[:r+1] = perm1[1:r+2] 
                perm1[r+1] = perm0 
            else: 
                r = nm 
                if not count[r]: 
                    print( checksum ) 
                    return maxFlipsCount 
            count[r] -= 1 
from sys import argv 
n = int(argv[1]) 
 
print(( "Pfannkuchen(%i) = %i" % (n, fannkuch(n)) )) 
 
	 

Fannkuch Perl

# The Computer Language Benchmarks Game 
# http://shootout.alioth.debian.org/ 
# initial fannkuch port from C by Steve Clark 
#   rewrite by Kalev Soikonen 
#   modified by Kuang-che Wu 
#   modified by David Golden 
# updated for fannkuch-redux by Jonathan DePeri 
#   permutations generated using Mike Pall's approach 
 
use integer; 
 
sub fannkuchredux { 
    my ($n) = shift; 
    my ($m, $checksum, $maxflips, $flips, $sign) = ($n-1, 0, 0, 0, 1); 
    my ($p, $q, $f, $i, @count); 
 
    @count = (0..$m); 
    $p = pack "c*", @count; 
 
    do { 
        if (ord(substr($p,0))) { 
            $q = $p; 
            $flips = 0; 
            while ($f = ord(substr($q,0))) { 
                $flips++; 
                substr($q, 0, $f+1, reverse(substr($q,0,$f+1))); 
            } 
            $maxflips = $flips if ($flips > $maxflips); 
            $checksum += ($sign * $flips); 
        } 
 
        return if ($n <= 1); 
        if ($sign == 1) { 
            $sign = -1; 
            substr $p, 1, 0, (substr($p,0,1,"")); 
        } else { 
            return if ($n <= 2); 
            $sign = 1; 
            substr $p, 1, 0, (substr($p,2,1,"")); 
            for $i (2..$m) { 
	            if ($count[$i]) { $count[$i]--; last; } 
	            return ($checksum, $maxflips) if ($i == $m); 
	            $count[$i] = $i; 
	            substr $p, $i+1, 0, (substr($p,0,1,"")); 
            } 
        } 
    } while (1); 
} 
 
for (shift) { 
    exit -1 if ((not defined $_) || $_ < 1); 
    my ($checksum, $maxflips) = fannkuchredux($_); 
    print "$checksum\n"; 
    print "Pfannkuchen($_) = $maxflips\n"; 
}