summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPhilipp Gesang <pgesang@ix.urz.uni-heidelberg.de>2010-08-05 21:46:29 +0200
committerPhilipp Gesang <pgesang@ix.urz.uni-heidelberg.de>2010-08-05 21:46:29 +0200
commit5983274b083d05aacadfaf6c0e00d65115fb2de4 (patch)
treeca76969b4b8664b11e54d6a6646853ca272a469c
downloadautomata-backgrounds-5983274b083d05aacadfaf6c0e00d65115fb2de4.tar.gz
init. life algorithm and cli pretty printer
-rw-r--r--.hgignore37
-rw-r--r--examples/10x10_glider.gol10
-rw-r--r--examples/glider_gen-p55.gol21
-rw-r--r--life.lua326
-rw-r--r--run.lua111
5 files changed, 505 insertions, 0 deletions
diff --git a/.hgignore b/.hgignore
new file mode 100644
index 0000000..dbf151e
--- /dev/null
+++ b/.hgignore
@@ -0,0 +1,37 @@
+syntax:glob
+*.swp
+*.pdf
+*.aux
+*.bbl
+*.log
+*.url
+*.toc
+*.ind
+*.out
+*.dvi
+*.blg
+*.4ct
+*.idv
+*.html
+*.css
+*.4tc
+*.lg
+*.xref
+*.idx
+*.tmp
+*.djvu
+*.ps
+*.make
+*.d
+*.fls
+*-blx.bib
+*.temp
+*.latexmain
+*.snm
+*.nav
+*.vrb
+*.top
+*.tuc
+*.swo
+*.png
+*.citator
diff --git a/examples/10x10_glider.gol b/examples/10x10_glider.gol
new file mode 100644
index 0000000..2c7875c
--- /dev/null
+++ b/examples/10x10_glider.gol
@@ -0,0 +1,10 @@
+0000000000
+0000000000
+0000000000
+0001000000
+0000100000
+0011100000
+0000000000
+0000000000
+0000000000
+0000000000
diff --git a/examples/glider_gen-p55.gol b/examples/glider_gen-p55.gol
new file mode 100644
index 0000000..739992a
--- /dev/null
+++ b/examples/glider_gen-p55.gol
@@ -0,0 +1,21 @@
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000010000000000000000000000
+00000000000010000000000000000000000
+00000000001110000000000000000000000
+00000000000000000000000000000000000
+00000000000000001110000000000000000
+00000000000000000100000000000000000
+00000000000000000000001110000000000
+00000000000000000000001000000000000
+00000000000000000000001000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
+00000000000000000000000000000000000
diff --git a/life.lua b/life.lua
new file mode 100644
index 0000000..aa444c4
--- /dev/null
+++ b/life.lua
@@ -0,0 +1,326 @@
+--
+--------------------------------------------------------------------------------
+-- FILE: life.lua
+-- USAGE: ./life.lua
+-- DESCRIPTION: Conway's Game of Life?
+-- OPTIONS: ---
+-- REQUIREMENTS: ---
+-- BUGS: ---
+-- NOTES: ---
+-- AUTHOR: Philipp Gesang (Phg), <megas.kapaneus@gmail.com>
+-- COMPANY:
+-- VERSION: 1.0
+-- CREATED: 05/08/10 12:03:11 CEST
+-- REVISION: ---
+--------------------------------------------------------------------------------
+--
+
+gol = {}
+
+gol.helpers = {}
+
+local C, Ct, P, R, S, match = lpeg.C, lpeg.Ct, lpeg.P, lpeg.R, lpeg.S, lpeg.match
+
+-- http://lua-users.org/lists/lua-l/2009-06/msg00343.html
+gol.helpers.utfchar = R("\000\127") +
+ R("\194\223") * R("\128\191") +
+ R("\224\240") * R("\128\191") * R("\128\191") +
+ R("\241\244") * R("\128\191") * R("\128\191") * R("\128\191")
+
+
+-- by Roberto, captures everything in a table
+-- http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html
+function gol.helpers.split (s, sep)
+ sep = P(sep)
+ local elem = C((1 - sep)^0)
+ local p = Ct(elem * (sep * elem)^0) -- make a table capture
+ return match(p, s)
+end
+
+-- Modified to match left and right of one separator only.
+function gol.helpers.split_once (s, sep)
+ local utfchar = gol.helpers.utfchar
+ sep = P(sep)
+ local left = C((1 - sep)^0)
+ local right = C((utfchar)^0)
+ local p = Ct(left * sep * right)
+ return p:match(s)
+end
+
+-- Modified stripper from Roberto to support trimming other chars than whitespace
+function gol.helpers.strip(str, char)
+ local space = S(" \t\v\n")
+
+ if char then
+ char = P(char)
+ else
+ char = space
+ end
+
+ local nochar = 1 - char
+
+ local stripper = char^0 * C((char^0 * nochar^1)^0)
+
+ return match(stripper,str) or ""
+end
+
+function gol.helpers.dead_row(len)
+ local row = ""
+ local dead = "0"
+ for i=1, len, 1 do
+ row = row .. dead
+ end
+ return row
+end
+
+-- Read rules of type "B3/S23"
+-- => “birth” of a new cell if exactly 3 adjacent cells are “alive”
+-- => “staying alive” of cells with two or three adjacent “live” cells
+function gol.parse_rule (raw_rule)
+ local help = gol.helpers
+ local b_s = help.split_once (raw_rule, "/")
+ local tmp_b = help.strip(b_s[1], "B")
+ local tmp_s = help.strip(b_s[2], "S")
+
+ local b, s = {}, {}
+
+ -- single digits express birth/stay conditions
+ local n = 1
+ repeat
+ table.insert( b, tonumber(tmp_b:sub(n,n)) )
+ n = n + 1
+ until n > string.len(tmp_b)
+
+ n = 1
+ repeat
+ table.insert( s, tonumber(tmp_s:sub(n,n)) )
+ n = n + 1
+ until n > string.len(tmp_s)
+
+ return { birth = b, stay = s }
+end
+
+function gol.apply_rule (cell, cnt, rule)
+ local live, dead = "1", "0"
+ local new = dead
+ local stay = rule.stay
+ local birth = rule.birth
+
+ -- checking if cnt matches the numbers from the conditions list
+ if cell == live then
+ for _, cond in ipairs(stay) do
+ if cnt == cond then
+ new = live
+ break
+ end
+ end
+ else -- ==dead
+ for _, cond in ipairs(birth) do
+ if cnt == cond then
+ new = live
+ break
+ end
+ end
+ end
+
+ return new
+end
+
+
+function gol.parse_file (fname)
+ local tmp = {} -- return an array
+ local len -- check for equal line length
+
+ local file = assert(io.open(fname, "r"), "Not a file: " .. fname)
+ for line in file:lines() do
+ if not len then len = string.len(line) end
+
+ if len ~= string.len(line) then
+ -- inconsistent horizontal sizes; kill off program
+ return nil
+ else
+ table.insert(tmp, line)
+ end
+ end
+ file:close()
+
+ return tmp
+end
+
+--- Computing single lines and whole frames and intervals thereof
+
+function gol.next_line (rows, rule)
+ local new = ""
+ local dead = "0"
+ local live = "1"
+
+ local n = 1
+ local max = string.len(rows[2])
+
+ repeat
+ local env = {}
+
+ local lpos, rpos -- positions left of / right of current
+
+ -- toroidal, flips over at borders
+ if n == 1 then
+ lpos = max
+ else
+ lpos = n - 1
+ end
+
+ if n == max then
+ rpos = 1
+ else
+ rpos = n + 1
+ end
+
+ local current = string.sub( rows[2], n, n )
+
+ -- +---+---+---+
+ -- |nw | n | ne|
+ -- +---+---+---+
+ -- |w | c | e| env[ironment] of current
+ -- +---+---+---+
+ -- |sw | s | se|
+ -- +---+---+---+
+
+ env.nw = string.sub( rows[1], lpos, lpos )
+ env.n = string.sub( rows[1], n , n )
+ env.ne = string.sub( rows[1], rpos, rpos )
+
+ env.w = string.sub( rows[2], rpos, rpos )
+ env.e = string.sub( rows[2], lpos, lpos )
+
+ env.sw = string.sub( rows[3], lpos, lpos )
+ env.s = string.sub( rows[3], n , n )
+ env.se = string.sub( rows[3], rpos, rpos )
+
+ -- counting live cells in the environment
+ local cnt = 0
+ for _, chr in pairs(env) do
+ if chr == live then
+ cnt = cnt + 1
+ end
+ end
+
+ -- adding new cell according to ruleset
+ new = new .. gol.apply_rule(current, cnt, rule)
+
+ n = n + 1
+ until n > max
+
+ return new
+end
+
+function gol.next_frame (old, rule)
+ local new = {}
+
+ local n = 1
+
+ repeat
+ local rows = {}
+
+ rows[2] = old[n] -- current
+
+ -- toroidal
+ rows[1] = old[n-1] or old[#old] -- last
+ rows[3] = old[n+1] or old[1] -- next
+
+ -- dead borders
+ --rows[1] = old[n-1] or gol.helpers.dead_row(string.len(b)) -- last
+ --rows[3] = old[n+1] or gol.helpers.dead_row(string.len(b)) -- next
+
+ new[n] = gol.next_line( rows, rule )
+
+ n = n + 1
+ until n > #old
+
+ return new
+end
+
+-- get the nth frame starting from init
+function gol.frame (init, rule, n)
+ local frame = init
+ local gnext = gol.next_frame
+
+ for i=1, n, 1 do
+ frame = gnext( frame, rule )
+ end
+
+ return frame
+end
+
+-- get array of frames until nth [from offset]
+function gol.frames (init, rule, n, offset)
+ local frames = {}
+ local last
+ local gnext = gol.next_frame
+
+ -- “fast forward”
+ if offset then
+ last = gol.frame( init, rule, offset )
+ else
+ last = init
+ end
+
+ for i=1, n, 1 do
+ frames[i] = last
+ last = gnext( last, rule )
+ end
+
+ return frames
+end
+
+--- pretty printing frames (ascii)
+
+-- pp a heading: len should exceed length of mark + 4
+function gol.pre_section (len, mark)
+ local mark = mark or "Frame"
+ local t = "-"
+
+ local s = t..t.." "..mark.." "
+ if s:len() < len then
+ for n=1, len - s:len(), 1 do
+ s = s..t
+ end
+ end
+
+ io.write ("\n\n"..s.."\n")
+end
+
+function gol.pre_frame (frame)
+ local repl = {
+ ["0"] = "·",
+ ["1"] = "O",
+ ["2"] = "2",
+ ["3"] = "3",
+ ["4"] = "4",
+ ["5"] = "5",
+ ["6"] = "6",
+ ["7"] = "7",
+ ["8"] = "8",
+ ["9"] = "9",
+ }
+
+ for j, row in ipairs(frame) do
+ local out = row
+ for chr, subst in pairs(repl) do
+ out = out:gsub(chr, subst)
+ end
+ io.write("\n"..out)
+ end
+end
+
+function gol.pre_movie (frames, section)
+ for i, frame in ipairs(frames) do
+ if section then
+ local l = string.len(frame[1])
+ gol.pre_section( l, "Nr. " .. tostring(i) )
+ end
+ gol.pre_frame( frame )
+ end
+ io.write("\n")
+end
+
+return gol
diff --git a/run.lua b/run.lua
new file mode 100644
index 0000000..611120e
--- /dev/null
+++ b/run.lua
@@ -0,0 +1,111 @@
+--
+--------------------------------------------------------------------------------
+-- FILE: run.lua
+-- USAGE: ./run.lua
+-- DESCRIPTION: Game of Life CLI frontend
+-- OPTIONS: ---
+-- REQUIREMENTS: ---
+-- BUGS: ---
+-- NOTES: ---
+-- AUTHOR: Philipp Gesang (Phg), <megas.kapaneus@gmail.com>
+-- COMPANY:
+-- VERSION: 1.0
+-- CREATED: 05/08/10 13:09:52 CEST
+-- REVISION: ---
+--------------------------------------------------------------------------------
+--
+
+-- check for a capable interpreter
+if not (arg[-1] == "texlua" or
+ context ~= nil) then
+ print ([[
+
+···············································································
+Please use the LuaTeX interpreter or modify the sources to fit your
+Lua machine of choice!
+GOTO http://www.luatex.org/
+···············································································
+]])
+ return 1
+end
+
+require "life"
+
+local help = gol.helpers
+
+life = {}
+life.debug = 1
+
+function life.get_args ()
+ gol.arg = arg
+ if gol.arg[-1] == "texlua" then
+ gol.machine = gol.arg[-1]
+ gol.self_name = gol.arg[0]
+ gol.arg[-1], gol.arg[0] = nil, nil
+ elseif context ~= nil then
+ -- TODO
+ end
+
+ local kv_args = function ()
+ local tmp = {}
+ local so = help.split_once
+ for _, a in ipairs(gol.arg) do
+ local lr = so(a, "=")
+ tmp[help.strip(lr[1], "-")] = lr[2]
+ end
+ return tmp
+ end
+
+ return kv_args()
+end
+
+function main ()
+ local current = {}
+ current.kv_args = life.get_args()
+ current.file = current.kv_args.file or "10x10_glider.gol"
+
+ -- check for debug flag
+ if tonumber(current.kv_args.debug) == 0 then
+ life.debug = false
+ else
+ life.debug = current.kv_args.debug or life.debug
+ end
+
+
+ -- prepare the rule
+ if current.kv_args.rule then
+ current.rule = gol.parse_rule (current.kv_args.rule)
+ else
+ current.rule = gol.parse_rule ("B3/S23") -- Conway's rule
+ end
+
+ if life.debug then for n, a in pairs(current.kv_args) do print(n, a) end end
+ if life.debug then for i, j in pairs(current.rule) do print(i, #j) end end
+
+ -- read the initial state (get an array of strings)
+ if current.file then
+ current.init = gol.parse_file (current.file)
+ else
+ return 1
+ end
+
+ if current.init then
+ if life.debug then
+ gol.pre_frame(current.init)
+ end
+ local lots = gol.frames( current.init, current.rule, 55 )
+ gol.pre_movie (lots, true)
+ else
+ io.write"\nCheck your input file for consistency, please.\n"
+ return 1
+ end
+
+ -- sustaining dead cells
+ current.sustain = current.kv_args.sustain or 0
+ current.fadeout = current.kv_args.fadeout or 0 -- TODO
+
+ return 0
+end
+
+return main()
+