[Shootout-list] Python Fannkuch using Splice Assignments

[Theodora Carson]

This an alternative implementation that still performs the same steps as the
reference implementation but uses Python's language feature of splice
assignments to replace loops doing the flips.

While this an elegant solution leveraging the language, it is not as fast as
the previously submitted looped version.  I post this as an example of
complex splicing.  Who knows?  Maybe Python will be able to leverage
splicing more efficiently in the future.

Kevin

#!/usr/bin/python -OO
# http://shootout.alioth.debian.org/
#
# Contributed by Kevin Carson

import sys

def fannkuch(n) :
    p = range(1, n+1)
    q = [None]*n
    maxflips = 0

    while True :
        if p[0] != 1 :
            q[:] = p[:]

            flips = 0
            while q[0] != 1 :
                j = q[0]
                i = j / 2 + j % 2

                # Flip lower & upper halves. Whether the flip set is
                # an even or odd quantity of elements is addressed by
                # adding the modulus of 2 to i in previously.
                q[:j/2],q[i:j] = q[j-1:i-1:-1],q[j/2-1::-1]

                flips += 1

            if ( flips > maxflips ) :
                maxflips = flips

        j = k = 0
        for i in xrange(1, n) :
            if p[i-1] < p[i] :
                j = i
            if (j != 0) and (p[i] > p[j-1]) :
                k = i

        if j == 0 :
            break

        p[j-1],p[k] = p[k],p[j-1]

        if ( ( n - j ) > 1 ) :
            p[j:] = p[:j-1:-1]

    return maxflips


def main() :
    if len(sys.argv) == 2 :
        n = int(sys.argv[1])
    else :
        n = 1

    print "Pfannkuchen(%d) = %ld" % (n, fannkuch(n))

main()