Euler Problem 18 … and 67

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:

  1. 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.
  2. 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))}"}

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>