Computer Language Shootout

[bearophileHUGS at lycos.com]

This is a direct translation of the D code, maybe it's not the faster
Python implementation, and surely it's not the shorter one. But Psyco
makes it much faster (Psyco likes "low level" style code).
ShedSkink is (almost) able to compile it too, producing a really fast
executable (with some "smart attentions" this SS version becomes only
17% slower than the D version for a given n=11 (26.66 sec instead of
22.70 sec of total running time on a PIII 500 MHz)).


! import sys
!
! def fannkuch(n):
!   perm = [0] * n
!   perm1 = range(n)
!   count = [0] * n
!   m = n - 1
!   r = n
!   maxFlipsCount = 0
!
!   while True:
!     while r != 1:
!       count[r-1] = r
!       r -= 1
!
!     # SS v.0.0.5 has a problem with this line:
!     if not (perm1[0]==0 or perm1[m]==m):
!       #perm = list(perm1)
!       # to not produce memory garbage
!       for i in xrange(n):
!         perm[i] = perm1[i]
!
!       i = perm[0]
!       flips = 0
!       while i:
!         temp = perm[i]
!         perm[i] = i
!         i = temp
!         j = 1
!         k = i - 1
!         while j < k:
!           temp = perm[j]
!           perm[j] = perm[k]
!           perm[k] = temp
!           j += 1
!           k -= 1
!         flips += 1
!
!       if flips > maxFlipsCount:
!         maxFlipsCount = flips
!
!     while True:
!       if r == n:
!         return maxFlipsCount
!       temp = perm1[0]
!       i = 0
!       while i < r:
!         j = i + 1
!         perm1[i] = perm1[j]
!         i = j
!       perm1[r] = temp
!
!       count[r] -= 1
!       if count[r] > 0:
!         break
!       r += 1
!
!
! #import psyco
! #psyco.bind(fannkuch)
!
! if len(sys.argv) > 1:
!   n = int(sys.argv[1])
! else:
!   n = 1
! print "Pfannkuchen(%d) = %ld" % (n, fannkuch(n))


Bye,
bearophile