En el weekly python newsletter, enlazaban al problema de sacar la suma máxima, dado un árbol y utilizando el movimiento del clásico videojuego qBert (no del todo cierto porque qBert sí podía subir, pero eso son tecnicismos). El árbol en concreto sería así:
chrismasTree = [
[75],
[95,64],
[17,47,82],
[18,35,87,10],
[20, 4,82,47,65],
[19, 1,23,75, 3,34]
]
Y las reglas son que qBert siempre debe bajar por el árbol, bien hacia un lado o el otro.
Dado el pequeño número de datos, se puede hacer una aproximación por fuerza bruta (recorriendo todos los posibles caminos y comparándolos) pero esta solución sería malísima si cambiamos el set de datos al proporcionado por el proyecto euler en su problema 67, que aseguran que si pudieras comprobar 10⁷ rutas por segundo, tadarías 20 billones americanos (millardos por aquí) de años en resolverlo.
El código para generar este segundo árbol, sería:
tri = []
peUrl = "http://projecteuler.net/project/triangle.txt"
for line in urllib.urlopen(peUrl).readlines():
tri.append([int(x) for x in line.strip().split(" ")])
print qbertRun(tri)
Y por si quieres intentar resolverlo, no pondré mi solución hasta después de “Leer mas”.
Continue reading »
Últimos comentarios