…esto no es un subtítulo…
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.
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:
* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
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.
Categorías: Informática
Permalink: https://sgcg.es/articulos/2013/08/18/jugando-con-automatas-celulares-2/