| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

PE018

Page history last edited by Kenneth Finnegan 12 years, 6 months ago

Project Euler Problem #18 & #67

 

Of these problems, 18 is fairly trivial.  With enough work, you could even solve it with a piece of paper and pencil.  67 is orders of magnitude more diffucult.  There are 299 differet possible paths from bottom to top, and to test every one would take more computing power than that in the world and more time than that in the universe.  I finally realized that the way to solve it is to cache every value as it's calculated.

 

Start on the second to bottom row, and for each of the 99 columns, find the maximum path to the bottom, which is trivial because there is only two paths for each column.  Save these values.  Now when you move to the third bottom row, all of the maximum paths beyond the second bottom row are already calculated.  Again it's trivial because each number only has two paths to the precomputed values you already have.  This allows the solution to be solved well under the maximum minute.

 

My solution for both of these problems use the same code, just recompile it, defining TRISIZE as the number of rows in the triangle.

cc -DTRISIZE=10 018.c

./a.out << 018.input

cc -DTRISIZE=100 018.c

./a.out << 067.input

 

 018.c

 018.input

 067.input

 


Return to list of solutions

Comments (0)

You don't have permission to comment on this page.