Lua Conway's Game of Life

gistfile1.lua

-- Author: Michael-Keith Bernard
-- Date: July 26, 2012
--
-- Game of Life
--
-- Ported from this Clojure implementation:
--
--  (defn neighbours [[x y]]
--    (for [dx [-1 0 1] dy (if (zero? dx) [-1 1] [-1 0 1])]
--      [(+ dx x) (+ dy y)]))
--
--  (defn step [cells]
--    (set (for [[loc n] (frequencies (mapcat neighbours cells))
--               :when (or (= n 3) (and (= n 2) (cells loc)))]
--           loc)))
--
-- Notes: This implementation is particularly inefficient because it relies on 2
-- features that don't exist in Lua natively:
--   1) pairs/tuples - in Clojure, lists and vectors can be compared for
--      equality and therefore offer a good substitute for tuples, eg:
--        (= [1 2] [1 2]) ;true
--      Lua tables are not comparable in this fashion:
--        {1, 2} == {1, 2} --false
--   2) sets - Clojure has a native set type:
--        #{[1 2] [3 4]}
--      Lua doesn't have a set, but one can be simulated for primitves easily:
--        { "foo" = true, "bar" = true }
--      However, because tables aren't comparable, there is no way to use the
--      above set notation with tables without manually checking for set
--      membership on every insert which is very slow since every new element
--      has to be deep-compared to existing members of the set.

function map(f, t)
  local res = {}
  for _, v in ipairs(t) do
    res[#res+1] = f(v)
  end
  return res
end

function each(f, t)
  map(f, t)
  return t
end

function concat(t)
  local res = {}
  for _, a in ipairs(t) do
    for _, b in ipairs(a) do
      res[#res+1] = b
    end
  end
  return res
end

function mapcat(f, t)
  return concat(map(f, t))
end

function eq(a, b)
  local ta, tb = type(a), type(b)
  if ta ~= tb then return false end
  if ta ~= "table" and tb ~= "table" then return a == b end

  for k, v in pairs(a) do
    local o = b[k]
    if o == nil or not eq(v, o) then return false end
  end

  for k, v in pairs(b) do
    local o = a[k]
    if o == nil or not eq(v, o) then return false end
  end

  return true
end

function key_for(t, key)
  for k, _ in pairs(t) do
    if eq(k, key) then
      return k
    end
  end
  return nil
end

function has_item(t, item)
  for _, v in ipairs(t) do
    if eq(v, item) then
      return true
    end
  end
  return false
end

function freq(t)
  local freqs = {}
  each(function(e)
    local key = key_for(freqs, e)
    if key ~= nil then
      freqs[key] = freqs[key] + 1
    else
      freqs[e] = 1
    end
  end, t)
  return freqs
end

-- Conway's Game of Life

function neighbors(point)
  local n = {}
  for _, dx in ipairs({-1, 0, 1}) do
    for _, dy in ipairs({-1, 0, 1}) do
      if not (dx == 0 and dy == 0) then
        n[#n+1] = { point[1] + dx, point[2] + dy }
      end
    end
  end
  return n
end

function step(cells)
  local new_cells = {}
  for loc, cnt in pairs(freq(mapcat(neighbors, cells))) do
    if cnt == 3 or (cnt == 2 and has_item(cells, loc)) then
      new_cells[#new_cells+1] = loc
    end
  end
  return new_cells
end

function prune(cells, w, h)
  local new_cells = {}
  for _, loc in ipairs(cells) do
    local x, y = loc[1], loc[2]
    if (x >= 0 and x <= w) and (y >= 0 and y <= h) then
      new_cells[#new_cells+1] = loc
    end
  end
  return new_cells
end

function render(board, w, h)
  for i = 1, h do
    for j = 1, w do
      if has_item(board, {j, i}) then
        io.write("#")
      else
        io.write(".")
      end
      io.write(" ")
    end
    io.write("\n")
  end
  io.write("\n")
end

function conway(w, h)
  local board = {}
  while #board < (w*h/4) do
    local e = { math.random(w), math.random(h) }
    if not has_item(board, e) then
      board[#board+1] = e
    end
  end

  local gen = 0
  while gen < 100 do
    gen = gen + 1
    os.execute("clear")
    render(board, w, h)
    board = prune(step(board), w, h)
    os.execute("sleep .1")
  end
  conway(w, h)
end

math.randomseed(os.time())
conway(15, 15)