Summary
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