#!/usr/bin/python
import sys, os, math#, pygame
#from pygame.locals import *

running = True
fps = 20

class GeneType:
  BLD = 1
  TRM = 2
  SPR = 3
  VAL = [BLD, TRM, SPR]

  def isValid(self, typ):
    for t in self.VAL:
      if (t == typ):
    return True
    return False

class GenePool(object):
  def __init__(self):
    self.nuid = 0
    self.genes = []
    self.mutations = {}
    self.terminal = self.addGene(GeneType.TRM, {})
    self.base = self.addGene(GeneType.BLD, {})

  def addGene(self, typ, neigh):
    i = self.nuid
    self.nuid += 1
    self.genes.append(Gene(typ, i, neigh, self))
    self.mutations[i] = {}
    for g in self.mutations.keys():
      self.mutations[g][i] = 1
      self.mutations[i][g] = 1
    return i

  def isGeneValid(self, gene):
    for g in self.genes:
      if g.uid == gene.uid:
    return True
    return False

  def validateNeigh(self, neigh):
    n = {}
    for d in Dir.VAL:
      n[d] = self.terminal
    for (k, v) in neigh.items():
      if not k in n:
    print 'Neighbour has invalid direction: ' + str(k) +'; ignoring'
      else:
    n[k] = v
    return n

class Dir:
  UP = 1
  RI = 2
  DO = 3
  LE = 4
  VAL = [UP, RI, DO, LE]

  def isValid(self, di):
    for d in self.VAL:
      if d == di:
    return True
    return False

  def applyDir(self, d, p):
    if d == self.UP:
      return (p[0], p[1] - 1)
    if d == self.RI:
      return (p[0] + 1, p[1])
    if d == self.DO:
      return (p[0], p[1] + 1)
    if d == self.LE:
      return (p[0] - 1, p[1])

class Gene(object):
  def __init__(self, typ, uid, neigh, pool):
    if GeneType().isValid(typ):
      self.typ = typ
    else:
      print 'Invalid gene type:', typ, '; Setting to terminal'
      self.typ = GeneType.TRM
    self.uid = uid
    if self.typ == GeneType.TRM:
      self.nbr = {}
    else:
      self.nbr = pool.validateNeigh(neigh)

class Creature(object):
  def __init__(self, origin = (0, 0), gp = None):
    if gp == None:
      self.genepool = GenePool()
    else:
      self.genepool = gp
    self.body = {}
    self.pos = origin

  def build(self):
    queue = []
    queue.append((self.genepool.genes[self.genepool.base], self.pos))   # Gotta start somewhere
    while len(queue) > 0:   # While there's still building to do
      g = queue.pop(0)   # Get the oldest gene
      if not g[0].typ == GeneType.TRM:   # If it isn't a terminal type
    if not g[1][1] in self.body:   # If it's on a new row
      self.body[g[1][1]] = {}   # Add new dict for the row
    if not g[1][0] in self.body[g[1][1]]:   # If the row and column are unique, ie the position hasn't been assigned to another gene already
      self.body[g[1][1]][g[1][0]] = g[0]   # Set the row, column to this gene
      for (d, n) in g[0].nbr.items():   # Go through all of this gene's neighbours
        queue.append((self.genepool.genes[n], Dir().applyDir(d, g[1])))   # And add them with the appropriate adjustment to the position

  def buildLimit(self, lim):
    queue = []
    queue.append((self.genepool.genes[self.genepool.base], self.pos))   # Gotta start somewhere
    while (len(queue) > 0) and (lim > 0):   # While there's still building to do and we haven't reached the limit
      g = queue.pop(0)   # Get the oldest gene
      if not g[0].typ == GeneType.TRM:   # If it isn't a terminal type
    if not g[1][1] in self.body:   # If it's on a new row
      self.body[g[1][1]] = {}   # Add new dict for the row
    if not g[1][0] in self.body[g[1][1]]:   # If the row and column are unique, ie the position hasn't been assigned to another gene already
      self.body[g[1][1]][g[1][0]] = g[0]   # Set the row, column to this gene
      lim -= 1   # Lower the limit since we've expanded
      for (d, n) in g[0].nbr.items():   # Go through all of this gene's neighbours
        queue.append((self.genepool.genes[n], Dir().applyDir(d, g[1])))   # And add them with the appropriate adjustment to the position


  def printBody(self):
    x1, y1, x2, y2 = 0, 0, 0, 0
    for y in self.body.keys():
      if y < y1:
    y1 = y
      elif y > y2:
    y2 = y
      for x in self.body[y].keys():
    if x < x1:
      x1 = x
    elif x > x2:
      x2 = x

    x2 -= x1 - 1
    y2 -= y1 - 1

    p = []
    for y in xrange(y2):
      p.append([])
      for x in xrange(x2):
    p[y].append(' ')

    for y in self.body.keys():
      for x in self.body[y].keys():
    p[y - y1][x - x1] = 'X'

    for l in p:
      print ''.join(l)

"""
pygame.init()
size = (640, 480)
screen = pygame.display.set_mode(size)
pygame.display.set_caption('Patterning')
pygame.mouse.set_visible(0)
clock = pygame.time.Clock()
"""

print 'Starting'

while running:
  running = False

p = GenePool()
u = p.addGene(GeneType.BLD, {})
l = p.addGene(GeneType.BLD, {})
m = p.addGene(GeneType.BLD, {})
n = p.addGene(GeneType.BLD, {})
b = p.addGene(GeneType.BLD, {})

p.genes[p.base].nbr[Dir.DO] = b
p.genes[u].nbr[Dir.DO] = n
p.genes[n].nbr[Dir.DO] = b
p.genes[b].nbr[Dir.RI] = l
p.genes[b].nbr[Dir.LE] = l
p.genes[l].nbr[Dir.RI] = u
p.genes[l].nbr[Dir.LE] = u

c = Creature((0, 0), p)
c.buildLimit(188)
c.printBody()
print 'Terminating'