"""\
Conway's  Game of Life
======================


The Game
--------

(This description is adapted from Daniel C. Dennett: Darwin's Dangerous 
Idea.  The game of Life was invented by the mathematician John Horton 
Conway, and first popularized by Martin Gardner in his "Mathematical Games" 
columns in the Scientific American of October 1970 and February 1971.)

Life is played on a two-dimensional grid, such as a checkerboard,
using simple counters, such as pebbles or pennies--or one could go
high-tech and play it on a computer screen.  It is not a game one plays
to win; if it is a game at all, it is solitaire.  The grid divides space
into square cells, and each cell is either ON or OFF at each moment.
Notice that each cell has eight neighbours:

  +---+---+---+---+---+
  |   |   |   |   |   |
  +---+---+---+---+---+
  |   | NW| N | NE|   |
  +---+---+---+---+---+
  |   | W | * | E |   |
  +---+---+---+---+---+
  |   | SW| S | SE|   |
  +---+---+---+---+---+
  |   |   |   |   |   |
  +---+---+---+---+---+

Time in the life world is discrete, not continuous; it advances in ticks, 
and the state of the world changes between each two ticks according to the 
following rule.

	_Life Physics_: For each cell in the grid, count how many of its eight 
	neighbors are ON at the present instant.  If the answer is exactly two, 
	the cell stays in its present state (ON or OFF) in the next instant.
	If the answer is exactly three, the cell in ON in the next instant.  
	Under all other conditions, the cell is OFF.


The Implementation
------------------

We represent the grid as a list of rows.  Each row is a Python long 
integer, where the bits of its binary representation gives the sucessive 
values of the cells (bit zero corresponds to the leftmost bit, and so on).

The grid is a finite rectangle, and the cells at the borders always remain 
OFF.  (It would not be too hard to implement an automatic resizing board of 
potentially infinite dimensions--this is left as an exercise.)

We use a trick to compute the new iterations a whole row at a time: the 
logic of addition through hardware gates is simulated using shifting and 
masking operations that compute a separate result for each bit position.  
(I invented this approach around 1977 when I first wrote a program for 
Life, in Pascal on a CDC Cyber.)

The rest of the program is a relatively straightforward class that stores 
the grid as a list of rows and has methods for setting and clearing 
individual cells, printing the grid, and calculating the next iteration.
The calculation checks for stable patterns ("still life") but not for 
periodic patterns -- this is left as an exercise for the reader.


The Code
--------

Add(Accumulator, Bit) -> Accumulator
TestAdd()
SlowNext(RowAbove, ThisRow, RowBelow) -> NewThisRow
FastNext(RowAbove, ThisRow, RowBelow) -> NewThisRow
Game(width, height) -> Game instance
	game.reset()
	game.close()
	game.set(row, col)
	game.clear(row, col)
	game.prettyprint()
	game.move()
	game.resize(width, height)
	game.shift(dx, dy)
	game.iteration: int
	game.stable: flag


Pointers
--------

Starting with an InfoSeek search, I found the following web pages of use:

http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/alife/systems/life/0.html
http://www.saintjoe.edu:9001/life.html
http://www.research.digital.com/nsl/projects/life/life.html
http://www.fusebox.com/cb/life/life.html
http://www.mbnet.mb.ca/~catseye/life/

"""


def Add((A0, A1, A2, A3), X):
	"""Add a single bit to a 4-bit accumulator.
	
	Given a 4-bit accumulator (A0, A1, A2, A3) and a single bit X, calculate 
	the new value of the accumulator after adding the bit.  For instance, if 
	the accumulator is (1, 1, 0, 0) (i.e., the value 3) and the bit is 1, the 
	new value of the accumulator will be (0, 0, 1, 0) (i.e., the value 4).  
	Overflow is ignored (i.e., 15 + 1 equals 0).
	
	This is interesting because in fact A0-A3 and X represent an array of 
	accumulators and bits that are all operated on in parallel: each bit 
	position of the binary representation of the integers is acted on 
	independently.
	
	"""
	A0, X = A0^X, A0&X
	A1, X = A1^X, A1&X
	A2, X = A2^X, A2&X
	A3, X = A3^X, A3&X
	return (A0, A1, A2, A3)	


def TestAdd():
	"""Test routine for Add().
	
	For each number < 15 we construct an accumulator (1 bit wide)
	and check that adding 0 and 1 to it have the desired effect.
	
	"""
	for a in range(15):
		print "a =", a
		A0 = a&1
		A1 = (a>>1)&1
		A2 = (a>>2)&1
		A3 = (a>>3)&1
		A = (A0, A1, A2, A3)
		AA = Add(A, 0)
		if AA != A: print "Add(%s, 0) -> %s" % (A, AA)
		AA = Add(A, 1)
		aa = a+1
		AA0 = aa&1
		AA1 = (aa>>1)&1
		AA2 = (aa>>2)&1
		AA3 = (aa>>3)&1
		if AA != (AA0, AA1, AA2, AA3):
			print "Add(%s, 1) -> %s" % (A, AA)


def SlowNext(N, C, S):
	"""Calculate the next iteration for a whole row.
	
	Inputs are the row above (N), the target row (C) and the row below (S).
	
	We calculate shifted versions of the three input rows so we have bits 
	corresponding to all eight neigboring cells in the same bit position as the 
	center cell.  We then count the number of neighbors by adding each 
	neighboring bit to a 4-bit accumulator, using the Add() subroutine defined 
	above.
	
	Finally, we compute the logical expression representing the next cell 
	value: ON if the neighbor count is 3, or if it is 2 and the original 
	cell was ON.
	
	The FastNext() function (below) calculates the same result, but faster.
	
	"""
	NW, W, SW = N<<1, C<<1, S<<1
	NE, E, SE = N>>1, C>>1, S>>1
	
	A = (0, 0, 0, 0)
	
	A = Add(A, NW)
	A = Add(A, N)
	A = Add(A, NE)
	A = Add(A, W)
	A = Add(A, E)
	A = Add(A, SW)
	A = Add(A, S)
	A = Add(A, SE)
	
	(A0, A1, A2, A3) = A
	
	return (A0|C) & A1 & ~(A2|A3)


def FastNext(N, C, S):
	"""Faster version of the Next() function.

	This optimizes the counting-neighbors stage by in-lining the Add() 
	function and by recognizing that in the first few steps the higher bits 
	of the accumulator are guaranteed to be zero.  The basic step is:
	
		X = <the next bit>
		A0, X = A0^X, A0&X
		A1, X = A1^X, A1&X
		A2, X = A2^X, A2&X
		A3, X = A3^X, A3&X
	
	This is further optimized by noticing which bits can be turned on
	in which stages.
	
	Note that the Game.move() method applies another optimization: it only 
	calls Next() when at least one of the rows is non-zero.
	
	"""
	NW, W, SW = N<<1, C<<1, S<<1
	NE, E, SE = N>>1, C>>1, S>>1
	
	A0, A1 = NW^N, NW&N
	A0, A1 = A0^NE, A1|A0&NE
	A0, X = A0^W, A0&W; A1, A2 = A1^X, A1&X
	A0, X = A0^E, A0&E; A1, X = A1^X, A1&X; A2 = A2|X
	A0, X = A0^SW, A0&SW; A1, X = A1^X, A1&X; A2 = A2^X
	A0, X = A0^S, A0&S; A1, X = A1^X, A1&X; A2 = A2^X
	A0, X = A0^SE, A0&SE; A1, X = A1^X, A1&X; A2, A3 = A2^X, A2&X
	
	return (A0|C) & A1 & ~(A2|A3)


# Choose which Next function is used.  By default, we use FastNext.
Next = FastNext


class Game:
	
	def __init__(self, width=20, height=20):
		self.setup(width, height)
		self.reset()
	
	def setup(self, width, height):
		self.width = width
		self.height = height
		if self.width <= 30:
			self.one = 1	# Use fixed-width (32-bit) arithmetic
		else:
			self.one = 1L	# Use long integer arithmetic
		self.mask = (self.one<<(self.width-1)) - 2
		self.moverange = range(1, self.height-1)
	
	def reset(self):
		self.grid = [0]*self.height
		self.iteration = 0
		self.stable = 0
	
	def __del__(self):
		self.close()
	
	def close(self):
		pass
	
	# Basic access: get, set, clear a cell.
	# Beware: these use (row, col) instead of (x, y)
	
	def get(self, row, col):
		return (self.grid[row]>>col) & 1
	
	def set(self, row, col):
		self.grid[row] = self.grid[row] | (self.one<<col)
	
	def clear(self, row, col):
		self.grid[row] = self.grid[row] & ~(self.one<<col)
	
	# Output (mostly useful for debugging)
	
	def prettyprint(self):
		for row in range(self.height):
			print "%3d [" % row,
			x = self.grid[row]
			for col in range(self.width):
				print (x&1) and "#" or ".",
				x = x>>1
			print "]"
		print "Iteration:", self.iteration, self.stable and "(STABLE)" or ""
	
	# Basic operation
	
	def move(self):
		oldgrid = self.grid[:]
		self.grid[0] = self.grid[-1] = 0
		for row in self.moverange:
			[N, C, S] = oldgrid[row-1:row+2]
			if N or C or S:
				NW, W, SW = N<<1, C<<1, S<<1
				NE, E, SE = N>>1, C>>1, S>>1
				
				A0, A1 = NW^N, NW&N
				A0, A1 = A0^NE, A1|A0&NE
				A0, X = A0^W, A0&W; A1, A2 = A1^X, A1&X
				A0, X = A0^E, A0&E; A1, X = A1^X, A1&X; A2 = A2|X
				A0, X = A0^SW, A0&SW; A1, X = A1^X, A1&X; A2 = A2^X
				A0, X = A0^S, A0&S; A1, X = A1^X, A1&X; A2 = A2^X
				A0, X = A0^SE, A0&SE; A1, X = A1^X, A1&X; A2, A3 = A2^X, A2&X
				
				self.grid[row] = ((A0|C) & A1 & ~(A2|A3)) & self.mask

##				new = Next(N, C, S) & self.mask
##				self.grid[row] = new
		self.iteration = self.iteration + 1
		self.stable = self.grid == oldgrid
	
	# Global grid change operations
	
	def shift(self, dx, dy):
		oldgrid = self.grid
		newgrid = [0]*self.height
		for row in range(self.height):
			data = oldgrid[row]
			row = row+dy
			if 0 <= row < self.height:
				if dx > 0: data = (data<<dx) & self.mask
				elif dx < 0: data = (data>>-dx) & self.mask
				newgrid[row] = data
		self.grid = newgrid
	
	def resize(self, width, height):
		self.setup(width, height)
		if type(self.one) is not type(1L):
			cast = int
		else:
			cast = long
		newgrid = self.grid[:height]
		if len(newgrid) < height:
			newgrid[height:] = [0]*(height - len(newgrid))
		self.grid = map(lambda data, mask=self.mask, cast=cast:
		                       cast(data&mask),
		                newgrid)
	
	def extent(self):
		top = 0
		bottom = self.height
		while top < bottom and self.grid[top] == 0:
			top = top + 1
		while top < bottom and self.grid[bottom-1] == 0:
			bottom = bottom - 1
		bits = 0
		for data in self.grid[top:bottom]:
			bits = bits | data
		left = 0
		right = self.width
		while left < right and bits&(self.one<<left) == 0:
			left = left + 1
		while left < right and bits&(self.one<<(right-1)) == 0:
			right = right - 1
		return left, top, right, bottom
	
	def recenter(self):
		left, top, right, bottom = self.extent()
		dx = (self.width - right - left) / 2
		dy = (self.height - bottom - top) / 2
		if dx or dy:
			self.shift(dx, dy)

	def load_from_file(self, file):
		options = eval(file.readline())
		grid = eval(file.read())
		width, height = options['width'], options['height']
		self.resize(width, height)
		self.grid = grid
		self.iteration = options['iteration']
		self.stable = options['stable']

	def save_to_file(self, file):
		options = {
			'width': self.width,
			'height': self.height,
			'iteration': self.iteration,
			'stable': self.stable,
			}
		file.write("%s\n" % repr(options))
		file.write("[\n")
		for data in self.grid:
			file.write(" %s,\n" % hex(data))
		file.write("]\n")
	
	# Create some common patterns
	
	def glider(self, row, col):
		self.set(row-1, col+1)
		self.set(row  , col+1)
		self.set(row+1, col+1)
		self.set(row+1, col)
		self.set(row  , col-1)
	
	def flasher(self, row, col):
		self.set(row, col-1)
		self.set(row, col)
		self.set(row, col+1)

	def letter_r(self, row, col):
		self.set(row-1, col)
		self.set(row-1, col+1)
		self.set(row  , col-1)
		self.set(row  , col)
		self.set(row+1, col)


def main():
	g = Game()
	g.glider(3, 3)
	g.flasher(3, 10)
	while 1:
		g.move()
		g.prettyprint()
		if g.stable:
			raw_input("STABLE POSITION REACHED -- STOP: ")
			break
		raw_input("Next: ")


if __name__ == '__main__':
	main()