Juego de la Vida.

Descripción.

Esta entrada se enfoca principalmente en implementar el Juego de la Vida de Jonh Conway, sin dejar a un lado la descripción del problema que en un principio se plantearon.

El Juego de la Vida es un autómata celular algorítmicamente computable, algo que interesa de este juego es que a partir de reglas muy sencillas se puedan obtener patrones interesantes. Consta de una matriz bidimensional la cual se colocan al principio un patrón de células "vivas" o "muertas" (sólo tienes esos dos estados). Su vecindario son ocho células más que pueden estar vivas o muertas.

Estas reglas son:

Para cada célula que está "viva":

     Cada celula con uno o ningún vecino "muere" de soledad.

     Cada célula con cuatro o más vecinos "muere" de sobre población. 

     Cada célula con dos o tres vecinos sobrevive.

Para cada célula que está "muerta":

     Cada célula con exactamente tres vecinos "vive"

Estas reglas son de, Nacimiento, Muerte o Supervivencia.

Implementación en Python.

A continuación se mestra la implementación en python comentando y resaltando las partes importantes como la validación de las celdas, los bordes, cuantos vecinos, entre otras cosas.

Primeramente se importaron estas librerías necesarias para poder trabajar.

# -*- coding: utf-8 -*-

from sys import argv #Para argumentos por consola
from os import system #Para hacer un clear en la pantalla
import time #Para el intervalo después del clear de la pantalla
import random #para llenar los celdas de manera pseudoaletoria

Después con la ayuda del manejo de exepciones y errores se validaron los argumentos por consola, esto ayuda a que si el usuario no da argumentos por "defuault" toma ciertos valores.

#se hace un try/except por si hay algun error en los argumentos por consola.
# Ya sea que no se especifiquen, o pongan algo extraño.
#TAM, GEN, POB, son variables globales.
try:
    TAM = int(argv[1])
    GEN = int(argv[2])
    POB = float(argv[3])
except Exception, e:
    #en este bloque se da un valor por defecto si se lanza una exepción.
    TAM = 30  #Le asigna un valor Tamaño de 30x30 celdas
    GEN = 50  #Le asigna un valor de 50 generaciones
    POB = 0.5 #Le asigna un valor de 0.5 que quiere decir que aproximadamente estará un 50% poblado.

#Por si en consola no se le pone un tamaño decente. :P
if TAM < 10:
    print "Pon un tamanio de almenos 10 para que se pueda aprecier mejor\n"
    quit()

Después ya validados los argumentos por consola, realicé dos funciones que principales que son la de crear la matriz e imprimir la matriz.

En python para crear una matriz utilicé Listas dentro de una Lista... Como un arreglo bidimensional.

#funcion la cual crea la matriz: recibe como parámetro el tamaño de la Matriz
#nos retorna una Matriz (Lista bidimiensional) con todas sus seldas muertas 
def creaMatriz(TAMANO):
    matriz = []
    for i in range(TAMANO):
        matriz.append([0] * TAMANO)
    return matriz

#imprime la matriz con sus valores 0 o 1. Recorriendo la Matriz.
def imprimeMatriz(matriz):
    for ly in matriz:
        for lx in ly:
            print str(lx)+",",
        print "\n"

#Imprime la matriz con con ciertos simbolos en este caso si la celula esta viva imprime un 'o'
#si esta muerta imprime un espacio en blanco
def imprimeMatrizAS(matriz):
    for ly in matriz:
        print "_",
        for lx in ly:
            if lx == 1:
                print "o",
            if lx == 0:
                print " ",
        print "_"

Ahora viene lo más importante que es la implementación de las reglas del Juego de la Vida, para ello se utilizan dos funciones las cuales  una recorre cada celda y otra valida esa celda recorrida.

# con esta funcion se recorre la matriz y cada celda es es validada con la función ventana recibe como parámetro la matriz original.
#Retorna una copia validada de la matriz con el estado siguiente de cada celda.
def recorreMatriz(matriz):
    matrizNueva = creaMatriz(len(matriz))
    for i in range(0, len(matriz)):
        for j in range(0, len(matriz[i])):
            matrizNueva[i][j] = ventana(matriz, i, j)#aqui se implementa la función ventana
    return matrizNueva

#Fución ventana la cual valida si la celda en el siguiente estado se encontrará Viva o Muere.
#Recibe como parámetros el estado actual de la matriz y donde se encuentra la célula a validar (i, j)
def ventana(matriz, i, j):
    #para entender mejor las condiciones
    arr = j-1
    aba = j+1
    izq = i-1
    der = i+1
    linf= 0
    lsup= len(matriz)-1    
    n = 0
    #casos especiales del borde..... Utilicé los casos posibles que se puedieron presentar.
    if izq < linf:
        if arr < linf:
            n =[matriz[der][j], matriz[der][aba], matriz[i][aba]].count(1)
        elif aba > lsup:
            n =[matriz[der][j], matriz[der][arr], matriz[i][arr]].count(1)
        else:
            n =[matriz[i][arr], matriz[der][arr], matriz[der][j], matriz[der][aba], matriz[i][aba]].count(1)
    elif der > lsup:
        if arr < linf:
            n =[matriz[izq][j], matriz[izq][aba], matriz[i][aba]].count(1)
        elif aba > lsup:
            n =[matriz[izq][j], matriz[izq][arr], matriz[i][arr]].count(1)
        else:
            n =[matriz[i][arr], matriz[izq][arr], matriz[izq][j], matriz[izq][aba], matriz[i][aba]].count(1)
    elif aba > lsup:
        if izq < linf:
            n =[matriz[der][j], matriz[der][arr], matriz[i][arr]].count(1)
        if der > lsup:
            n =[matriz[izq][j], matriz[izq][arr], matriz[i][arr]].count(1)
        else:
            n =[matriz[izq][j], matriz[izq][arr], matriz[i][arr], matriz[der][arr], matriz[der][j]].count(1) 
    elif arr < linf:    
        if izq < linf:
            n =[matriz[der][j], matriz[der][aba], matriz[i][aba]].count(1)
        if der > lsup:
            n =[matriz[izq][j], matriz[izq][aba], matriz[i][aba]].count(1)
        else:
            n =[matriz[izq][j], matriz[izq][aba], matriz[i][aba], matriz[der][aba], matriz[der][j]].count(1)
    else:
    #esto es para si ninguno de sus vecins se salen del borde...
        n =[matriz[izq][arr], matriz[izq][j], matriz[izq][aba], matriz[i][aba], matriz[der][aba], matriz[der][j], matriz[der][arr], matriz[i][arr]].count(1)

    #Implementación de la Regla del Juego de la Vida para saber si se retorna 1 (Nace o Sobrevive) o se retorna 0 (Muere) 
    if matriz[i][j] == 1 and (n == 2 or n == 3):
        return 1

    elif matriz[i][j] == 0 and n == 3:
        return 1  
    else:
        return 0  

Por último se define una función main (para no perder la costumbre de otros lenguajes) o mejor dicho para ejecutar solamente esa rutina si el modulo no se encuentra importado en otro archivo.

def main():
    matrix = creaMatriz(TAM)

#Aqui se llena la matriz en posiciones pseudoaleatorias.
    for i in range(0, int((TAM*TAM)*POB)):
        matrix[random.randint(0, TAM-1)][random.randint(0, TAM-1)] = 1

#Esta es la rutina para imprimer e implementar las funciones en la matriz
    system("clear")
    for i in range(GEN):
        print "Generacion:", i+1
        imprimeMatrizAS(matrix)
        mod = recorreMatriz(matrix)
        matrix = mod
        time.sleep(0.6)
        system("clear")
    print "Generacion:", i+1    
    imprimeMatrizAS(matrix)    

if __name__ == "__main__": #Si el módulo a ejecutar es el mismo ejecutar main()
    main()

Capturas de Pantalla.

Ejecutando con configuración inicial.

Conclusión

Para terminar esta entrada, primeramente espero no dar pena ajena con mi código, estoy seguro de que debe de haber una forma computacionalmente mejor, aunque este algortmo fue un reto ya que intenté realizarlo sin ninguna referencia a otro código de este problema. Por otra parte me hubiera gustado agregar más cosas al codigo como por argumentos elegir algun patron o algo random y también poderlo hacer en GUI.


Referencias:

http://es.wikipedia.org/wiki/Aut%C3%B3mata_celular

http://es.wikipedia.org/wiki/Juego_de_la_vida