/
rules.coffee
148 lines (126 loc) · 6 KB
/
rules.coffee
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
# This module is part of [recursiveuniver.se](http://recursiveuniver.se).
#
# ## Rules Module
#
# The Rules Module provides a method for setting up the [rules][ll] of the Life universe.
#
# [ll]: http://www.conwaylife.com/wiki/Cellular_automaton#Well-known_Life-like_cellular_automata
# ### Setting the rules for this game's "Universe"
#
# There many, many are different possible "games" consisting of cellular automata arranged in a two-dimensional
# matrix. Cafe au Life handles the "life-like" ones, roughly those that have:
#
# * A stable 'quiescent' state. A universe full of empty cells will stay empty.
# * Rules based only on the population of a cell's Moore Neighborhood: Every cell is affected by the population of its eight neighbours, and all eight neighbours are treated identically.
# * Two states.
#
# Given a definition of the state machine for each cell, Cafe au Life performs all the necessary initialization to compute
# the future of a pattern.
# `set_universe_rules` generates the size four "seed" squares that actually calculate their results
# from the life-like game rules. All larger squares decompose recursively into size four squares, and thus
# do not need to know anything about the rules.
#
# The default, `set_universe_rules()`, is equivalent to `set_universe_rules([2,3],[3])`, which
# invokes Conway's Game of Life, commonly written as 23/3. Other games can be invoked with their survival
# and birth counts, e.g. `set_universe_rules([1,3,5,7], [1,3,5,7])` invokes
# [Replicator](http://www.conwaylife.com/wiki/Replicator_(CA))
# ### Baseline Setup
_ = require('underscore')
YouAreDaChef = require('YouAreDaChef').YouAreDaChef
exports ?= window or this
# A handy function for generating quadrants that are the cartesian products of a collection
# multiplied by itself once for each quadrant, and another function for turning any array or object into a dictionary function.
#
# (see also: [Reusable Abstractions in CoffeeScript][reuse])
#
# [reuse]: https://github.com/raganwald/homoiconic/blob/master/2012/01/reuseable-abstractions.md#readme
cartesian_product = (collection) ->
_.reduce(
_.reduce(
_.reduce( {nw, ne, se, sw} for nw in collection for ne in collection for se in collection for sw in collection
, (x, y) -> x.concat(y))
, (x, y) -> x.concat(y))
, (x, y) -> x.concat(y))
dfunc = (dictionary) ->
(indices...) ->
indices.reduce (a, i) ->
a[i]
, dictionary
exports.mixInto = (exports) ->
{Square, Cell} = exports
# A Seed knows how to calculate its own result from
# the rules
class Square.Seed extends Square
constructor: (params) ->
super(params)
@result = _.memoize( =>
a = @to_json()
Square.cache.find
nw: Square.Seed.succ(a, 1,1)
ne: Square.Seed.succ(a, 1,2)
se: Square.Seed.succ(a, 2,2)
sw: Square.Seed.succ(a, 2,1)
)
class Square.Smallest extends Square
_.defaults exports,
set_universe_rules: (survival = [2,3], birth = [3]) ->
Cell.Alive ?= new Cell(1)
Cell.Dead ?= new Cell(0)
return exports if Square.cache.current_rules?.toString() is {survival, birth}.toString() and Square.cache.length >= 65552
rule = dfunc [
(if birth.indexOf(x) >= 0 then Cell.Alive else Cell.Dead) for x in [0..9]
(if survival.indexOf(x) >= 0 then Cell.Alive else Cell.Dead) for x in [0..9]
]
Square.Seed.succ = (cells, row, col) ->
current_state = cells[row][col]
neighbour_count = cells[row-1][col-1] + cells[row-1][col] +
cells[row-1][col+1] + cells[row][col-1] +
cells[row][col+1] + cells[row+1][col-1] +
cells[row+1][col] + cells[row+1][col+1]
rule(current_state, neighbour_count)
Square.cache.clear()
# The canonical 2x2 squares are initialized from the cartesian product
# of every possible cell. 2 possible cells to the power of 4 quadrants gives sixteen
# possible 2x2 squares.
#
# 2x2 squares do not compute results
all_2x2_squares = cartesian_product([Cell.Dead, Cell.Alive]).map (quadrants) ->
Square.cache.add new Square.Smallest(quadrants)
# The canonical 4x4 squares are initialized from the cartesian product of
# every possible 2x2 square. 16 possible 2x2 squares to the power of 4 quadrants
# gives 65,536 possible 4x4 squares.
#
# 4x4 squares know how to compute their 2x2 results, and as we saw above, they
# memoize those results so that they are only computed once. (A variation of
# memoizing the result computation is to compute it when generating the 4x4 square,
# thus "compiling" the supplied rules into a table of 65,536 rules taht is looked
# up at runtime.)
#
# We will see below that all larger squares compute their results by recursively
# combining the results of smaller squares, so therefore all such computations
# will terminate when they reach a square of size 4x4.
cartesian_product(all_2x2_squares).forEach (quadrants) ->
Square.cache.add new Square.Seed(quadrants)
Square.cache.current_rules = {survival, birth}
exports
# ## The first time through
#
# If this is your first time through the code, read the [Future Module][future] next. You can look at the [Cache][cache], [Garbage Collection][gc], and [API][api] modules at your leisure, they arent really core to the algorithm.
#
# [menagerie]: http:menagerie.html
# [api]: http:api.html
# [future]: http:future.html
# [cache]: http:cache.html
# [canonical]: https://en.wikipedia.org/wiki/Canonicalization
# [rules]: http:rules.html
# [gc]: http:gc.html
# ---
#
# **(c) 2012 [Reg Braithwaite](http://braythwayt.com)** ([@raganwald](http://twitter.com/raganwald))
#
# Cafe au Life is freely distributable under the terms of the [MIT license](http://en.wikipedia.org/wiki/MIT_License).
#
# The annotated source code was generated directly from the [original source][source] using [Docco][docco].
#
# [source]: https://github.com/raganwald/cafeaulife/blob/master/lib
# [docco]: http://jashkenas.github.com/docco/