Euler Problem 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 4
2 4 6
8 5 9 3

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

Find the maximum total from top to bottom of the triangle below:

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

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

My Solution 
def max_path_sum(triangle):
  height = len(triangle)

  #initialize state array 
  sum_triangle = []
  for i in range(height):
      sum_triangle.append([0 for _ in range(len(triangle[i]))])

  sum_triangle[0][0] = triangle[0][0]

  # Dynamic programming approach, loop through triangle and update states. 
  # This makes it run in polynomial time vs exponential with a recursion call.
  for i in range(1,height):
      for j in range(0,i+1):
          # check edge cases
          if (i==j):
              sum_triangle[i][j] = sum_triangle[i-1][j-1] + triangle[i][j]
          elif (j==0):
              sum_triangle[i][j] = sum_triangle[i-1][j] + triangle[i][j]
          else:
              # take max of prior two states and add new value
              sum_triangle[i][j] = max(sum_triangle[i-1][j-1], sum_triangle[i-1][j]) + triangle[i][j]

  return max(sum_triangle[height-1])

max_path_sum(triangle)

Answer: 1,074

Euler Problem 19

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

My Solution 
def leap_year(year):
  if (year%4==0):
      if (year%400==0):
          return True
      elif(year%100==0):
          return False
      return True
  return False

def num_sum_on_first():
  sunday_count=0
  years = list(range(1901,2001))
  # First Days of the month no leap year
  first = [1,32,60,91,121,152,182,213,244,274,305,335]
  # Change to day of the week
  first = [x%7 for x in first]
  # Jan 1, 1901 was a Tuesday, so values with remainder 6 will be Sundays.
  # 365 % 7 = 1 so starting day will shift by one each year (2 on leap years).
  for year in years:
      # Adjust first dates on leap years
      if leap_year(year):
          first = [x%7+1 for x in first]
          first[0] = first[0]-1
          first[1] = first[1]-1
      # For each first of the month, check against sunday value
      sunday_count+=first.count(6)
      # Increment for change of year
      first = [x%7+1 for x in first]
  return sunday_count

num_sum_on_first()

Answer: 171

–>