[pyar] Problemita

[Tordek]

On 10/06/10 18:58, Jesús Francisco wrote:
> 2010/6/10 Marcos Moyano<marcos en anue.biz>:
>>  Hola lista,
>>  Les paso un problemita que me estuvo comiendo la cabeza un buen rato del día
>>  de hoy y lamentablemente no encontré una solución elegante. Por ahi algún
>>  valiente con ganas me tire una mano :-)
>>
>>  A) Mirar el triangulo/grafo:
>>      5
>>     9 6
>>    4 6 8
>>  0 7 1 5
>>  B) Arrancando desde arriba (5) y moviéndonos para abajo a numeros
>>  adyacentes, vayamos sumándolos. La suma máxima es: 5 + 9 +  6 + 7 = 27
>>  (ejemplo de otros caminos posibles son: 5 + 6 + 8 + 5, 5 + 9 + 4 + 7, 5 + 6
>>  + 6 + 7, etc.) (Notar el último ejemplo)
>>
>>  Alguien me tira una idea de como modelaría la estructura de manera que sea
>>  *simple* la solución?
>>  En la teoría todo bien. Podemos usar Dijkstra o A* y sale de pelos, pero no
>>  logro implementarlo de manera "sencilla".
>>
>
> Si lo que quieres es la suma máxima, pues por cada piso agarra el
> máximo y súmalos.
>
> sum(max(piso) for piso in piramide)

Solo podes sumar numeros adyacentes de cada piso. Es decir: tu 
solución da 5 + 9 + 8 + 7... pero no hay un camino 9-8.

-- 
Guillermo O. «Tordek» Freschi. Programador, Escritor, Genio Maligno.
http://tordek.com.ar :: http://twitter.com/tordek
http://www.arcanopedia.com.ar - Juegos de Rol en Argentina