SGCG

Volver arriba

Jugando con autómatas celulares (6)

2013-08-26

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. Hace unos días creamos unas pocas funciones útiles de propósito general. Estas funciones son convenientes no solamente en un programa de autómatas celulares, sino que son herramientas convenientes en muchas situaciones. Hoy presentamos una que se nos había quedado en el tintero junto a dos especializaciones: el mapa acumulativo y el producto acumulativo.

Mapa acumulativo

Vamos a necesitar generar listas de productorios parciales: listas cuyos elementos son el primer elemento de una lista de entrada; el producto del primer elemento y el segundo elemento; el producto del primer elemento, el segundo elemento y el tercer elemento… Para ello, primero definiremos una función llamada cumulative-map que aceptará un operador operator (una función) de dos argumentos, un valor inicial initial-value (que sería normalmente el elemento identidad del operador) y una lista sequence sobre la que aplicar el operador desde el primer elemento hasta el último. Lo haremos con fold:
(define (cumulative-map operator initial-value sequence) (define (accumulate item accumulator) (cons (operator item (car accumulator)) accumulator)) (reverse (fold accumulate (list (operator initial-value (car sequence))) (cdr sequence))))
Esto también funciona en Python:
def cumulative_map(operator, initial_value, sequence): def accumulate(item, accumulator): return [operator(item, accumulator[0])] + accumulator return fold(accumulate, [operator(initial_value, sequence[0])], sequence[1:])[::-1]
Usamos fold para hacer el equivalente a una función que crea una lista de forma recursiva. La función fold no tiene por qué devolver un escalar cuando se le pasa una lista. Ahora bien, como la llamada a fold va construyendo la lista de salida de derecha a izquierda, tenemos que darle la vuelta al resultado. Esta función cumulative-map falla si la secuencia está vacía.

Producto acumulativo

Ahora que tenemos nuestra función cumulative_map, es fácil generar listas de sumas parciales, listas de productos parciales y otras cosas similares. Lo que nos interesa es el generador de listas de productos parciales, cumulative-product. Tiene este aspecto en Scheme:
(define (cumulative-product sequence) (cumulative-map * 1 sequence))
Es casi igual en Python:
def cumulative_product(sequence): return cumulative_map(lambda a, b: a * b, 1, sequence)

Otra posible aplicación interesante del mapa acumulativo

Digamos que tenemos un autómata celular cuya regla de evolución no es autónoma, sino que depende de algún parámetro externo. Para fijar ideas, supongamos que este autómata es un ecosistema de juguete en el que la evolución de una celda depende de las celdas vecinas y de parámetros externos que modelan las condiciones meteorológicas. Podríamos usar cumulative-map para generar un conjunto de generaciones sucesivas de nuestro autómata celular a partir de una lista de condiciones meteorológicas y un estado inicial.

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.
• 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 cómodamente.
• 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: https://sgcg.es/articulos/2013/08/26/jugando-con-automatas-celulares-6/

Volver arriba