viernes, 11 de enero de 2013

Codility - Diciembre 2012


Una lástima, esperaremos a la solución por parte de codility a ver que nos cuentan. En cualquier caso he disfrutado intentando solucionarlo.

El problema parte de una maya cuadrada de NxN nodos. En cada iteración se rompe la conexión entre dos nodos. El objetivo es indicar en qué punto se rompe la conexión entre el primer nodo y el último.

 

Un problema de búsqueda de caminos. Mi solución fue cargar la estructura en memoria. Un objeto por cada nodo que guarda referencia a los nodos con los que tiene relación (norte, sur, este, oeste). Cada iteración actualizaba los nodos para reflejar la pérdida de conexión. Teniendo esta estructura en memoria recorría los posibles caminos utilizando una pila para recordar las alternativas que iba dejando atrás.

Tras el primer certificado intenté enviar una segunda solución. Esta optimizaba la búsqueda de caminos recordando el último utilizado. Ya que la validación un camino ya calculado es mucho más rápida que completar el calculo completo. Pero no fue suficiente y los chicos de codility aun me siguen diciendo que no escalo bien.

Tengo la intuición de que sería mucho más eficiente, si de alguna forma, en vez de fijarnos en la maya, nos fijamos en la caida de los nodos. Quizá calcular cuándo se aisla una esquina sea más rápido que encontrar el camino. Pero de momento es sólo una idea.

No hay comentarios:

Publicar un comentario