This is an old topic, but here's some simple Python code which implements Paul Callahan's neat idea. This code prints generation 30 of the Gosper glider gun to the console.
It's not very fast (~100 gens/second on breeder.lif on my laptop), and it uses dictionaries (hash tables) rather than walking a list with a set of pointers which would be much more efficient in (e.g.) a C implementation.
The life code is just create_life_table() and Board.generation(); the rest of the code just packs and unpacks from various formats.
Code: Select all
def create_life_table():
"""Generate the lookup table for the cells."""
successors = {}
def life(*args):
n = sum(args[1:])
n |= args[0] # if we or with the cell value, we can just test == 3
if n==3:
return 1
else:
return 0
# generate all 16 bit strings
for iv in range(65536):
bv = [(iv>>j)&1 for j in range(16)]
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p = bv
# compute next state of the inner 2x2
nw = life(f, a, b, c, e, g, i, j, k)
ne = life(g, b, c, d, f, h, j, k, l)
sw = life(j, e, f, g, i, k, m, n, o)
se = life(k, f, g, h, j, l, n, o, p)
# compute the index of this 4x4
nw_code = a | (b<<1) | (e<<2) | (f<<3)
ne_code = c | (d<<1) | (g<<2) | (h<<3)
sw_code = i | (j<<1) | (m<<2) | (n<<3)
se_code = k | (l<<1) | (o<<2) | (p<<3)
# compute the state for the 2x2
next_code = nw | (ne<<1) | (sw<<2) | (se<<3)
# get the 4x4 index, and write intp the table
this_code = nw_code | (ne_code<<4) | (sw_code<<8) | (se_code<<12)
successors[this_code] = next_code
return successors
class Board:
def __init__(self):
"""Create a new, empty simulation."""
self.clear()
def clear(self):
"""Clear the state of the simulation."""
self.cells = {}
self.life_table = create_life_table()
self.offset = 0
def get_all(self):
"""Return a list of all the ON cells inside the rectangle (x1,y1), (x2,y2)"""
o = -self.offset
# points are stored as a 4 bit number, in the order:
# (MSB) se sw ne nw (LSB)
pts = [((x<<1)+o,(y<<1)+o) for x,y in self.cells if self.cells[(x,y)]&1]
pts += [((x<<1)+1+o,(y<<1)+o) for x,y in self.cells if self.cells[(x,y)]&2]
pts += [((x<<1)+o,(y<<1)+1+o) for x,y in self.cells if self.cells[(x,y)]&4]
pts += [((x<<1)+1+o,(y<<1)+1+o) for x,y in self.cells if self.cells[(x,y)]&8]
return pts
def set(self, x, y, value):
"""Set the cell at (x,y) to value (either 0 or 1)"""
# get 2x2 co-ordinate
xc = x>>1
yc = y>>1
c = self.cells.get((xc,yc),0)
# flip the appropriate bit
mask = 1 << ((y&1)<<1)
mask <<= x & 1
if value:
c = c | mask
else:
c = c & ~mask
self.cells[(xc,yc)] = c
def set_all(self, pts):
"""Set a list of points."""
for cell in pts:
self.set(cell[0], cell[1], 1)
def step(self, n):
"""Run n generations."""
for i in range(n):
self.generation()
def generation(self):
"""Advance by one generation."""
new_cells = {}
# compute cell co-ordinates of each live 2x2 block, and its NW, N and W neighbour
cells = set(self.cells.keys())
cells.update([(x-1,y) for x,y in cells])
cells.update([(x,y-1) for x,y in cells])
# for each of these x,y co-ordinates
for x,y in cells:
# get the neighbours
nw = self.cells.get((x, y), 0)
ne = self.cells.get((x+1, y), 0) << 4
sw = self.cells.get((x, y+1), 0) << 8
se = self.cells.get((x+1, y+1), 0) << 12
# lookup up the 2x2 successor of this 4x4 block
code = nw | ne | sw | se
result = self.life_table[code]
if result:
new_cells[(x,y)] = result
# shift the offset, flip the buffer
self.offset += 2
self.cells = new_cells
## utilities: convert from RLE / to ASCII
def to_str(pts):
"""Convert to ASCII"""
if not pts:
return ""
pts = sorted(pts, key=lambda x:(x[1],x[0]))
xs = [p[0] for p in pts]
min_x, max_x, min_y, max_y = min(xs), max(xs), pts[0][1], pts[-1][1]
rle = []
x,y = min_x, min_y
for xn,yn in pts:
while yn!=y:
y, rle, x = y+1, rle+['\n'], min_x
while xn!=x:
rle, x = rle+[' '],x+1
rle, x = rle+['*'], x+1
return "".join(rle)
def from_rle(rle):
"""Parse an RLE string"""
pts = []
x,y = 0,0
rc, count = 1, 0
lines = rle.split("\n")
for line in lines:
line = line.strip().rstrip().lower()
if line and line[0] in 'bo$0123456789':
for char in line:
if char=='o':
pts += [(x+i,y) for i in range(rc)]
if char in 'bo':
x += rc
if char=='$':
y += rc
x = 0
if char.isdigit():
count = count*10 + int(char)
rc = count
else:
count, rc = 0, 1
return pts
if __name__=="__main__":
b = Board()
b.set_all(from_rle("""x = 36, y = 9, rule = B3/S23
27bo$26b4o$9boo14boobobo$bo7bobbo11b3obobbobboo$o3boo7bo11boobobo3boo$
o5bo6bo12b4o$b5o7bo7bo5bo$9bobbo9bo$9boo9b3o!"""))
b.step(30)
print to_str(b.get_all())