La tela de araña

propuesto por josejuan

Un problema fácil de resolver imperativamente... ¿y funcionalmente? (inmutabilidad y transparencia referencial). Aun así (el enfoque funcional), creo que puede ser un buen kata para practicar punteros y/o TAD's.

Enunciado
Tenemos una estructura GRANDE, puede ser una lista, un árbol, un grafo, etc... por concretar y simplificar, sea un grafo con NxN nodos formando una cuadrícula.

En dicha cuadrícula, tenemos cierto número de arañas situadas en nodos distantes, por simplificar, situarlas inicialmente en cada vértice de la diagonal (habrá N arañas).

Cada araña, puede realizar 2, 3 o 4 movimientos estando en un vértice (arriba, abajo, izquierda y/o derecha).

La tela de araña para 4x4 inicialmente sería así:

*---+---+---+
|   |   |   |
+---*---+---+
|   |   |   |
+---+---*---+
|   |   |   |
+---+---+---*



Todas las arañas se mueven según una entrada (por simplificar se puede tomar el movimiento aleatoriamente) y al llegar a cada vértice, incrementan el valor que contiene (inicialmente todos a cero excepto en el que están las arañas).

Así, de la cuadrícula inicial, en un paso se mueven todas las arañas y se obtiene la cuadrícula 2, al siguiente paso se obtiene la cuadrícula, etc...

Las arañas NO se estorban unas a otras.

Se puede hacer una función que muestre el árbol, las arañas y los vértices para poder ver evolucionar al sistema.

RECUERDA, se supone que la estructura es lo suficientemente grande como para que sea inaceptable reconstruir la cuadrícula a cada paso y sólo interesa ir actualizando las N posiciones de las NxN totales en cada paso.

En un lenguaje imperativo (y en particular con punteros, arrays, diccionarios, etc...) es un desafío normal, ¿como se convierte este problema si nuestro código debe ser inmutable y transparente referencialmente?

¡Suerte! ;)

UPDATED: información de zippers en haskell zipper

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

10 Soluciones

Dar mi solución

2votos
La tela de araña en Clojure
por

vemv

hace 6 años

Es posible que la reprentación que escogí del grafo no sea la más adecuada: http://en.wikipedia.org/wiki/Adjacency_list. Por otra parte, no quise tomar prestada directamente la 'list comprehension' de josejuan. El caso es que le cogí cariño después de dedicarle un buen rato a su implementación ;p El enfoque es efectivamente inmutable. Sin embargo la implementación tiene bastante guiños imperativos. Diría que el problema descrito es esencialmente secuencial, por lo que no es paralelizable.

Dar mi solución