SGCG

Volver arriba

Jugando con autómatas celulares (10)

2013-09-02

Hace varios artículos, 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.

Seguimos construyendo funciones para hacer una biblioteca de autómatas celulares razonablemente general y práctica. El trabajo de hoy nos permitirán crear muchas generaciones sucesivas de nuestros autómatas cómodamente.

Bucle interactivo

Podemos generalizar lo que hicimos con la función interactive-rule-90 del segundo artículo de la serie. Vamos a crear una función llamada interactive-step que aceptará la regla rule a aplicar, una lista cells de celdas, una función neighbourhoods con la que extraer los vecindarios y una función display-cells con la que mostrar por pantalla las celdas. Esta función es así en Scheme:
(define (interactive-step rule cells neighbourhoods display-cells) (display-cells cells) (if (not (equal? (read-char) #\q)) (interactive-step rule (apply-rule rule cells neighbourhoods) neighbourhoods display-cells)))

El parámetro display-cells puede ser display simplemente o, mejor, una llamada a translate-and-display-1d, esta función que aceptaba una cadena translation-table que permitía traducir los números de estado a caracteres mediante la función translate; estas funciones de traducción fueron definidas hace varios artículos.

La versión de Python es similar, pero en vez de usar recursión final, usamos un bucle. El código es así:
def interactive_step(rule, cells, neighbourhoods, display_cells): import sys display_cells(cells) while not sys.stdin.readline()[0] is 'q': new_cells = apply_rule(rule, cells, neighbourhoods) cells = new_cells display_cells(cells)

Bucle no interactivo

También podemos querer iterar el autómata cierto número de generaciones. Recogeremos las generaciones en una lista para su posterior inspección y manipulación. Esta vez, usaremos un bucle do explícito en vez de nuestras construcciones funcionales habituales. El trabajo con unfold en este caso sería algo engorroso debido a que habría que empaquetar los argumentos o, como alternativa, a definir algún elemento no estrictamente funcional como una función que mediante clausura fuera haciendo descender un contador interno. Esta versión tan concisa hace la magia:
(define (step rule cells neighbourhoods number-of-generations) (do ((current-cells cells (apply-rule rule current-cells neighbourhoods)) (generations-so-far '() (cons current-cells generations-so-far)) (generations-left number-of-generations (- generations-left 1))) ((< generations-left 1) (reverse generations-so-far))))
Acepta una función regla rule, una lista de celdas inicial cells, una función de extracción de vecindarios neighbourhoods y el número number-of-generations de generaciones que crear. La salida es una lista cuyos elementos son las listas de celdas de las diferentes generaciones desde la primera hasta la última.

El código de Python hace algo similar, pero con la lista de generaciones creada desde el principio. El resultado es el mismo. El código es el siguiente:
def step(rule, cells, neighbourhoods, number_of_generations): generations_so_far = [] * number_of_generations generations_so_far[0] = cells for generation_number in range(1, number_of_generations, 1): current_cells = generations_so_far[generation_number-1] generations_so_far[generation_number] = apply_rule(rule, current_cells, neighbourhoods) return generations_so_far

Otros artículos de la serie

• Introducción.
• Pequeño autómata de demostración.
• Función para crear reglas deterministas.
• Funciones para sacar por pantalla las listas de celdas.
• Funciones auxiliares útiles.
• Más funciones auxiliares útiles.
• Funciones para trabajar con mallas cartesianas.
• Extracción de vecinos en mallas cartesianas cíclicas.
• Funciones para crear autómatas unidimensionales elementales.
• Prueba con varios autómatas elementales.
• Funciones para imprimir autómatas bidimensionales cartesianos.
• Juego de la vida de Conway.
• Funciones para trabajar con autómatas no deterministas.
• Autómata no determinista: modelo del incendio forestal.
• Autómatas de segundo orden.
• Mejora del rendimiento mediante memoización.
• Más pequeñas modificaciones para acelerar notablemente el código.
• Salida de imágenes.

Categorías: Informática

Artículos publicados el mismo mes

Permalink: http://sgcg.es/articulos/2013/09/02/jugando-con-automatas-celulares-10/

Volver arriba