Advertisement
Guest User

Project Euler #18 and 67

a guest
Oct 7th, 2016
304
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.83 KB | None | 0 0
  1. #This is where you would paste an array of the numbers
  2. pyramid = [...]
  3.  
  4. #Runs a "sum factorial" function (like a regular factorial but adding instead of multiplying) as part of finding the position in the array
  5. #The basic idea is that the position of the first number in a row is equal to the sum factorial of that row number minus 1
  6. def sum_factorial(x):
  7.     total = 0
  8.     for i in range(x, 0, -1):
  9.         total += i
  10.     return total
  11.  
  12. #Finds positin in the array of numbers corresponding to the inputs row and iteration within that row
  13. #The position is found by running the sum factorial function on the row number, adding the iteration within the row
  14. #and subtracting 1 as arrays start counting from 0
  15.  
  16. def position(row, iteration):
  17.     return sum_factorial(row - 1) + iteration - 1
  18.  
  19. #Iterates for the number of rows in the triangle minus 1, starting from the bottom to the top
  20. for row in range(99, 0, -1):
  21.     #The amount of iterations in a row is equal to the row number, but you must add 1 because range() does not include the second value
  22.     for iteration in range(1, row + 1):
  23.         #Checks to see if the number to the bottom left of the current number it is checking (it checks all numbers in each row) is greater than the number to the right
  24.         if pyramid[position(row, iteration) + row] > pyramid[position(row, iteration) + row + 1]:
  25.             #If it is greater, the current number is now equal to itself + the number to the bottom left of it
  26.             pyramid[position(row, iteration)] += pyramid[position(row, iteration) + row]
  27.         else:
  28.             #Otherwise, it is now equal to itself + the number to the right of it
  29.             pyramid[position(row, iteration)] += pyramid[position(row, iteration) + row + 1]
  30.  
  31. #The top number should now be equal to the sum of the route with largest route
  32. print(pyramid[0])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement