Atribuyen a Edison la frase: “I will not say I failed 1000 times, I will say that I discovered there are 1000 ways that can cause failure.” Pues yo he estado haciendo lo mismo en los ratos libres de estos ajetreados días... +
#AdventOfCode2021 #AdventOfCode
Por las noches mientras veía alguna peli del Prime time he estado programando mi particular acercamiento al problema 15 haciendo stiching de soluciones para encontrar la solución completa al #AoC +
La dificultad no provenía del Floyd Warshall sino de como pegar las soluciones entre si propagando los costos del tal manera que no me sorprendian los fallos, hasta que aburrido/estancado pensé programar el dijkstra para tener la solución y comparar el devenir de cada código.. +
Hay mil sitios de donde coger el código, yo preferí ver si mi antiguo libro de algoritmica aún daba la talla. Y efectivamente en la pag. 90 encontré este clasico de los algoritmos voraces y la gestión de grafos..
Asi que me decidí a implementarlo de la forma mas simple posible usando simples listas (ni conjuntos ni colas de prioridad..)
Aun asi comparado con el Floyd es un poco mas complejo pero poco más, aunque me ha permitido probar por 1º vez una lambda con capturas en Python:
Asi que rehice el cuerpo de la parte 1 para usar el dijkstra y sacar la solución antes de volver a mi aventura con el Floyd..
Asi que probé con el test y funcionó sin muchos problemas..
Incluso probé un par de grid mas que tenia para pruebas y todo parecía bien..
Asi que lo usé con fichero del puzzle. Parecía ir bien asi que me aventure a pasar la solucion a la página del advent of code..
Pues resulta que no resuelve el puzle! 😅 Curioso, no? Eventualmente daré con ello, mientras seré un imitador de Edison...
Diviértanse (yo lo hago)
#AdventOfCode2021 #AdventOfCode
BTW: Pylance se ha vuelto muy lento o quizás es el intellisense del @code . ¿Alguien tienen experiencias similares?
Encontré que me he olvidado de ordenar los nodos por la distancia usando key= itemgetter(2). Sutil diferencia que necesitó de 5 ficheros mas de test y comparando desde (0,0) con (h-1, h-1) siendo h la altura del mapa...
probamos de nuevo con el fichero del puzzle. Esta vez añadí la representacion gráfica del camino...
Claramente con el algoritmo Dijkstra y si uno no está espeso la cosa está hecha (ya se encargó él de tener la claridad de mente). Voy a ver que piden en la 2º parte si no piden mucho volveré a ver si acabo mi aproximación con el Floyd (ya por curiosidad)
La 2da parte te piden extender la lista 2D A derecha y hacia abajo 5 veces y ha sido bastante fácil sin embargo a la hora de atacar el mapa completo 500x500 nodos que hecho de no usar una cola de prioridad ni montículo le está pasando factura a mi implementación de dijkstra …
Y el hecho principalmente de iniciar con la lista completa de nodos hace que tenga que hacer 6 millones de ordenaciones de una lista que en su tamaño máximo tiene 250k nodos (Y que se recrea cada vez combinándose con el coste acumulado actual para cada nodo )
Aquí la opción más rápida aparte de incorporar un montículo sería no poblar la lista inicial de nodos con todos ellos sino incrementalmente con los vecinos del nodo actual. Esto los elimina del procesamiento hasta que no sean “descubiertos”.
Tras mas de 1 hora y media corriendo, abortamos la ejecución y nos proponemos implementar algunos de estos cambios...
Primeramente añadimos un set para recordar que vertices/nodos hemos vistado ya...
La lista de nodos se poblará solamente con el nodo inicial
Cada nodo/vértice visitado se añade en el conjunto de visitados +
los candidatos se se eligen entre los vecinos (arriba, abajo, derecha e izquierda) SIEMPRE que no sean nodos que ya han sido visitados +
Finalmente si el vecino/candidato no está ya en la lista de vertices a procesar se añade a ella.
Aqui vemos la nueva función llamada dijkstra_fast(...) en toda su gloria..
La extension a 5 veces el tamaño no ha sido dificil, solo hay que llevar la cuenta de en cual tesela estamos y en que posicion relativa a la tesela original..
Comprobamos con el ejemplo que funciona correctamente, ademas podemos observar ya que el tiempo de ejecución ha disminuido obstensiblemente.. ¿Tanto? veremos luego..
Probamos en con el puzle ahora de tamaño 500x500 . dijkstra(...) tardó mas de 1 hora 30 mins sin llegar a acabar, ¿cuánto nos tomará ahora con dijkstra_fast(...)? La salida queda descolocada por el tamaño del mapa 2D pero podemos observar que en menos de 2 mins hemos terminado..
Hemos reducido el procesamiento en la lista de nodo al "frente de onda" minorando el procesamiento en la costosa lista de nodos.
Este ha sido uno de los puzles mas instructivos y aún tengo ideas en la recamara para probar con él..
Diviértanse!
#AdventOfCode #AdventOfCode2021
Ja ja ya puedo decir eso de...
I just completed "Chiton" - Day 15 - Advent of Code 2021 adventofcode.com/2021/day/15 #AdventOfCode
No quería quedarme con la espinita de no probar un montículo o "heap". Heapq permite convertir una lista en un monticulo directamente así que cambiando tres lineas tenemos la version del algorithmo que resuelve la 2da parte el día 15 en unos 8 segundos..
Me preguntaba si sería posible añadir el mismo nodo con distintos costes en el montículo y si esto afectaría al algoritmo asi q eliminé el chequeo añadiendo los vecinos con mejor coste directamente a "nodes".
Todos los test pasan y el fichero del puzle se procesa en 2 segundos..
¿Porqué me recreo aqui? por que este algorithmo de busqueda no informada es la puerta al A-Estrella. Tan solo añadir a donde queremos ir con una heurística admisible y tenemos practicamente el A*. Seguro q a los roboteros de
@UAHrobotics
les gustará juguetear con esto..
Bueno pues ya que stoy no me voy a quedar con las ganas de contar la versión recursiva y lo que es mejor el estilo de continuaciones llamada en inglés por su siglas:CPS "Continuation Passing Style"
¿quereis conocerlo? Pues seguimos el hilo...
#AdventOfCode #adventofcode2021
Recordermos la ultima version iterativa del Dijkstra "Shortest Path" que hacúa uso de un Heap o montículo...
Amen de alguna prueba con arrays voy a tranformar esta version en una recursiva con el siempre manido esquema worker/wrapper...
El worker queda definido en _dijkstra(...) con la estructura típica recursiva: Caso base + caso general.
El wrapper prepara los datos necesarios y recoge los frutos del trabajo de worker.
No ha costado mucho trabajo... Ejecutamos el fichero de test con la parte2 del día 15 y ...
Opps! tras unos 1000 niveles de anidamiento obtenemos una excepción de excesivo anidamiento recursivo..
¿como podemos librarnos de esto?
La idea es anidar un número asequible de llamadas , digamos 100 veces y abortar "prematuramente" trasladando la responsabilidad de seguir con el cálculo al call site. Pero claro el top level debe recoger el estado de todo lo que haciamos y replicar la llamada 101...
Podriamos crear una lambda que capture el estado actual de la siguiente llamada recursiva y así el call site no tiene porque saber nada de nuestro estado interno, simplemente debe ejecutar la lambda para proseguir con el cálculo. Esto es lo q se llama en el argot una continuación
modificamos el worker para llevar la cuenta del nivel de anidamiento:
- devolver una excepción en caso de maximo nivel de anidamiento que contiene una lambda que al evaluarse ejecutará la sigueinte llamada recursiva que hubieramos hecho si no hubieramos excedido el limite..
En caso de terminar la computación con exito devolver a su vez una lambda que al evaluarse devuelve el resultado. Esto no es estrictamente necesario pero lo hacemos de cara a homogenizar la interfaz del worker de cara a lo que ve al call site (el wrapper)
Por su puesto la llamada recursiva que hace el worker sigue siendo igual con la pequeá diferencia de que llevamos la cuenta de cuantos niveles de anidamiento...
Modificamos ahora el wrapper para que evalues las continuaciones en el caso normal en el caso de excepción y extraiga los datos finalmente... A continuación veremos en detalle cada cambio.
primero debemos convertir la primera llamada al worker en una continuacion, ya que el warpper ahora sólo entiende de evaluar continuaciones y no simples llamadas a funciones. En #Haskell diriamos que hemos liftado o elevado la funcion _dijkstra(...) al contexto de continuaciones
El wrapper usa un while para controlar la evaluacion y protege con un try la evaluación de la continuacion, esto nos permitirá actuar en consecuencia según la continuación eleve una excepción o no..
En caso de excepción MaxDepth (creada ad-hoc para nuestro esquema) obtenemos las continuación contenida en la excepción y dejamos que el bucle while repita la evaluación...
En caso de ejecución correcta result contiene la continuación final (recordad que _dijkstra(...) ahora solo devuelve continuaciones) asi pues la evaluamos para desempaquetar el resultado final (sea quel que sea) y lo devolvemos al call site.
probamos con el test de la segunda parte y vemos que funciona perfectamente. sabiendo que el limite que pusimos eran 100 anidamientos hemos devuelto el control en 10 excepciones y reanuado el proceso evaluando 10 lambdas y finalmente una mas para devolver el resultado.
Esta claro que con 10 continuaciones el sobrecoste ha sido minimo ( y podriamos haber puesto 500 de límite reduciendo el proceso muchos mas). Al probar con el ejemplo completo del día 15 vemos que el tiempo de proceso sigue en la figura de los 2 segundos..
En fin, hay mucho más en el #AdventOfCode que perder el culo por sacar el resultado lo mas rápido posible. Para la mayoria de nosotros es una oportunidad para aprender mas allá de la zona de confort, no la desaprovecheis!!
Diviértanse!
#AdventOfCode #adventofcode2021
@threadreaderapp unroll
Share this Scrolly Tale with your friends.
A Scrolly Tale is a new way to read Twitter threads with a more visually immersive experience.
Discover more beautiful Scrolly Tales like this.