fannkuch-redux Toit program
source code
/* The Computer Language Benchmarks game
https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
transliterated from Mike Pall's Lua program by Isaac Gouy
*/
main args:
n := args.size == 1 ? int.parse args[0] : 0
pf := fannkuch n
print "$pf[0]\nPfannkuchen($n) = $pf[1]"
fannkuch n/int -> List:
p := ByteArray n; q := ByteArray n; s := ByteArray n
sign := 1; maxflips := 0; sum := 0; m := n - 1
n.repeat: p[it] = it; q[it] = it; s[it] = it
while true:
// Copy and flip.
q0 := p[0] // Cache 0th element.
if q0 != 0:
for i := 1; i < n; i++: q[i] = p[i] // Work on a copy.
flips := 1
while true:
qq := q[q0]
if qq == 0: // ... until 0th element is 0.
sum += sign * flips
if flips > maxflips: maxflips = flips // New maximum?
break
q[q0] = q0
if q0 >= 3:
i := 1; j := q0 - 1
while i < j: t := q[i]; q[i] = q[j]; q[j] = t; i++; j--
q0 = qq; flips++
// Permute.
if sign == 1: // Rotate 0<-1.
t := p[1]; p[1] = p[0]; p[0] = t; sign = -1
else: // Rotate 0<-1 and 0<-1<-2.
t := p[1]; p[1] = p[2]; p[2] = t; sign = 1
for i := 2; i < n; i++:
sx := s[i]
if sx != 0:
s[i] = sx - 1; break
if i == m: return [sum, maxflips] // Out of permutations.
s[i] = i // Rotate 0<-...<-i+1.
t = p[0]; for j := 0; j <= i; j++: p[j] = p[j+1]
p[i+1] = t
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
v2.0.0-alpha.146
Wed, 24 Apr 2024 22:18:45 GMT
MAKE:
cp -r Include/toit/.packages .
cp -r Include/toit/package.lock .
cp -r Include/toit/package.yaml .
/opt/src/toit/bin/toit.compile -O2 --strip -o fannkuchredux.toit_run fannkuchredux.toit
1.40s to complete and log all make actions
COMMAND LINE:
./fannkuchredux.toit_run 12
PROGRAM OUTPUT:
3968050
Pfannkuchen(12) = 65