Skip to content

Instantly share code, notes, and snippets.

@gozzoo
Created August 10, 2011 09:30
Show Gist options
  • Save gozzoo/1136445 to your computer and use it in GitHub Desktop.
Save gozzoo/1136445 to your computer and use it in GitHub Desktop.
fannkuch-redux Go program source code
package main
import (
"fmt"
"os"
"strconv"
)
func max(a, b int ) int {
if a > b {
return a
}
return b;
}
func fannkuchredux(n int) int {
perm := make([]int, n)
perm1 := make([]int, n)
count := make([]int, n)
maxFlipsCount := 0
permCount := 0;
checksum := 0;
for i := 0; i < n; i++ {
perm1[i] = i
}
r := n
for true {
for r != 1 {
count[r-1] = r
r -= 1
}
for i := 0; i < n; i += 1 {
perm[i] = perm1[i]
}
flipsCount := 0;
for k := perm[0]; k != 0; k = perm[0] {
k2 := (k+1) >> 1
for i := 0; i < k2; i++ {
temp := perm[i]
perm[i] = perm[k-i];
perm[k-i] = temp
}
flipsCount += 1
}
maxFlipsCount = max(maxFlipsCount, flipsCount)
csi := flipsCount
if permCount % 2 != 0 {
csi = -flipsCount
}
checksum += csi
for true {
if r == n {
fmt.Printf("%d\n", checksum)
return maxFlipsCount
}
perm0 := perm1[0]
i := 0;
for i < r {
j := i + 1;
perm1[i] = perm1[j]
i = j
}
perm1[r] = perm0
count[r] = count[r] - 1
if count[r] > 0 {
break
}
r++;
}
permCount++;
}
return 0;
}
func main() {
n := 7
if len(os.Args) > 1 {
v, err := strconv.Atoi(os.Args[1])
if err != nil {
fmt.Printf( "error: %s\n", err.String() )
return
}
n = v
}
fmt.Printf("Pfannkuchen(%d) = %d\n", n, fannkuchredux(n));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment