You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
80 lines
2.0 KiB
80 lines
2.0 KiB
-- The Computer Language Benchmarks Game
|
|
-- http://benchmarksgame.alioth.debian.org/
|
|
-- contributed by Mike Pall
|
|
|
|
local function fannkuch(n: integer)
|
|
local p: integer[], q :integer[],
|
|
s: integer[], sign: integer,
|
|
maxflips: integer,
|
|
sum: integer = {}, {}, {}, 1, 0, 0
|
|
for i=1,n do
|
|
p[i] = i
|
|
q[i] = i
|
|
s[i] = i
|
|
end
|
|
repeat
|
|
-- Copy and flip.
|
|
local q1: integer = p[1] -- Cache 1st element.
|
|
if q1 ~= 1 then
|
|
for i=2,n do
|
|
q[i] = p[i]
|
|
end -- Work on a copy.
|
|
local flips: integer = 1
|
|
repeat
|
|
local qq: integer = q[q1]
|
|
if qq == 1 then -- ... until 1st element is 1.
|
|
sum = sum + sign*flips
|
|
if flips > maxflips then
|
|
maxflips = flips
|
|
end -- New maximum?
|
|
break
|
|
end
|
|
q[q1] = q1
|
|
if q1 >= 4 then
|
|
local i: integer, j: integer = 2, q1 - 1
|
|
repeat
|
|
q[i], q[j] = q[j], q[i];
|
|
i = i + 1;
|
|
j = j - 1;
|
|
until i >= j
|
|
end
|
|
q1 = qq;
|
|
flips = flips + 1
|
|
until false
|
|
end
|
|
-- Permute.
|
|
if sign == 1 then
|
|
p[2], p[1] = p[1], p[2]; sign = -1 -- Rotate 1<-2.
|
|
else
|
|
p[2], p[3] = p[3], p[2]; sign = 1 -- Rotate 1<-2 and 1<-2<-3.
|
|
for i=3,n do
|
|
local sx: integer = s[i]
|
|
if sx ~= 1 then
|
|
s[i] = sx-1;
|
|
break
|
|
end
|
|
if i == n then
|
|
return sum, maxflips
|
|
end -- Out of permutations.
|
|
s[i] = i
|
|
-- Rotate 1<-...<-i+1.
|
|
local t: integer = p[1];
|
|
for j=1,i do
|
|
p[j] = p[j+1]
|
|
end;
|
|
p[i+1] = t
|
|
end
|
|
end
|
|
until false
|
|
end
|
|
|
|
local n = tonumber(arg and arg[1]) or 11
|
|
ravi.compile(fannkuch, {omitArrayGetRangeCheck=1})
|
|
local t1 = os.clock()
|
|
local sum, flips = fannkuch(n)
|
|
local t2 = os.clock()
|
|
io.write(sum, "\nPfannkuchen(", n, ") = ", flips, "\n")
|
|
io.write("elapsed time in secs ", (t2-t1), "\n")
|
|
|
|
--ravi.dumplua(fannkuch)
|