Euler problem 18 has taken me far longer to conquer than it should have, for the following reasons which I offer here as a guide to others:

**I aimed low at first**

I tried to write the ‘brute force’ version, thinking I’d learn something along the way and that it would be a good step I could later optimise.

It proved time consuming and didn’t help me derive my optimal solution.**I took my eyes off the prize**

…and concentrated on reading the tree, and storing routes and visited nodes. I’d forgotten the question. Using TDD here might’ve saved me some time.

Ditching what I had ans following my instincts, the solution virtually wrote itself. In summary:

- Start with the bottom 2 rows, and work up. Determine which of the two numbers on the lower row will produce the highest return when added to the single number in the row above.
- Use the derived maximum value to overwrite the single number in the upper row.
- Repeat until you cannot repeat any more.

I was thrilled to see this return very quickly for Problem 18, more so when it was just as fast for Problem 67.

Here’s my solution, in Ruby:

# Project Euler - solution to problems 18 and 67

triangles = []

triangles << [75,95,64,17,47,82,18,35,87,10,20,4,82,47,65,19,1,23,75,3,34,88,2,77,73,7,63,67,99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31,4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]

def makeTriangle(ar)

rowCount=0

$rowsArr=[]

while ar.size > 0

$rowsArr[rowCount] = []

reducer = rowCount+1

while reducer > 0

$rowsArr[rowCount].push(ar.shift)

reducer-=1

end

rowCount+=1

end

$rowsArr

end

def solveTriangle(triangle)

numRows = triangle.length()-1

while numRows > 0

$ar= Array.new

$rowsArr[numRows-1].each_index{|i|

sumFirstRoute = triangle[numRows-1][i]+triangle[numRows][i]

sumLastRoute = triangle[numRows-1][i]+triangle[numRows][i+1]

higher = sumFirstRoute>sumLastRoute ? sumFirstRoute : sumLastRoute

triangle[numRows-1][i]= higher

}

numRows-=1

end

triangle[0][0]

end

triangles.each{|tri| puts "Max attainable value from triangle\: #{solveTriangle( makeTriangle(tri))}"}

triangles = []

triangles << [75,95,64,17,47,82,18,35,87,10,20,4,82,47,65,19,1,23,75,3,34,88,2,77,73,7,63,67,99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31,4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]

def makeTriangle(ar)

rowCount=0

$rowsArr=[]

while ar.size > 0

$rowsArr[rowCount] = []

reducer = rowCount+1

while reducer > 0

$rowsArr[rowCount].push(ar.shift)

reducer-=1

end

rowCount+=1

end

$rowsArr

end

def solveTriangle(triangle)

numRows = triangle.length()-1

while numRows > 0

$ar= Array.new

$rowsArr[numRows-1].each_index{|i|

sumFirstRoute = triangle[numRows-1][i]+triangle[numRows][i]

sumLastRoute = triangle[numRows-1][i]+triangle[numRows][i+1]

higher = sumFirstRoute>sumLastRoute ? sumFirstRoute : sumLastRoute

triangle[numRows-1][i]= higher

}

numRows-=1

end

triangle[0][0]

end

triangles.each{|tri| puts "Max attainable value from triangle\: #{solveTriangle( makeTriangle(tri))}"}