Project Euler 16

[abyss]

Here is the solution to Project Euler problem 16 in thinBasic. The algorithm can also be used for problem 67.

Problem description (slight formatting issues on the bigger triangle, for the right formatting go to http://projecteuler.net/index.php?section=problems&id=18):


By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 5
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total of the following triangle:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23


It is written in comments, but let me repeat that the algorithm is based on the brilling idea described in http://blog.functionalfun.net/2008/08/project-euler-problems-18-and-67.html.



' Project Euler 18 solution (can be used for PE 67 as well)
' following the tips in http://blog.functionalfun.net/2008/08/project-euler-problems-18-and-67.html
' by Spyros Paraschis

uses "console"

const MAXROWS=15

dim i,n,f,g as integer
dim s as string

dim triangle(MAXROWS,) as string
triangle(1,1)=75
triangle(2,1)=95,64
triangle(3,1)=17,47,82
triangle(4,1)=18,35,87,10
triangle(5,1)=20,04,82,47,65
triangle(6,1)=19,01,23,75,03,34
triangle(7,1)=88,02,77,73,07,63,67
triangle(8,1)=99,65,04,28,06,16,70,92
triangle(9,1)=41,41,26,56,83,40,80,70,33
triangle(10,1)=41,48,72,33,47,32,37,16,94,29
triangle(11,1)=53,71,44,65,25,43,91,52,97,51,14
triangle(12,1)=70,11,33,28,77,73,17,78,39,68,17,5
triangle(13,1)=91,71,52,38,17,14,91,43,58,50,27,29,48
triangle(14,1)=63,66,04,68,89,53,67,30,73,16,69,87,40,31
triangle(15,1)=04,62,98,27,23,09,70,98,73,93,38,53,60,04,23

console_writeline("Project Euler 18 solver")
ShowTriangle()

for i=MAXROWS-1 to 1 step -1
for n=1 to MAXROWS-1
if triangle(i,n)<>"" then
g=val(triangle(i,n))
f=max(g+val(triangle(i+1,n)),g+val(triangle(i+1,n+1)))
triangle(i,n)=f
end if
next
next



console_writeline()
console_writeline("Replacing with sums")


console_writeline("The maximum sum is " & triangle(1,1))

console_writeline("Press any key to end")
waitkey

function ShowTriangle()
for i=1 to MAXROWS
s=string$((MAXROWS-i) * 2," ")
for n=1 to MAXROWS 'ubound(triangle(i))
if triangle(i,n) <>"" then s=s & format$(triangle(i,n),"00") & " "
next
console_writeline(s)
next
end function