SGCG

Volver arriba

Jugando con autómatas celulares (12)

2013-09-12

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.

Hasta el momento, todos los ejemplos que hemos visto han sido de autómatas unidimensionales. Los autómatas unidimensionales son fáciles de visualizar. También son fáciles de visualizar los bidimensionales, aunque con la desventaja de que no podemos seguir su historia de un vistazo en una pantalla bidimensional como sí podemos hacer con los unidimensionales. Hoy vamos a preparar una función para imprimirlos por pantalla cómodamente. Nos centraremos en autómatas definidos en un retículo cartesiano; dejamos fuera otras construcciones más complicadas como pueden ser los retículos hexagonales o de panal de abeja.

Conversión de listas planas en listas de listas

Resulta muy conveniente convertir la representación de lista plana de un retículo cartesiano bidimensional en una lista cuyos elementos son a su vez listas, cada una con una fila del retículo. Podemos hacer el trabajo de forma muy compacta con ayuda de las funciones que ya hemos diseñado en entregas anteriores. En Scheme, el código es así:
(define (cartesian-rows cells sizes) (let ((rows (car sizes)) (columns (cdr sizes))) (map (lambda (row) (map (lambda (column) (matrix-ref cells sizes (list row column))) (range 0 columns 1))) (range 0 rows 1))))
La función cartesian-rows acepta una lista plana de celdas cells y una lista de dimensiones sizes que contiene el número de filas y el número de columnas. La traducción esencialmente literal a Python es así:
def cartesian_rows(cells, sizes): rows, columns = sizes return map(lambda row: map(lambda column: matrix_ref(cells, sizes, (row, column)), range(0, columns, 1)), range(0, rows, 1))

Impresión por pantalla de retículos cartesianos bidimensionales

Vamos a reutilizar la función translate-and-display-1d. La nueva función, translate-and-display-cartesian-2d, convierte su argumento cells (una lista plana de celdas que representa un retículo bidimensional) junto con el segundo argumento sizes (una lista de dimensiones con el número de filas y el número de columnas) para obtener una lista de filas con cartesian-rows; posteriormente, recorre esta lista de filas y hace llamadas sucesivas a translate-and-display-1d con la tabla de traducción translation-table (que es una cadena de caracteres que sirve para asignar los números de los estados de las celdas a los caracteres en las posiciones correspondientes de la cadena). Quizá queda más claro el código en Scheme:
(define (translate-and-display-cartesian-2d cells sizes translation-table) (for-each (lambda (row) (translate-and-display-1d row translation-table) (newline)) (cartesian-rows cells sizes)))
La traducción a Python también es inmediata:
def translate_and_display_cartesian_2d(cells, sizes, translation_table): import sys for row in cartesian_rows(cells, sizes): translate_and_display_1d(row, translation_table) sys.stdout.write('\n')

Veamos un ejemplo del código anterior:
(translate-and-display-cartesian-2d '(0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0) '(5 4) " *")
La salida es así:
* * * * *

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.
• Funciones para crear generaciones sucesivas de autómatas cómodamente.
• Prueba con varios autómatas elementales.
• 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/12/jugando-con-automatas-celulares-12/

Volver arriba