[The Original Shootout]   [NEWS]   [FAQ]   [Methodology]   [Platform Details]   [Acknowledgements]   [Scorecard]
All Source For lua
Ackermann's Function
```-- \$Id: ackermann.lua,v 1.5 2000/12/09 20:07:43 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

function Ack(M, N)
if (M == 0) then
return( N + 1 )
end
if (N == 0) then
return( Ack(M - 1, 1) )
end
return( Ack(M - 1, Ack(M, (N - 1))) )
end

NUM = tonumber((arg and arg[1])) or 1
write("Ack(3,", NUM ,"): ", Ack(3,NUM), "\n")

```
Array Access
```-- \$Id: ary3.lua,v 1.1 2001/05/31 02:27:48 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

local n = tonumber((arg and arg[1]) or 1)

local x, y = {}, {}
local last = n - 1

for i=0,last do
x[i] = i + 1
y[i] = 0
end
for k=1,1000 do
for j=last,0,-1 do
y[j] = y[j] + x[j]
end
end

write(y[0], " ", y[last], "\n")
```
Count Lines/Words/Chars
```-- \$Id: wc.lua,v 1.1 2001/05/14 16:33:47 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- from Roberto Ierusalimschy

BUFSIZE = 2^12

local cc,lc,wc = 0,0,0
while 1 do
local lines, rest = read(BUFSIZE, "*l")
if lines == nil then break end
if rest then lines = lines..rest..'\n' end
cc = cc+strlen(lines)
local _,t = gsub(lines, "%S+", "")   -- count words in the line
wc = wc+t
_,t = gsub(lines, "\n", "\n")   -- count newlines in the line
lc = lc+t
end

write(lc, " ", wc, " ", cc, "\n")
```
Exception Mechanisms
```-- \$Id: except.lua,v 1.1 2001/01/16 14:27:55 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- from Roberto Ierusalimschy

-- uses `call' to catch errors; return the error message
-- (or nil if there are no errors)

function try (f, ...)
call(f, arg, "x", function (msg) %arg.msg = msg end)
return arg.msg
end

HI = 0
LO = 0

function some_function (n)
local res = try(hi_function, n)
if res then print("We shouldn't get here: " .. res) end
end

function hi_function (n)
local res = try(lo_function, n)
if res == "Hi_Exception" then HI = HI+1
elseif res then error(res)  -- rethrow
end
end

function lo_function (n)
local res = try(blowup, n)
if res == "Lo_Exception" then LO = LO+1
elseif res then error(res)  -- rethrow
end
end

function blowup (n)
if mod(n,2) ~= 0 then error "Lo_Exception"
else error "Hi_Exception"
end
end

N = (arg and arg[1]) or 1
for i=1,N do
some_function(i)
end

print(format("Exceptions: HI=%d / LO=%d", HI, LO))
```
Fibonacci Numbers
```-- \$Id: fibo.lua,v 1.2 2000/12/24 19:10:50 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

function fib(n)
if (n < 2) then return(1) end
return( fib(n-2) + fib(n-1) )
end

N = tonumber((arg and arg[1])) or 1
write(fib(N), "\n")
```
Hash (Associative Array) Access
```-- \$Id: hash.lua,v 1.1 2000/12/10 00:48:41 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- Author: Roberto Ierusalimschy

local n = tonumber((arg and arg[1]) or 1)

local X={}
for i=1,n do
X[format("%x", i)] = i
end

local c = 0

for i=n,1,-1 do
if X[i..''] then c = c+1 end
end

print(c)
```
Hashes, Part II
```-- \$Id: hash2.lua,v 1.2 2001/01/11 14:52:55 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- with help from Roberto Ierusalimschy

local n = tonumber((arg and arg[1]) or 1)

local hash1={}
for i=0,10000 do
hash1["foo_"..i] = i
end
local hash2={}
for i=1,n do
for k,v in hash1 do
hash2[k] = v + (hash2[k] or 0)
end
end

write(format("%d %d %d %d\n", hash1["foo_1"], hash1["foo_9999"],
hash2["foo_1"], hash2["foo_9999"]))
```
Heapsort
```#!/usr/local/bin/lua-- \$Id: heapsort.lua,v 1.10 2001/05/08 02:46:59 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

local IM = 139968
local IA =   3877
local IC =  29573

LAST = 42
function gen_random(max)
LAST = mod((LAST * %IA + %IC), %IM)
return( (max * LAST) / %IM )
end

function heapsort(n, ra)
local j, i, rra
local l = floor(n/2) + 1
local ir = n;
while 1 do
if l > 1 then
l = l - 1
rra = ra[l]
else
rra = ra[ir]
ra[ir] = ra[1]
ir = ir - 1
if (ir == 1) then
ra[1] = rra
return
end
end
i = l
j = l * 2
while j <= ir do
if (j < ir) and (ra[j] < ra[j+1]) then
j = j + 1
end
if rra < ra[j] then
ra[i] = ra[j]
i = j
j = j + i
else
j = ir + 1
end
end
ra[i] = rra
end
end

local ary = {}
local N = (tonumber((arg and arg[1])) or 1)

for i=1, N do
ary[i] = gen_random(1.0)
end

heapsort(N, ary)

write(format("%0.10f\n", ary[N]))
```
Hello World
```-- \$Id: hello.lua,v 1.1 2001/06/17 22:00:34 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

write("hello world\n")
```
List Operations
```-- \$Id: lists.lua,v 1.6 2001/01/13 22:04:18 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy

--------------------------------------------------------------
-- List module
-- defines a prototipe for lists
--------------------------------------------------------------

List = {first = 0, last = -1}

function List:new ()
local n = {}
for k,v in self do n[k] = v end
return n
end

function List:length ()
return self.last - self.first + 1
end

function List:pushleft (value)
local first = self.first - 1
self.first = first
self[first] = value
end

function List:pushright (value)
local last = self.last + 1
self.last = last
self[last] = value
end

function List:popleft ()
local first = self.first
if first > self.last then error"list is empty" end
local value = self[first]
self[first] = nil  -- to allow collection
self.first = first+1
return value
end

function List:popright ()
local last = self.last
if self.first > last then error"list is empty" end
local value = self[last]
self[last] = nil  -- to allow collection
self.last = last-1
return value
end

function List:reverse ()
local i, j = self.first, self.last
while i<j do
self[i], self[j] = self[j], self[i]
i = i+1
j = j-1
end
end

function List:equal (otherlist)
if self:length() ~= otherlist:length() then return nil end
local diff = otherlist.first - self.first
for i1=self.first,self.last do
if self[i1] ~= otherlist[i1+diff] then return nil end
end
return 1
end

-----------------------------------------------------------
-----------------------------------------------------------

-- Some tests

function test ()
local SIZE = 10000
-- create a list with elements 1..SIZE
local l1 = List:new()
for i=1,SIZE do
l1:pushright(i)
end
-- creates a copy of l1
local l2 = l1:new()
-- remove each individual item from left side of l2 and
-- append to right side of l3 (preserving order)
local l3 = List:new()
while l2:length() > 0 do
l3:pushright(l2:popleft())
end
-- remove each individual item from right side of l3 and
-- append to right side of l2 (reversing list)
while l3:length() > 0 do
l2:pushright(l3:popright())
end
-- reverse l1 in place
l1:reverse()
-- compare Li1 and Li2 for equality
-- and return length of the list
if not l1:equal(l2) then return nil
else return l1:length()
end
end

N = tonumber((arg and arg[1])) or 1
for i=1, N do
result = test()
end
print(result)
```
Matrix Multiplication
```-- \$Id: matrix.lua,v 1.2 2001/01/13 14:47:43 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- with help from Roberto Ierusalimschy

local n = tonumber((arg and arg[1]) or 1)

local size = 30

function mkmatrix(rows, cols)
local count = 1
local mx = {}
for i=0,(rows - 1) do
local row = {}
for j=0,(cols - 1) do
row[j] = count
count = count + 1
end
mx[i] = row
end
return(mx)
end

function mmult(rows, cols, m1, m2)
local m3 = {}
for i=0,(rows-1) do
m3[i] = {}
for j=0,(cols-1) do
local rowj = 0
for k=0,(cols-1) do
rowj = rowj + m1[i][k] * m2[k][j]
end
m3[i][j] = rowj
end
end
return(m3)
end

local m1 = mkmatrix(size, size)
local m2 = mkmatrix(size, size)
for i=1,n do
mm = mmult(size, size, m1, m2)
end
write(format("%d %d %d %d\n", mm[0][0], mm[2][3], mm[3][2], mm[4][4]))
```
Method Calls
```-- \$Id: methcall.lua,v 1.2 2000/12/24 22:04:51 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

-- set up a simple object inheritance
settagmethod(tag{}, "index", function (object, field)
if field == "parent" then return nil end
if type(object.parent) ~= "table" then return nil end
return object.parent[field]
end)

--------------------------------------------------------------
-- Toggle module
--------------------------------------------------------------

function new_Toggle(start_state)
return {
bool = start_state,
value = function (self)
return self.bool
end,
activate = function(self)
self.bool = not self.bool
return self
end,
}
end

--------------------------------------------------------------
-- NthToggle module
--------------------------------------------------------------

function new_NthToggle(start_state, max_counter)
return {
parent = new_Toggle(start_state),
count_max = max_counter,
counter = 0,
activate = function (self)
self.counter = self.counter + 1
if self.counter >= self.count_max then
self.parent:activate()
self.counter = 0
end
return self
end
}
end

-----------------------------------------------------------
-- main
-----------------------------------------------------------

function main ()
local N = tonumber((arg and arg[1])) or 1

local val = 1
local toggle = new_Toggle(val)
for i=1,N do
val = toggle:activate():value()
end
if toggle:value() then write("true\n") else write("false\n") end

val = 1
local ntoggle = new_NthToggle(val, 3)
for i=1,N do
val = ntoggle:activate():value()
end
if ntoggle:value() then write("true\n") else write("false\n") end
end

main()
```
Nested Loops
```-- \$Id: nestedloop.lua,v 1.2 2001/01/12 01:45:42 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

local n = tonumber((arg and arg[1]) or 1)
local x = 0
for a=1,n do
for b=1,n do
for c=1,n do
for d=1,n do
for e=1,n do
for f=1,n do
x = x + 1
end
end
end
end
end
end
write(x,"\n")
```
Object Instantiation
```-- \$Id: objinst.lua,v 1.3 2001/07/11 17:18:08 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- with help from Roberto Ierusalimschy

-- set up a simple object inheritance
settagmethod(tag{}, "index", function (object, field)
if field ~= "parent" then
local p = object.parent
return p and p[field]
end
end)

--------------------------------------------------------------
-- Toggle module
--------------------------------------------------------------

function new_Toggle(start_state)
return {
bool = start_state,
value = function (self)
return self.bool
end,
activate = function(self)
self.bool = not self.bool
return self
end,
}
end

--------------------------------------------------------------
-- NthToggle module
--------------------------------------------------------------

function new_NthToggle(start_state, max_counter)
return {
parent = new_Toggle(start_state),
count_max = max_counter,
counter = 0,
activate = function (self)
self.counter = self.counter + 1
if self.counter >= self.count_max then
self.parent:activate()
self.counter = 0
end
return self
end
}
end

-----------------------------------------------------------
-- main
-----------------------------------------------------------

function main ()
local N = tonumber((arg and arg[1])) or 1
local toggle = new_Toggle(1)
for i=1,5 do
toggle:activate()
if toggle:value() then write("true\n") else write("false\n") end
end
for i=1,N do
toggle = new_Toggle(1)
end

write("\n")

local ntoggle = new_NthToggle(1, 3)
for i=1,8 do
ntoggle:activate()
if ntoggle:value() then write("true\n") else write("false\n") end
end
for i=1,N do
ntoggle = new_NthToggle(1, 3)
end
end

main()
```
Random Number Generator
```-- \$Id: random.lua,v 1.12 2001/05/08 01:36:50 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy

local IM = 139968
local IA = 3877
local IC = 29573

LAST = 42
function gen_random(max)
LAST = mod((LAST * %IA + %IC), %IM)
return( (max * LAST) / %IM )
end

local N = tonumber((arg and arg[1])) or 1
local result = 0
for i=N, 1, -1 do
result = gen_random(100)
end
write(format("%.9f\n", result))
```
Regular Expression Matching
```-- \$Id: regexmatch.lua,v 1.4 2000/12/09 20:07:45 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy

-- I added the following line and slightly modified the pattern
-- match below so that the program will reject the case:
-- 1(111) 111-1111 (due to preceeding digit)
-- (Doug)
text = gsub(gsub(text, "^", "   "), "\n", "\n   ")

N = tonumber((arg and arg[1])) or 1
count = 0
while N > 0 do
gsub(text,"%D(%D)(%d%d%d)(%)?) (%d%d%d)[- ](%d+)",
function (A,area,B,exch,digits)
if (A == '(') == (B == ')') and strlen(digits) == 4 then
local tel = "("..area..") "..exch.."-"..digits
if N == 1 then
count = count+1
write(count, ": ", tel, "\n")
end
end
end)
N = N-1
end
```
Reverse a File
```#!/usr/local/bin/lua-- \$Id: reversefile.lua,v 1.3 2001/05/14 01:52:38 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

local lines = {}
local w = write
nl = 0

gsub(read("*a"), "([^\n]+\n)", function (l)
%lines[nl] = l
nl = nl + 1
end)

nl = nl - 1
for i=nl,0,-1 do
w(lines[i])
end
```
Sieve of Erathostenes
```-- \$Id: sieve.lua,v 1.9 2001/05/06 04:37:45 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
--
-- Roberto Ierusalimschy pointed out the for loop is much
-- faster for our purposes here than using a while loop.

function main(num)
local flags = {}
for num=num,1,-1 do
count = 0
for i=2,8192 do
flags[i] = 1
end
for i=2,8192 do
if flags[i] == 1 then
k = 0
for k=i+i, 8192, i do
flags[k] = 0
end
count = count + 1
end
end
end
end

NUM = tonumber((arg and arg[1])) or 1
count = 0
main(NUM)
write("Count: ", count, "\n")
```
Spell Checker
```-- \$Id: spellcheck.lua,v 1.2 2001/01/23 01:30:42 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- based on code from Roberto Ierusalimschy

local dict = {}
while 1 do
local line = read()
if line == nil then break end
dict[line] = 1
end
readfrom()    -- closes dictionary

while 1 do
local word = read()
if word == nil then break end
if not dict[word] then print(word) end
end
```
Statistical Moments
```-- \$Id: moments.lua,v 1.2 2001/01/05 01:35:56 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy

local nums = {}
local n = 0
local sum = 0
while 1 do
local line = read()
if line == nil then break end
line = line+0        -- convert line to number
sum = sum + line
n = n + 1
nums[n] = line
end

local mean = sum/n

local average_deviation, variance, skew, kurtosis = 0, 0, 0, 0

for i = 1, n do
local deviation = nums[i] - mean
average_deviation = average_deviation + abs(deviation)
variance = variance + deviation^2
skew = skew + deviation^3
kurtosis = kurtosis + deviation^4
end

average_deviation = average_deviation/n
variance = variance/(n-1)
local standard_deviation = sqrt(variance)
if variance ~= 0 then
skew = skew / (n * variance * standard_deviation)
kurtosis = kurtosis/(n * variance * variance) - 3.0
end

sort(nums)
local mid = floor(n/2)
local median
if mod(n,2) == 1 then
median = nums[mid+1]
else
median = (nums[mid] + nums[mid+1])/2
end

write(format("n:                  %d\n", n))
write(format("median:             %f\n", median))
write(format("mean:               %f\n", mean))
write(format("average_deviation:  %f\n", average_deviation))
write(format("standard_deviation: %f\n", standard_deviation))
write(format("variance:           %f\n", variance))
write(format("skew:               %f\n", skew))
write(format("kurtosis:           %f\n", kurtosis))
```
String Concatenation
```-- \$Id: strcat.lua,v 1.2 2001/01/31 03:38:54 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- from Roberto Ierusalimschy

-- this version uses a custom string buffer

------------------------------------------------------------------
-- Buffer library
------------------------------------------------------------------

Buffer = {n=0}

function Buffer:new ()
local new = {}
for k,v in self do new[k] = v end
return new
end

tinsert(self, s)
local i = self.n
for i=self.n-1, 1, -1 do
if strlen(self[i]) > strlen(self[i+1]) then break end
local top = tremove(self)
self[i] = self[i]..top
end
end

function Buffer:close ()
for i=self.n-1, 1, -1 do
local top = tremove(self)
self[i] = self[i]..top
end
return self[1]
end

------------------------------------------------------------------
-- Test
------------------------------------------------------------------

local n = tonumber((arg and arg[1]) or 1)
local buff = Buffer:new()
for i=1,n do
end
write(strlen(buff:close()), "\n")
```
Sum a Column of Integers
```-- \$Id: sumcol.lua,v 1.2 2000/10/07 08:41:44 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

sum = 0
while line ~= nil do
sum = sum + line
end
write(sum, "\n")
```
Word Frequency Count
```-- \$Id: wordfreq.lua,v 1.3 2000/12/21 03:20:30 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy

-- this version reads 4K chunks of input at a time

local words = {}   -- list of all words (for sorting)
local count = {}   -- count occurrences of each word

BUFSIZE = 2^12

while 1 do
local lines, rest = read(BUFSIZE, "*l")
if lines == nil then break end
lines = lines..(rest or '')    -- ensures whole lines
gsub(strlower(lines), "(%l+)", function (w)
local cw = %count[w]
if cw == nil then     -- first occurrence?
cw = 0
tinsert(%words, w)
end
%count[w] = cw + 1
end)
end

sort(words, function (a,b)
return  %count[a] > %count[b]  or
(%count[a] == %count[b] and a > b)
end)

for i=1,getn(words) do
local w = words[i]
write(format("%7d\t%s\n", count[w], w))
end
```