Bytes
You enter a gold mine with one goal: to become filthy rich. But there’s a catch. Every step you take collects gold and collapses the tunnel behind you. There’s no going back. Luckily, there’s another way out. So which route leaves you the richest by the time you escape?
The Challenge
Uno podría pensar que el mayor desafío de los laberintos es encontrar el camino más corto y salir cuanto antes. Pero este caso que nos ocupa es de hecho un poco más complicado. No queremos salir rápido, sino salir con la mayor cantidad de oro posible. Encontrar un camino cualquiera es fácil, encontrar el más corto es también fácil, pero encontrar el más largo de todos es un desafío totalmente diferente.
El principal motivo por el cual este problema es tan difícil es porque tenemos que encontrar todos los caminos posibles para asegurarnos de que no nos estamos perdiendo de ningún camino con más oro. Y el número de caminos posibles crece rápidamente con el tamaño del mapa.
Muchas veces subestimamose el poder de la combinatoria. Por ejemplo, este mapa simple realmente tiene 90 caminos diferentes. Si, 90, totalmente diferentes unos de otros. ¿Cuál es el mejor? Resulta que se pueden conseguir 87 unidades de oro con uno de ellos. ¿Podrías encontrarlo tú también?
Draft
TODO: explain the rules of the mine and why the objective is not the shortest path.
TODO: show a first brute-force / DFS style solution.
TODO: explain pruning ideas and memoization opportunities.
TODO: compare simple correctness-first code with optimized code.