SGCG

…esto no es un subtítulo…

Ir a: contenido categorías calendario archivo suscripción

Volver arriba

Jugando con autómatas celuluares (2)

2013-08-18

En el anterior artículo, planteamos un interesante proyecto: una pequeña biblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.

Antes de plantear la arquitectura completa de un sistema de autómatas celulares más o menos versátil, vamos a construir nuestro primer autómata elemental. Así podremos jugar un poco antes de entrar en un terreno más árido.

Diseño del primer autómata celular elemental

Nuestro primer autómata consiste en una circunferencia de celdas con dos estados posibles cada una: 0 y 1. Como la topología es la de una circunferencia, todas las celdas tienen una celda vecina a la izquierda y una celda vecina a la derecha; si la topología fuera la de un segmento finito, a la celda de cada extremo le faltaría una vecina.

Nuestro primer autómata va a ser determinista y va a usar lo que se conoce como la regla 90 o la de Martin—Odlyzko—Wolfram. Esta regla solamente depende del estado de la celda de la izquierda y el estado de la celda de la derecha: si la celda de la izquierda está a 1 y la celda de la derecha está a 0, el nuevo estado es 1; si la celda de la izquierda está a 0 y la celda de la derecha está a 1, el nuevo estado es 1; en todos los demás casos, el nuevo estado es 0. En Scheme, la regla es así:
(define (rule-90 neighbours) (let ((left (car neighbours)) (right (cdr neighbours))) (cond ((and (= 1 left) (= 0 right)) 1) ((and (= 0 left) (= 1 right)) 1) (else 0))))
En este código, los vecinos, neighbours, vienen en forma de un par cuyo primer elemento (el car) es el estado de la celda de la izquierda (left) y cuyo segundo elemento (el cdr) es el estado de la celda de la derecha (right). La versión en Python es así:
def rule_90(neighbours): left = neighbours[0] right = neighbours[1] if left == 1 and right == 0: return 1 elif left == 0 and right == 1: return 1 else: return 0
En este caso, los vecinos (neighbours) llegan en forma de una tupla cuyo primer elemento es el estado de la celda de la izquierda (left) y cuyo segundo elemento es el estado de la celda de la derecha (right).

Ahora nos hace falta una función para estraer el vecindario de una lista de celdas. Lo más interesante es que la topología es la de una circunferencia, así que la celda anterior a la primera celda es la última celda y la celda siguiente a la última celda es la primera celda. En Scheme, obtener la lista de celdas a la derecha es fácil: es la cola de la lista de celdas tras dejar el primer elemento fuera y, al final, el primer elemento. La lista de celdas a la izquierda es commo la de la de celdas a la derecha, pero calculada del revés. La idea es la siguiente:
(define (rule-90-neighbourhoods cells) (define sllec (reverse cells)) (define left (reverse (append (list-tail sllec 1) (list (car sllec))))) (define right (append (list-tail cells 1) (list (car cells)))) (map cons left right))
Esta función, rule-90-neighbourhoods, acepta una lista de celdas (cells), construye las celdas a la izquierda (left) y las celdas a la derecha (right) y empaqueta todo esto en una lista en la que cada elemento es un par con el estado de la celda a la izquierda y el estado de la celda a la derecha de la celda correspondiente. El código en Python es similar:
def rule_90_neighbourhoods(cells): sllec = cells[::-1] left = (sllec[1:] + [sllec[0]])[::-1] right = cells[1:] + [cells[0]] return zip(left, right)
El funcionamiento es idéntico, pero usamos la sintaxis más críptica pero a la vez más compacta de Python y además usamos la función zip, que a efectos prácticos hace lo mismo que el (map cons left right) de la versión de Scheme: recorre los elementos de las listas left y right y los empaqueta en pares.

Tenemos que mostrar por pantalla nuestras listas de celdas. Podemos imprimir un asterisco si una celda está a 1 y un espacio si una celda está a 0. Definamos una función llamada display-cells que acepte una lista de celdas e imprima según este criterio:
(define (display-cells cells) (display (list->string (map (lambda (cell) (if (= cell 1) #\* #\ )) cells))))
La función equivalente en Python es así:
def display_cells(cells): import sys sys.stdout.write(''.join(map(lambda cell: '*' if cell == 1 else ' ', cells)))

Ya tenemos casi todo preparado. Ahora necesitamos algo para poner el autómata celular en movimiento. Vamos a inventarnos una función llamada interactive-rule-90 que va a aceptar como entrada el estado inicial de las celdas e imprimirá una nueva generación cada vez que el usuario pulse <ENTER> o parará cuando el usuario introduzca la letra q. Usamos las funciones escritas hoy en combinación con la sencillísima apply-rule que definimos el otro día para iterar de generación en generación de celdas. Esto es así en Scheme:
(define (interactive-rule-90 cells) (display-cells cells) (if (not (eq? (read-char) #\q)) (interactive-rule-90 (apply-rule rule-90 cells rule-90-neighbourhoods))))
Este planteamiento recursivo puede explotar en Python, así que lo escribimos de forma iterativa:
def interactive_rule_90(cells): import sys while True: display_cells(cells) if sys.stdin.read(1) == 'q': break new_cells = apply_rule(rule_90, cells, rule_90_neighbourhoods) cells = new_cells

Estamos en condiciones de empezar a jugar. Podemos hacer esto en Scheme:
(interactive-rule-90 '(0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0))
En Python:
interactive_rule_90(8 * [0] + [1] + 8 * [0])
Tras pulsar <ENTER< varias veces, sale esto:

        *        
       * *       
      *   *      
     * * * *     
    *       *    
   * *     * *   
  *   *   *   *  
 * * * * * * * * 
*               *

¡Recuerda a un triángulo de Sierpinski!

Trabajo futuro

Lo que hemos hecho hasta ahora no es ni elegante ni adaptable. Plantearemos en los próximos artículos un sistema muy flexible que nos permitirá expresar cómodamente nuevos autómmatas celulares con los que experimentar.

Otros artículos de la serie


Categorías: Informática

Permalink: http://sgcg.es/articulos/2013/08/18/jugando-con-automatas-celulares-2/