fannkuchredux.nim

import os, strutils

proc max(a, b: int): int =
    if a > b:
        return a
    return b

proc fannkuchredux(n: int): int =
    var perm  = newSeq[int](n)
    var perm1 = newSeq[int](n)
    var count = newSeq[int](n)
    var maxFlipsCount = 0
    var permCount = 0
    var checksum = 0
    var i: int

    for i in 0..n-1:
        perm1[i] = i

    var r = n;

    while true:
        while r != 1:
            count[r-1] = r
            dec(r)
        
        for i in 0 .. n-1:
            perm[i] = perm1[i]

        var flipsCount = 0

        var k = perm[0]
        while k != 0:
            var k2 = (k+1) shr 1
            for i in 0 .. k2-1:
                var temp = perm[i]
                perm[i] = perm[k-i]
                perm[k-i] = temp
            inc(flipsCount)
            k = perm[0]

        maxFlipsCount = max(maxFlipsCount, flipsCount);
        #if flipsCount > maxFlipsCount:
        #    maxFlipsCount = flipsCount

        var m = permCount mod 2;
        var csi = if permCount mod 2 == 0: flipsCount else: -flipsCount
        checksum += csi

        while true:
            if r == n:
                echo ($checksum)
                return maxFlipsCount

            var perm0 = perm1[0]
            i = 0
            while i < r:
                var j = i + 1
                perm1[i] = perm1[j]
                i = j
            perm1[r] = perm0
            dec(count[r])
            if count[r] > 0:
                break
            inc(r)

        inc(permCount)

var n = 7

if paramCount() > 0:
    var ns = paramStr(1)
    n = ns.parseInt

echo ("Pfannkuchen(" & $n & ") = " & $fannkuchredux(n))