21 de julio de 2012

Project Euler 18

I wrote the following code but it was not my idea, i already 
solved this problem before (bruteforce,), so i had access to 
some solutions others explained on Project Euler's forums, 
this is mather's idea.

Escribí el siguiente código pero no fue mi idea, y a había 
resuelto este problema con anterioridad (fuerza bruta) así 
que tenía acceso a soluciones que otros ya explicaron en 
los foros de Project Euler. Esta idea es de "mather" 


#!/usr/bin/env python
tr=[]
ap=tr.append #Just trying
ap([75])     #to fit it
ap([95,64])  #in the blog
ap([17,47,82])
ap([18,35,87,10])
ap([20,4,82,47,65])
ap([19,1,23,75,3,34])
ap([88,2,77,73,7,63,67])
ap([99,65,4,28,6,16,70,92])
ap([41,41,26,56,83,40,80,70,33])
ap([41,48,72,33,47,32,37,16,94,29])
ap([53,71,44,65,25,43,91,52,97,51,14])
ap([70,11,33,28,77,73,17,78,39,68,17,57])
ap([91,71,52,38,17,14,91,43,58,50,27,29,48])
ap([63,66,4,68,89,53,67,30,73,16,69,87,40,31])
ap([4,62,98,27,23,9,70,98,73,93,38,53,60,4,23])
routes=tr[0]
for i in range(13,-1,-1):
    for j in range(i+1):
        if tr[i+1][j]>tr[i+1][j+1]:
            tr[i][j]+=tr[i+1][j]
        else:
            tr[i][j]+=tr[i+1][j+1]
print tr[0][0]

The idea here is to begin with the penultimate row comparing
the two adjacent numbers in the next row to sum the largest 
to the current cell all the way up to the first row.


La idea es empezar con el penúltimo renglón comparando los
dos números adyacentes del siguiente renglón para sumarle
el mayor de los dos a la entrada actual, repitiendo esto hasta
el primero renglón.


Note:
I did not publish my solution because it is pure bruteforce.
Nota:
No publiqué mi solución porque es pura fuerza bruta.