-- $Id: ackermann.lua,v 1.5 2000/12/09 20:07:43 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

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

NUM = tonumber((arg and arg[1])) or 1
io.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/
-- contributed by Roberto Ierusalimschy

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

local x, y = {}, {}

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

io.write(y[1], " ", y[n], "\n")

-- $Id: wc.lua,v 1.1 2001/05/14 16:33:47 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

local cc,lc,wc = 0,0,0
for line in io.lines() do
  cc = cc + string.len(line)  -- count chars in the line
  local _,t = string.gsub(line, "%S+", "")   -- count words in the line
  wc = wc+t
  lc = lc+1            -- count lines
end
cc = cc + lc   -- count the newlines as characters

io.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/
-- contributed by Roberto Ierusalimschy

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

function try (f, arg)
  local status, err = pcall(f, arg)
  if not status then return err end
end


local HI = 0
local 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, 0)  -- 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, 0)  -- rethrow
  end
end


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


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

print(string.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/
-- contributed by Roberto Ierusalimschy

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
print(fib(N))

-- $Id: hash.lua,v 1.1 2000/12/10 00:48:41 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

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

local X={}
for i=1,n do
  X[string.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/
-- contributed by Roberto Ierusalimschy

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

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

io.write(string.format("%d %d %d %d\n", hash1["foo_1"], hash1["foo_9999"],
         hash2["foo_1"], hash2["foo_9999"]))

#!/usr/local/bin/lua-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

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

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

function heapsort(n, ra)
  local j, i, rra
  local l = math.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)

io.write(string.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/
-- contributed by Roberto Ierusalimschy

print("hello world")

-- $Id: lists.lua,v 1.6 2001/01/13 22:04:18 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

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

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

function List:new ()
  local n = {}
  self.__index = self
  setmetatable(n, self)
  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/
-- contributed by 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=1,rows do
    local row = {}
    for j=1,cols 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=1,rows do
    local m3i = {}
    m3[i] = m3i
    local m1i = m1[i]
    for j=1,cols do
      local rowj = 0
      for k=1,cols do
        rowj = rowj + m1i[k] * m2[k][j]
      end
      m3i[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
io.write(string.format("%d %d %d %d\n", mm[1][1], mm[3][4], mm[4][3], mm[5][5]))

-- $Id: methcall.lua,v 1.2 2000/12/24 22:04:51 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

--------------------------------------------------------------
-- Toggle class
--------------------------------------------------------------

Toggle = {}

function Toggle:value ()
  return self.state
end

function Toggle:activate ()
  self.state = not self.state
  return self
end

function Toggle:new (start_state)
  local o = {state = start_state}
  self.__index =self
  setmetatable(o, self)
  return o
end


--------------------------------------------------------------
-- NthToggle class
--------------------------------------------------------------

NthToggle = Toggle:new()

function NthToggle:activate ()
  self.counter = self.counter + 1
  if self.counter >= self.count_max then
    self.state = not self.state
    self.counter = 0
  end
  return self
end

function NthToggle:new (start_state, max_counter)
  local o = Toggle.new(self, start_state)
  o.count_max = max_counter
  o.counter = 0
  return o
end


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

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

  local val = 1
  local toggle = Toggle:new(val)
  for i=1,N do
    val = toggle:activate():value()
  end
  print(val and "true" or "false")
    
  val = 1
  local ntoggle = NthToggle:new(val, 3)
  for i=1,N do
    val = ntoggle:activate():value()
  end
  print(val and "true" or "false")
end

main()

-- $Id: nestedloop.lua,v 1.2 2001/01/12 01:45:42 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

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
print(x)

-- $Id: objinst.lua,v 1.3 2001/07/11 17:18:08 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy



--------------------------------------------------------------
-- Toggle class
--------------------------------------------------------------

Toggle = {}

function Toggle:value ()
  return self.state
end

function Toggle:activate ()
  self.state = not self.state
  return self
end

function Toggle:new (start_state)
  local o = {state = start_state}
  self.__index = self
  setmetatable(o, self)
  return o
end


--------------------------------------------------------------
-- NthToggle class
--------------------------------------------------------------

NthToggle = Toggle:new()

function NthToggle:activate ()
  self.counter = self.counter + 1
  if self.counter >= self.count_max then
    self.state = not self.state
    self.counter = 0
  end
  return self
end

function NthToggle:new (start_state, max_counter)
  local o = Toggle.new(self, start_state)
  o.count_max = max_counter
  o.counter = 0
  return o
end


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

function main ()
    local N = tonumber((arg and arg[1])) or 1
    local toggle = Toggle:new(1)
    for i=1,5 do
      toggle:activate()
      print(toggle:value() and "true" or "false")
    end
    for i=1,N do
      toggle = Toggle:new(1)
    end

    print("")

    local ntoggle = NthToggle:new(1, 3)
    for i=1,8 do
      ntoggle:activate()
      print(toggle:value() and "true" or "false")
    end
    for i=1,N do
      ntoggle = NthToggle:new(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/
-- contributed by Roberto Ierusalimschy

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

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

local N = tonumber((arg and arg[1])) or 1
local result = 0
for i=1, N do
    result = gen_random(100)
end
io.write(string.format("%.9f\n", result))

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

local text = io.read("*a")

-- make sure text does not start with a number
text = "\n" .. text

-- pattern is: not a digit, optional (, 3 digits, optional ),
-- space, 3 digits, space or hyphen, 4 digits, not a digit
local pattern = "%D(%(?)(%d%d%d)(%)?) (%d%d%d)[- ](%d%d%d%d)%f[%D]"

local N = tonumber((arg and arg[1])) or 1
local count = 0
for i=N,1,-1 do
  for open,area,close,exch,digits in string.gfind(text, pattern) do
      if (open == '(') == (close == ')') then
        local tel = "("..area..") "..exch.."-"..digits
        if i == 1 then
          count = count+1
          io.write(count, ": ", tel, "\n")
        end
      end
    end
end

#!/usr/local/bin/lua-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy

local lines = {}
local nl = 0

for l in io.lines() do
    nl = nl + 1
    lines[nl] = l
end

for i=nl,1,-1 do
    io.write(lines[i], "\n")
end

-- $Id: sieve.lua,v 1.9 2001/05/06 04:37:45 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy
--
-- 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=1,num do
      count = 0
      for i=2,8192 do
        flags[i] = true
      end
      for i=2,8192 do
        if flags[i] then
          for k=i+i, 8192, i do
            flags[k] = false
          end
        count = count + 1    
      end
      end
    end
end

NUM = tonumber((arg and arg[1])) or 1
count = 0
main(NUM)
io.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
-- contributed by Roberto Ierusalimschy

local dict = {}
for line in io.lines("Usr.Dict.Words") do
  dict[line] = true
end

for word in io.lines() do
  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/
-- contributed by Roberto Ierusalimschy

local nums = {}
local n = 0
local sum = 0
for line in io.lines() do
  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 + math.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 = math.sqrt(variance)
if variance ~= 0 then
  skew = skew / (n * variance * standard_deviation)
  kurtosis = kurtosis/(n * variance * variance) - 3.0
end

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

io.write(string.format("n:                  %d\n", n))
io.write(string.format("median:             %f\n", median))
io.write(string.format("mean:               %f\n", mean))
io.write(string.format("average_deviation:  %f\n", average_deviation))
io.write(string.format("standard_deviation: %f\n", standard_deviation))
io.write(string.format("variance:           %f\n", variance))
io.write(string.format("skew:               %f\n", skew))
io.write(string.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/
-- contributed by Roberto Ierusalimschy

-- this version uses a custom string buffer

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

Buffer = {""}

function Buffer:new ()
  local new = {}
  self.__index = self
  setmetatable(new, self)
  return new
end

function Buffer:add (s)
  table.insert(self, s)    -- push 's' into the the stack
  for i=table.getn(self)-1, 1, -1 do
    if string.len(self[i]) > string.len(self[i+1]) then
      break
    end
    self[i] = self[i] .. table.remove(self)
  end
end

function Buffer:close ()
  self[1] = table.concat(self)
  table.setn(self, 1)   -- now there is only one element
  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
io.write(string.len(buff:close()), "\n")

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

local sum = 0
for line in io.lines() do
  sum = sum + line
end
print(sum)

-- $Id: wordfreq.lua,v 1.3 2000/12/21 03:20:30 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- contributed 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

local BUFSIZE = 2^12

while true do
  local lines, rest = io.read(BUFSIZE, "*l")
  if lines == nil then break end
  lines = lines..(rest or '')    -- ensures whole lines
  for w in string.gfind(string.lower(lines), "(%l+)") do
    local cw = count[w]
    if not cw then     -- first occurrence?
      cw = 0
      table.insert(words, w)
    end
    count[w] = cw + 1
  end
end

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

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