class Grid(object):

 	def __init__(self):

 		self.cells = {}

 		self.minx = 0

 		self.maxx = 0

 		self.miny = 0

 		self.maxy = 0

 	def set(self, pos, value=1):

 		if not pos in self.cells or value != self.cells[pos]:

 			self.cells[pos] = value

 			self.update(pos)

 		return self

 	def clear(self, pos):

 		if pos in self.cells:

 			del self.cells[pos]

 			self.update(pos)

 		return self

 	def update(self, (x, y)):

 		self.minx = min(x, self.minx)

 		self.maxx = max(x, self.maxx)

 		self.miny = min(y, self.miny)

 		self.maxy = max(y, self.maxy)

 		return self

 	def width(self):

 		return self.maxx - self.minx + 1

 	def height(self):

 		return self.maxy - self.miny + 1

 	def __len__(self):

 		return len(self.cells)

 	def __str__(self):

 		pass

 import copy

 class Rule(object):

 	def iterate(self, oldgrid):

 		grid = copy.deepcopy(oldgrid)

 		for x in xrange(oldgrid.minx - 1, oldgrid.maxx + 2):

 			for y in xrange(oldgrid.miny - 1, oldgrid.maxy + 2):

 				#print x, y, self.neighbours(oldgrid, x, y)

 				n = self.neighbours(oldgrid, (x, y))

 				if n > 2:

 					grid.set((x, y))					

 		return grid

 	def neighbours(self, grid, (testx, testy)):

 		n = 0

 		#print "testing ", testx, testy

 		for x in range(testx - 1, testx + 2):

 			for y in range(testy - 1, testy + 2):

 				if (x, y) in grid.cells:

 					n += 1

 				#print x, y, n

 		return n 

 class Rule2(object):

 	def iterate(self, oldgrid):

 		grid = copy.deepcopy(oldgrid)

 		for x in xrange(oldgrid.minx - 1, oldgrid.maxx + 2):

 			for y in xrange(oldgrid.miny, oldgrid.maxy + 2):

 				#print "testing ", x, y,

 				if (x+1, y) in oldgrid.cells or (x, y-1) in oldgrid.cells:

 					grid.set((x, y), 1)								

 		return grid

 import random

 import marshal

 class PotentialGrowth(object):

 	def __init__(self):

 		random.seed()

 	def iterate(self, oldgrid):

 		grid = copy.deepcopy(oldgrid)

 		for cell in oldgrid.cells.iteritems():

 			pos = cell[0]

 			value = cell[1]

 			if value > 1:

 				new_pos, new_value = self.grow(grid, pos)

 				grid.set(new_pos, new_value)

 				grid.set(pos, value - 1)

 		return grid

 	def grow(self, grid, (x, y)):

 		neighbours = [(x-1, y), (x, y+1), (x+1, y), (x, y-1)]

 		neighbours = [n for n in neighbours if n not in grid.cells]

 		try:

 			pos = random.choice(neighbours)	

 			value = 4

 		except IndexError:

 			pos = (x, y)

 			value = grid.cells[pos]

 		return pos, value

 import sys

 import math

 def ruleTest():

 	rule = Rule()

 	grid = Grid()

 	grid.set((0, 0))

 	grid.set((0, 1)).set((1, 0)).set((0, -1)).set((-1, 0))

 	print "iteration radius(diff) area(diff) pi"

 	iterations = int(sys.argv[1])

 	for i in range(iterations):

 		A = len(grid)

 		r = grid.width() / 2.0

 		r_ideal = math.sqrt(A / math.pi)

 		A_ideal = r**2 * math.pi

 		pi = A / r**2

 		print "%i %f(%f) %i(%i) %f" % (i, r, r - r_ideal, 

 										A, A - A_ideal, pi)

 		grid = rule.iterate(grid)

 		dumpGrid(grid, "grid.cfg")

 		#print

 def rule2Test():

 	rule = Rule2()

 	grid = Grid()

 	grid.set((0, 0)).set((-1, 0)).set((0, 1))

 	olda = 1

 	iterations = int(sys.argv[1])

 	for i in range(iterations):

 		a =  (float(len(grid)) - grid.width()) * 4.0

 		pi = 1.0 / ((grid.width()-1)**2 / ((a + olda) / 2.0))

 		print i, grid.width(), len(grid), pi

 		grid = rule.iterate(grid)

 		olda = a

 		dumpGrid(grid, "grid.cfg")

 def potentialTest():

 	rule = PotentialGrowth()

 	grid = Grid()

 	grid.set((0, 0), 4)

 	iterations = int(sys.argv[1])

 	for i in range(iterations):

 		A = len(grid)

 		r = grid.width() / 4.0 + grid.height() / 4.0

 		r_ideal = math.sqrt(A / math.pi)

 		A_ideal = r**2 * math.pi

 		pi = A / r**2

 		print "%i %f(%f) %i(%i) %f" % (i, r, r - r_ideal, 

 										A, A - A_ideal, pi)

 		grid = rule.iterate(grid)

 		dumpGrid(grid, "grid.cfg")

 def main():

 	ruleTest()

 	#rule2Test()

 	#potentialTest()

 if __name__ == "__main__":

 	main()