-- $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")

-- $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")

-- $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")

-- $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))

-- $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")

-- $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)

-- $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"]))

#!/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]))

-- $Id: hello.lua,v 1.1 2001/06/17 22:00:34 doug Exp $
-- http://www.bagley.org/~doug/shootout/

write("hello world\n")

-- $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)

-- $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]))

-- $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()

-- $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")

-- $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()

-- $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))

-- $Id: regexmatch.lua,v 1.4 2000/12/09 20:07:45 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy

text = read("*a")

-- 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

#!/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

-- $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")

-- $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

assert(readfrom("Usr.Dict.Words"))
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

-- $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))

-- $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

function Buffer:add (s)
  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
  buff:add("hello\n")
end
write(strlen(buff:close()), "\n")

-- $Id: sumcol.lua,v 1.2 2000/10/07 08:41:44 doug Exp $
-- http://www.bagley.org/~doug/shootout/

sum = 0
line = read()
while line ~= nil do
    sum = sum + line
    line = read()
end
write(sum, "\n")

-- $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