Jugando con autómatas celulares (8)

2013-08-29

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. Nuestros autómatas celulares pueden tener topologías muy diversas, pero una de las más comunes es la de una malla cartesiana que a menudo es toroidal o cíclica: al avanzar en una de las direcciones coordenadas, la malla se repite periódicamente. Las funciones que hemos preparado para el trabajo general funcionan con listas planas, pero aprovechamos el último artículo para crear unas funciones que nos permiten pasar de índices planos a los índices multidimensionales correspondientes y también en el sentido opuesto. Hoy vamos a aprovechar estas funciones para crear otras con las que extraer los vecindarios de las celdas, que es algo fundamental para el funcionamiento de nuestros autómatas celulares.

Aritmética de índices

Necesitamos una función para sumar índices multidimensionales. Esta función es útil para obtener el vecindario de una celda. Nos interesa trabajar en una topología toroidal o cíclica: si un índice sobrepasa su límite por un extremo, vuelve por el extremo opuesto. Esto lo hacemos con aritmética modular. La siguiente función, cyclic-addition, hace el trabajo:
(define (cyclic-addition sizes indices1 indices2) (map (lambda (size index1 index2) (modulo (+ index1 index2) size)) sizes indices1 indices2))
La función admite como parámetros una lista sizes con los tamaños de las diferentes dimensiones, una lista indices1 con los índices que son el primer sumando y una lista indices2 con los índices que son el segundo sumando. El resultado es una lista con el conjunto de índices suma módulo cada dimension del primer conjunto de índices y el segundo conjunto de índices. El código en Python es similar:
def cyclic_addition(sizes, indices1, indices2): def add_one_index(size, index1, index2): return (index1 + index2) % size return tuple(map(add_one_index, sizes, indices1, indices2)))

Acceso a las celdas mediante índices multidimensionales

Almacenamos los conjuntos de celdas en listas planas, pero necesitamos acceder a celdas específicas mediante sus correspondientes índices multidimensionales. Podemos hacer esto fácilmente porque ya preparamos una función llamada multidimensional->flat que convierte un conjunto de índices multidimensionales a un índice plano.

Ahora vamos a crear una función llamada matrix-ref que acepta una lista plana matrix, una lista sizes de tamaños de dimensiones y una lista indices de índices multidimensionales y devuelve el elemento de la lista plana matrix correspondiente a los índices especificados. Esta función es así:
(define (matrix-ref matrix sizes indices) (list-ref matrix (multidimensional->flat sizes indices)))
En Scheme, estamos guardando los conjuntos de celdas en listas simplemente enlazadas. Algo malo que tiene esto es que el coste del acceso aleatorio es lineal. Si esto se convierte en un problema, podemos pasar a trabajar con vectores y usar vector-ref en vez de list-ref.

Tras el código de Scheme, toca el código de Python. En este caso, no nos preocupamos del tipo de estructura de datos. El código es así:
def matrix_ref(matrix, sizes, indices): flat_index = multidimensional_to_flat(sizes, indices) return matrix[flat_index]

Extracción de los vecindarios

Llega la hora de crear una función para extraer vecindarios en mallas cartesianas cíclicas. La función se llamara cyclic-cartesian-neighbourhoods y aceptará una lista de celdas cells, una lista de tamaños de las distintas dimensiones sizes y una especificación de las posiciones relativas de los vecinos offsets. Este último parámetro nos da una forma muy compacta de especificar cómo son los vecindarios: se trata de una lista cuyos elementos son a su vez listas con los índices relativos al actual de los vecinos; por ejemplo, en un autómata bidimensional en que el primer índice va según el eje arriba-abajo (índices pequeños arriba, índices grandes abajo) y el segúndo índice va según el eje izquierda-derecha (índices pequeños a la izquierda, índices grandes a la derecha), la especificación ((-1 0) (1 0) (0 1) (-1 0)) daría como vecindario la celda de arriba, la de abajo, la de la derecha y la de la izquierda. Todo esto lo logramos con el siguiente código de Scheme:
(define (cyclic-cartesian-neighbourhoods cells sizes offsets) (define (neighbour indices offset) (matrix-ref cells sizes (cyclic-addition sizes indices offset))) (define (neighbourhood indices) (map (lambda (offset) (neighbour indices offset)) offsets)) (define indices (map (lambda (flat-index) (flat->multidimensional sizes flat-index)) (range 0 (length cells) 1))) (map neighbourhood indices))
Si este código es lento, la optimización más evidente consiste en hacer que matrix-ref trabaje con vectores y hacer una transformación list->vector para disfrutar de un tiempo de acceso mucho más rápido.

Digamos que tenemos una lista de celdas (11 12 13 21 22 23 31 32 33) con topología bidimensional de dimensiones (3 3). Si queremos obtener la celda de la misma columna y la fila inmediatamente superior y la celda de la misma fila y la columna inmediatamente a la derecha, hacemos lo siguiente:
(cyclic-cartesian-neighbourhoods '(11 12 13 21 22 23 31 32 33) '(3 3) '((-1 0) (0 1)))
El resultado es el que sigue:
((31 12) (32 13) (33 11) (11 22) (12 23) (13 21) (21 32) (22 33) (23 31))

Tras el código de Scheme, toca el de Python, que es muy similar:
def cyclic_cartesian_neighbourhoods(cells, sizes, offsets): def neighbour(indices, offset): return matrix_ref(cells, sizes, cyclic_addition(sizes, indices, offset)) def neighbourhood(indices): return map(lambda offset: neighbour(indices, offset), offsets) indices = map(lambda index: flat_to_multidimensional(sizes, index), range(0, len(cells), 1)) return map(neighbourhood, indices)

Gracias a todo lo que hemos preparado hasta ahora, la función que extrae vecindarios es muy cortita. El trabajo que hay detrás es algo mayor que el que habríamos tenido que hacer si nos hubiéramos conformado con hacer únicamente una función de extracción de vecindarios llena de bucles explícitos, pero a cambio hemos conseguido unas herramientas muy generales que podemos usar para otros fines. Todo este código no es muy pythónico, eso sí; al fin y al cabo, el diseño original está hecho en Scheme y la versión en Python es más o menos una transcripción directa, así que el resultado es más bien schémico y algo incómodo en Python.

Tenemos casi todo listo para empezar a trabajar.

Otros artículos de la serie

Categorías: Informática

Permalink: http://sgcg.es/articulos/2013/08/29/jugando-con-automatas-celulares-8/

SGCG