## Archive for June 26th, 2009

### Problem 13 – Too Easy?

June 26, 2009

I’m a little confused about problem 13. I wanted to come up with some nice way to find the first (leftmost) 10 digits of the sum. The only way I came up with was to actually do the sum though. I thought maybe that coding this up would point out something I hadn’t thought about that made the problem more difficult. Like maybe the 50 digit numbers were too big to store as integer values, or the sum was, or something. So I just coded up the naive solution to see what would happen:

```from __future__ import with_statement

import sys, time

""" Input a file, reading into a list of integers """
ret = []
with open(filename) as file:
for line in file:
ret.append(int(line))
return ret

def solve(nums):
""" The leading 10 digits of the sum of the numbers in the list nums """
return str(sum(nums))[0:10] # loving this syntax

if __name__ == "__main__":
t = time.time()
t = time.time() - t
```

I ran that, and it spit out an answer in about 0.0004 seconds.

So, am I missing something from this exercise, or is it that easy? Is there a more clever way to do it anyway?

### Problem 14 – A Class

June 26, 2009

I was thinking a little bit more about my solutions to problem 14, and thinking that passing around the “mem” dictionary wasn’t particularly efficient. I didn’t want to make it a global variable, because I have a sort of stigma against those. I think, maybe, in Python it’s a stigma I should/could get over, because the file named prob14_v3.py that contains my script is actually a module (Python does that bit for me, no extra work on my part) that gets its own namespace without any extra work from me. But I could be wrong about that.

So, anyway, I thought maybe I’d try wrapping up my code into a class, and making the dictionary an attribute of that class. Here’s what I coded up:

```class ProblemSolver:
def __init__(self, bound = 1000000):
self.mem = {1:1}
self.bound = bound

def lenseq(self, n):
if(n in self.mem):
return self.mem[n]
suc = n%2 and 3*n+1 or n//2
self.lenseq(suc)
self.mem[n] = self.mem[suc] + 1
return self.mem[n]

def solve(self):
retn,retl = 0,0
for n in xrange(1, self.bound):
l = self.lenseq(n)
if(l > retl):
retn,retl = n,l
return (retn,retl)

if __name__ == "__main__":
solver = ProblemSolver(int(sys.argv[1]))
print solver.solve()
```

I’ve not done much in the way of rigorous performance testing, comparing this script with my other solution from yesterday, or with one that just uses a global variable to store the dictionary. A few quick tests indicate that they take approximately the same time to run.