James Pine Has A Blog

Problem #18, find the greatest sum of numbers along a path in a triangle of numbers, looks like a standard tree search problem. However, there’s a note at the bottom stating a brute force method won’t work for a harder/bigger version in problem #67. So I decided to skip the exercise of writing the tree traversal and think about a more efficient way of getting to the solution.

It occurred to me that it would be possible to follow multiple paths, computing sums at each level of the triangle and then the maximum number out of all the ones at the bottom would be the answer. Before I started coding, I realized it would be even easier to work from the bottom up and then I’d be left with the answer.

First I needed to read the numbers from the file into a data structure. I decided a list of lists would be fine:

def readRowsOfNumbersFile(f):
 g = []
 file = open(f,"r")
 while True:
  temp = file.readline()
  if not temp:
   break 
  g.append(map(int,temp.split()))
 file.close()
 return g

Then it was fairly trivial to sum the numbers and return the answer. First I reversed the order of the rows, then set the list of sums to the first row. For each of the following rows a new row of sums is constructed by taking the maximum of the sum of each number and the number above it and above and to the right.

g = readRowsOfNumbersFile(sys.argv[1])
g = g[::-1]
sums = g[0]
for r in xrange(1,len(g)):
 prevSums = sums
 row = g[r] 
 for i in xrange(len(row)):
  sums[i] = max(prevSums[i] + row[i],prevSums[i+1] + row[i])
print sums[0]

Problem #19, how many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?, can be solved in a very clever way with one line of arithmetic. Alas, I did not arrive at that solution. In Python using some of the built calendar functions, also results in a one line solution. Again, I did not arrive at that one either (but at least now am familiar with the calendar module).

Instead, I wrote a program as usual, based on a literal interpretation of the rules of the Gregorian calendar.

daysInMonth = [31,28,31,30,31,30,31,31,30,31,30,31]
daysInMonthLeap = [31,29,31,30,31,30,31,31,30,31,30,31]
  
# go through year 1900 to set firstDay properly for 1901
firstDay = 1 # Monday
for m in daysInMonth:
 firstDay += m
 firstDay = firstDay % 7

sun1stMonths = 0 
for y in xrange(1901,2001):
 dim = daysInMonth
 if y % 4 == 0:
  dim = daysInMonthLeap
 for m in dim:
  if firstDay % 7 == 0: # Sunday
   sun1stMonths += 1 
  firstDay += m 
  firstDay = firstDay % 7
print sun1stMonths

Problem #20, find the sum of the digits in the number 100!, is a no brainer:

def factorial(n):
 if n == 1:
  return 1
 else:
  return n * factorial(n-1)

print sum(map(int,str(factorial(100))))