Project Euler Problem 1 - In Python

Project Euler

Project Euler is a web site with hundreds of problems for you to tackle however you want to solve them. Some of them, if you are sufficiently adroit mathematically, can be solved on the back of an envelope. Most of them clearly need a piece of software to grind through the calculations. You can use whatever programming language you prefer. the site asks only for the answer. Each problem yields a numeric answer. If you provide the correct answer, the site credits you for solving the problem and grants you access to a discussion page. The discussions are mostly people bragging how they solved the problem. The bragging isn't anything important, but it can be useful to look at other people's approaches to see other ways of looking at the problem that perhaps hadn't occurred to you.

The one "guideline" is that a good solution should need no more than a minute of time on your computer. If your solution needs way more time than that, then you should look for a better solution.

Tell Ya What I'm Gonna Do...

I'm going to show you how to solve some of the project Euler problems using the Python 3 programming language. Instead of having you install Python 3 on your computer, I'll be using the "Python in the cloud" facilities of pythonanywhere.com. You can sign up for a free account of your own there. For small programs like ours, they offer their service for free. If you use their site to build something that becomes enormously popular (say, the next "Farmville" game), you'll be needing to pay for their services, but we're far, far from crossing that line between trivial computing load and significant computing burden.

It'd be useful if you figure out a good way to prepare your Python programs in a file, but you can start with notepad or whatever simple editor you are most comfortable with. If you tell us in the comments on this blogpost what editor or IDE ("Integrated Development Environment") you prefer, it may influence whether I write future articles addressing that editor or IDE.

Project Euler Problem 1

The first problem on project Euler is one that calls for very little code. I'll tell you that I approached the problem as a computer programmer, but in the discussion page for the problem there were people who knew how to compute sums of a series using a simple formula and they were able to readily solve problem 1 using only pencil and paper. That's just proof that although I've worked with mathematicians, I'm a software guy, not a mathematician.

The crux of problem 1 is: Find the sum of all the multiples of 3 or 5 below 1000.

The example given makes clear that they are only asking us to consider positive integers. So no need to worry about negative 3 and negative 5 and so on. ("If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.").

Spoiler Alert.

I'm going to talk here about how I solved the problem. If you want to solve the problem on your own, stop reading here and go solve that problem. Feel free to come back later and tell us in comments how your solution is better than mine. Better in what sense?

Solving Problem 1 in Python

At this point, I am tempted to show you the small program that I used to solve the problem, but that is so small a program that you'd probably glance at it and walk away grumbling "nothing to learn here", so I've decided to creep up on the solution a bit more slowly. I hope you pick up some comfort with Python programming along the way.

The General Shape of the Program.

Generally, the way to write a program is to start out with a rough idea of what the program should look like. You can write this down in "pseudo-code" - a mixture of your native language and whatever bits of programming language structure you are comfortable to stir in. One of the delights of Python is that Python code looks a lot like pseudo-code, so if you nudge your pseudo-code into being real Python code, you can test out your pseudo-code by running the program. When it works, perhaps you are done, but if your actual target language isn't supposed to be Python, then you have a working prototype that you need to re-code into your intended target language (Perhaps C or C++ or even some assembler language). It is worth noting that in the real world, often a manager faced with a working prototype that works well enough, will suddenly decide that a Python implementation is plenty good enough to declare the problem solved, even if its the first instance of Python code admitted into "production" use in that shop.

This program is going to need an iteration (loop) to consider all the natural numbers less than 1000. And inside that loop it is going to need a conditional statement (if statement) to select the numbers that are multiples of 3 or of 5 (which for whatever reason are the numbers that this problem considers to be interesting). And for the numbers that are multiples of 3 or 5, we'll need a little arithmetic to accumulate the sum of the selected numbers.

There's more than one way to do it. For example, we could loop through all the non-negative integers <1000 and build up a list of the numbers that meet the criteria of being "interesting". Then we could take the sum of that list to get the desired answer. But we have no further use for the list in this problem, so I assert it is simpler to just accumulate the sum as we go.

Another approach would be to generate the multiples of 3 and to generate the multiples of 5 that are less then 1000, and then tally up the generated lists, but you'd need to be careful not to include any numbers twice. Some numbers (e.g. 15) are multiples of both 3 and of 5, but only should get added into the sum for this problem once, so I assert it is simpler to just consider each of the candidate numbers and accumulate the ones that meet the criteria for being interesting.

Got another plausible shape for the solution this problem?

So, I'm going to stick with my initial proposal which in Python-like pseudo-code looks like this:

sum=0
for num in numbers 1 thru 999:
    if num is "interesting":
       sum += num
print(sum)

Note that in Python, indentation is used to delineate the blocks of code. My Python-like pseudo-code follows that same convention. Thus the body of the loop statement is indented under the "for" that introduces the loop. The body of the "then" clause that is made conditional by the "if" statement is indented inside the "if". Since the "if" is inside the "for" loop, the accumulation of the sum is doubly indented. The initialization of sum to zero is outside of the "for" loop so it isn't indented at all. The "print" statement is also not indented. We don't want to print the partial sum on each iteration of the loop, so it is important not to indent that final "print". But maybe when you are debugging, a print statement inside the loop would be a helpful addition. That would be done by adding another print statement and indenting it so it is inside the loop. You might want to include a comment on your debugging code so you can trim the debugging code out when your program is in good working order.

The "sum += num" statement is Python short-hand for "sum = sum + num", since accumulating totals is such a frequently needed operation.

I hope you've noticed that the pseudo-code is not quite working python, so we aren't done yet. The most glaring magic is how do we really decide if a given number, which we've named "num", is "interesting"?

How to test if a number is a multiple of some value

So we need to consider how to test a number to see if it is a multiple of 3 (or of whatever number we want to test to see if it is a multiple of). Python has a modulo operator (%) that is documented here. x % y is how you ask Python to compute the remainder of dividing the number stored in x by the number stored in y. So all you need to realize is that if x is a multiple of y, that the remainder will be 0, and if x is not a multiple of y, then the remainder will not be zero.

So if we have a number to test named num, then we can test if num is a multiple of 3 by using this Python code:

num % 3 == 0

The result of that test expression is a True or False value (True if the remainder is 0. False if the remainder is not 0). But we want to know if the number is divisible by 3 or is divisible by 5. Happily, Python has an "or" operator that will let us combine 2 True/False values in exactly the way we need.

Here's a copy/paste of my PC anywhere session where I tried this out:

>>> num=27
>>> num % 3
0
>>> num % 3 == 0
True
>>> num % 5
2
>>> num % 5 == 0
False
>>> num % 3 == 0 or num % 5 == 0
True

As you can see, the Python rules for operator precedence did exactly the right thing for us here, but I find that long expression a bit hard to read, so I added some un-necessary parentheses to make it easier for a human to parse.

>>> (num % 3 == 0) or (num % 5 == 0)
True

How to conjure up a list of numbers?

In many programming languages, Fortran for instance, the way you conjure up a sequence of numbers is you have a variable to serve as a counter. You initialize the counter to a starting value, then you increment the counter to get the next value and you need a test to decide when you've gone as far as you want to go. If you've programmed in C, that's what a "for" loop in C does. But there's a more Pythonic way to do this in Python, so please take care not to write Fortran (or C) code in Python syntax. A Python "for" loop looks like

for x in list:
    do something with x

Where x is an arbitrary variable name that takes on each of the values in the list and the body of the loop (which I've represented as "do something with x") processes each of the values as x is stepped through the list.

If you want to read more about looping in Python, especially if you are comfortable with looping in other languages, I strongly recommend Ned Batchelder's blog post "Loop like a native".

Not only does Python have a statement to consider each of the values in a list of values. It also has a built-in generator of a list of values. In Python 2, "range" is a built-in function to return a list of integers, but such a list takes up space. So "xrange" was introduced to return a generator that'll provide the desired sequence of integer values on demand without ever actually creating the list as a whole in memory. xrange worked well enough and explaining the distinction between range and xrange was ugly enough that in Python 3, xrange became range and you only need to know its a generator if you're interested in the details of how stuff works. So just say range(1000) to conceptually whip a list of numbers 0 through 999.

So now our pseudo-code has morphed into runnable Python code:

sum=0
for num in range(1000):
    if (num % 3)==0 or (num % 5) == 0:
       sum += num

print(sum)

And we're done, except for running the code to get the answer. I'll not reveal the numeric answer here, so please learn how to run this yourself.

Mystified? Please tell me if I've confused you so I can polish things up before my next blog post.

Python Generators

Background

Back in May, 2013, I posted "Cheap, but not Free, Modular Code has a Price". In that blog article I compared the performance of my solution of Project Euler problem 14 to the performance of Nico Ekkart's solution of that same problem. As I explained in that article last May, Project Euler's guidance on performance is that a solution should be able to complete on a typical PC in less than a minute. My initial solution ran well over a minute and I applied a cache to speed my program up. Once I'd gotten it down below the one minute limit, I had concluded "good enough" and went on to other problems. But Nico honed his solution a little tighter and outperformed my program by a factor of 4.

Looks to me that we had basically the same solution, but his was more of an in-line implementation, while I used a Python generator to produce the sequences of numbers the processing of which is the heart of problem 14. I concluded that the Python structuring facilities like generators do add overhead but I opined that the added clarity of packaging the sequence generation as a "generator" made the overhead worthwhile. Nico's code for his cache was so little code that I didn't really defend my use of a Python "class" for my cache implementation. Some further experiments with the code to determine how much of my extra overhead came from the generator vs. how much came from my cache implementation might be interesting. I've posted the source code and invite you to experiment and share your findings.

But that isn't what I came here to talk about today

This blog post today is aimed at expanding your knowledge of Python Generators and share with you a neat trick that I've recently learned: a generator of dictionaries.

Python Dictionaries

Back in January, 2013, I posted "Dictionary Implementation". In that article I pointed to where the Udacity CS101 MOOC introduces Python dictionaries and pointed to further places to look to learn how Python implements dictionaries, hash tables. If you aren't comfortable with Python's notion of a dictionary, I'll sum it up as an easy to use collection of name-value pairs, much like an array is an easy to use collection of subscript-value pairs.

Given an integer value as a subscript into an array, you can easily ask for the value associated with that subscript. (In Python such an array is called a "list". But if you have a dictionary of name-value pairs, in Python it is easy to ask for the value associated with a name. e.g. What value is associated with "eggplant", where "eggplant" in this example is a possible "name" entry in the dictionary. If this is all still mysterious to you, my suggestion is to dig for more info on the web. Google search is your friend. A Google search for:

python dictionary

turned up more than 5,000,000 web pages today and Google looks to have done a decent job of sorting the most helpful ones to the front of the search results.

Or perhaps you should work your way through Udacity CS101 to learn this concept of dictionaries and more.

Python Generators

But as I already said, the topic of my blog post today is Python Generators. Rather than take the time and trouble to create a fresh new tutorial about Python Generators, I'll pause here to provide a link to an article from April 2013 from Jeff Knupp: "Improve your Python: 'Yield' and Generators Explained". That article resonated with me as written in an easy to understand way. It's about 19 screens long, so it isn't a quick read, but you can get back to Facebook and YouTube later.

Knupp's article should certainly get you to the point of being comfortable with my Project Euler problem 14 generator. My generator is very vanilla, just conjuring up a sequence of numbers. The one tricky aspect is my program often doesn't pursue the sequence to the end, but sometimes decides it needs to see a new sequence. I was a little nervous when I did it that way, but now understand that Python doesn't mind dangling generators like that, and even should know enough to be able to garbage collect their saved state, if memory gets tight and it is clear that there's no way the program could get back into that old sequence. Powerful stuff and a feature unlike anything available available in C, Fortran, Basic or Cobol to name 4 examples of older more traditional programming languages.

But Wait! There's more!

If you've read this far but are yawning, thinking that hardly ever do you, yourself, have occasion to use complex logic to generate a sequence of numbers in the programs that you write, well hang on and see what else generators are good for.

Igor Vasilcovsky recently pointed out to me an interesting tutorial from David Beazley about generators. The meat is the slide deck under the presentation link on that page. Even with 2 slides to a page, that slide set runs to 79 pages so it probably is too much to absorb in one sitting. So try to work through it in several sessions. Here's my summary of the key elements I think you should get from wading through that presentation:

1. A generator can return any kind of Python object. That is, it isn't limited to returning the numbers of a sequence. If you paid close attention to my Pythonic Python from July, 2013, you may remember that one of the points I made there was that Python functions can return large complex objects, not limited to just a number or just a pointer. Better still, Python takes care of the book keeping to automatically garbage collect the returned object if you are no longer using it.

   Beazley has examples with a generator returning strings (lines from log files), and then takes an unexpected turn to have the generator parse the strings into values and stash the values into a dictionary with a name for each value and then return the resulting dictionary as the generator's output. (A dictionary per line of the log file!) My initial reaction to that was to be horrified at the overhead, but if you think about it, looking up a name in a dictionary is quite central to Python's run time modus operandi, so dictionary objects being generated is perhaps more general than generating some more specific Python class object, and looking up values by name is pretty much the same as using a name of a member of a class object to get to a value in the class object. So given that Python is able to get decent performance from run-time interpretive execution, generating dictionaries is a lot more sensible then my initial gut reaction took it to be.

2. A generator is just Python software so it can do anything that any Python software might want to do to provide the next value in the sequence. It can compute the next value using a formula, or it could access a file to learn the next value. It is even able to make use of another generator to get an input sequence that it manipulates and passes along. So generators can be chained together into long pipelines.
3. If your program is basically about iterative processing of a series of stuff, then chaining together pipelines of generators can fundamentally shape a clean structure for your program and with a little practice you'll soon have a collection of useful reusable filters that you can use to construct future programs that you haven't even thought of yet. Share them with your friends. If you own the code, consider making it (and it's documentation) GPL licensed and freely shared on Github or some other such public place.

I'm seeing hints on the Internet that future Python releases will have even more use of generators. e.g. standard approaches built in to the language to process streams of events. e.g. Brett Cannon's 40 minute talk: "Python 3.3: Trust me, it is better than 2.7". He foreshadows a Guido Van Rossum talk about Python 3.4 scheduled for that same conference. If you can find a link to a video of Guido's talk about 3.4 and new roles for generators, please share it in the comments section here.

Cheap, but not free. Modular code has a price...

Introduction and Spoiler Alert

Recently, Nico Ekkart asked on the Google+ Python Community for suggestions on how to speed up his Python implementation of Project Euler Project 14. I remembered my initial implementation of Project 14 had taken way more than the allowed minute of processing on my laptop and that I'd souped it up by adding a cache to get the run time down. I dusted off the files and compared the performance to Nico's. Sadly, his outperformed mine.

To see the requirements for Project 14, see: http://projecteuler.net/problem=14.

Spoiler alert: If you would rather solve Problem 14 on your own, don't follow the links below. In fact, you should read no further in this article, lest your thoughts be polluted with prior art. To see Nico's question and the associated discussion thread, see: https://plus.google.com/113176807122785773311/posts/MPA7LmLZdVW.

The source code for Nico's implementation is here: https://gist.github.com/rdrewd/7654766.

As I explained in Creeping up on OOP in Python - Part 1, all my Project Euler programs have a wrapper main program to time and report the timing of the run and to print the answer. The source code for that wrapper script is here: https://gist.github.com/rdrewd/7654590.

The source code for my initial uncached implementation is here: https://gist.github.com/rdrewd/7654699.

The source code for my cached implementation is here: https://gist.github.com/rdrewd/7654742.

I ran each of these programs using Cygwin Python 2.7.3. The log of the runs is here: https://gist.github.com/rdrewd/7654787 and includes one additional run. The difference was that I tweeked the cache size up from 100,000 to 1,000,000 entries to see if it would improve my run time. It did, but my run time still was behind that of Nico's code.

So what's the difference between my code and Nico's code? Well, a crucial non-difference is that both my cached version and Nico's code use a cache ("memoization") to save having to recalculate results that are already known. Far as I can see, a crucial difference is that I used a Python generator function to run through the specified sequence, and I used a simple class to do the caching. Nico's code is more in-line, mostly a simple while loop to compute the sequences, so there are many fewer calls going on. Nico's code uses one statement to do the caching where I used a simple object to implement the stashing of values in to the cache with a "method" (stash) and another method (value) to check whether a value is already in the cache On the one hand, I like Python's structuring provisions for generating sequences, but on the other hand, given the millions of times this program is invoking the next step in the sequence, the overhead does mound up to noticeable amounts of CPU time. I was also worried that perhaps I didn't have enough real memory to be able to cache all million values, so my cache had a bound on how much it'd cache. Nico's code just trusted in the virtual memory to allow a very large dictionary.

Summary of run times:

Nico's code	6.645 CPU sec
Drew's nocache	177.638 CPU sec
Drew's cache	28.501 CPU sec
Drew's big cache	16.863 CPU sec

Conclusion

The modular control structures in Python are remarkably efficient, but they are not entirely free of overhead. I stopped tuning after I got the run time below the requirement of "no more than a minute", but clearly I was off the pace by a factor of 4 or so. Was the structure of my functions and objects worth that cost? Well, for having met the requirements, I think so. I have to concede that Nico's code was so short that I do find it hard to argue that my function def's and Cache class added any significant amount of clarity to the code. As for Nico's question of how to make his code run faster, the stackoverflow pointers in the original comment thread may help get his run time down even further. Memoization is the big performance win, and thanks to Python dictionary data type, that is darn easy to implement.

Revised 11/26/2013 - My employer blocks pastebin.com, so to facilitate sharing with my co-workers, I've copied the pastebin snippets to gist.github.com and updated the links here accordingly.

Creeping up on OOP in Python - Part 2.

Introduction to part 2 and Spoiler alert

In my previous blog post, I showed my first solution to Project Euler problem 22. For those of you who want to solve the problem on your own, I cautioned that my posting was a "spoiler". In today's article, part 2, I refine the code to use a Python object of my own. I believe the result is better code, but again, a "spoiler" if you'd rather develop your own independent implementation. Sorry, but if you want to remain untarnished by my prior art, please don't read any futher in this article and do not follow any of the links to the source code under discussion.

A classier solution to Problem 22

Well this has been fun! My improved version of problem22 is here: http://pastebin.com/agBBSQ9Z

In the previous version of the code, you may remember I had main() initialize valuedict so the value dictionary could be passed in to the namescorer routine. As I mentioned in part 1, I wasn't entirely happy with that arrangment as the valuedict was clearly an internal implementation detail of the namescorer routine. So, why should main() even know about that stuff?

The first big change was to add a NameScorer class. When you instantiate it, you tell it the alphabet of symbols that the NameScorer object will be asked to process. The first symbol is counted as value 1, the 2nd symbol is given a value of 2, etc. The __init__ routine of NameScorer builds the valuedict, which when you come down to it, is just an implementation detail of how we compute the score for a name. Assuming ASCII and using the ord(c)-ord('A') approach is another way to do it. The new approach removes the valuedict from main(). That looked out of place in main() and I either had to make it global (which is considered bad form) or do what my previous version did: pass the valuedict in to the nameScore routine each time it was called!. Happy to be rid of that.

What I learned as I wrote my first class is that a self. qualifier is very important when trying to refer to a symbol that is part of the instance of the class. Multiple times the tests aborted with a message that there's no such global symbol as valdict. I'd have to correct the code to say self.valdict and hit my forehead while exclaiming Doh! I kind of wish for a short cut like import has so you don't have to repeatedly qualify a symbol reference with the module name.

The next big change didn't actually survive to the final version. I had "for" loops that iterated over the alphabet or the name list, but I also had a counter that had to tick along with each iteration. That meant an initialization statement before the "for" and an incrementing statement in the body of the loop. There isn't wonderful documentation of the syntax in the Python books I have here, but you can say

     for (i, name) in

and thus have both the names and the counter automatically handled by the "for". That left almost nothing inside the "for" and it was then that I realized, the initialization of the value dictionary, could be handled by a "list comprehension" generating the tuples that then just become an argument to dict(). And the totaling of the weighted name scores in main could be done by invoking

    sum(i*ns.score(name) for (i, name) in
        zip(range(1,len(nameList)+1), namelist))

Best explanation of this that I've since found is Ned Batchelder's blog post "Loop like a native".

The books I have here say that current Python implementations implement list comprehensions like that by actually generating the list of tuples and iterating over that. Apparently the intent is that some day the tuples will be generated as needed. But heck. Memory is plentiful.

zip by the way is a function that given 2 lists, generates tuples by pairing together the i-th element in one list with the i-th element in the other list. It only generates as many tuples as the shorter of the 2 lists, but both my lists were the same length.

Somewhat invisible in the code is that while making these changes, I learned a few more basic tricks with the git version control system. I checked in yesterday's problem22.py to git. That version was implicitly the master branch.

Then I created an experimental branch (yeah, this is overkill for a one person operation, but remember I'm doing this to learn). Each time I had a working change to problem22.py, I'd check it into the experimental branch. My last incremental change was in recognition of the ease of getting old versions thanks to git and frequent well commented logs of what changed. So I decided that my old habit of leaving test prints, etc. embedded into the code, albeit commented out, was just making it harder to read the program. So I weeded that commented-out scaffolding out of the final version.

Premature optimization is a bad idea

One disapointment was I was hoping the list comprehensions would get interpreted faster than the for loops, albeit at the price of using more memory. But it runs no faster, maybe even 10ms slower, but that's in the noise range, so more tests would be needed to pin down what is actually happening. I did accidently give myself one clue. I added print statements to show the type of the grammar variable and of the grammar.parsefile(...) result that I had to convert to a vanilla list before I could sort the list. I was lazy, so rather than tear apart the return(list(grammar.parsefile(...))) so I'd have an intermediate result that I could pass to type() to see what it was, I left the return statement alone and preceded it with a print statement that changed list(...) to type(...). That meant I parsed the file twice. The total CPU time nearly doubled, so without resorting to grand profiling tools (which I confess I don't yet know anyhow - and profiling a 320ms run is not such a great thing to do!), but we have some evidence that the vast majority of the run time is going into pyparsing as it reads and parses the 5000 or so names in the input file. So hoping that tweeking the other loops and argument passing would improve CPU time was naive on my part. Oops.

How many times do I have to hear measure first before you try to optimize, before it really sinks into my brain?

Oh, and the type of the grammar is "pyparsing.And", which agrees with the top level of delimited list generating an expression using the overloaded + operator. I'm quite certain that the type of "grammar" is a subclass of parser element, so a grander grammer could be built up with this as just one part of it, Mercifully, I didn't need anything grander.

The type of grammar.parseFile(...) is 'pyparsing.ParseResults". I didn't dig deeper to see why the thing looks like a list, but won't sort. It occurs to me that sort depends heavily on the comparison operators and presumably copy operators to swap values around. Perhaps pyparsing overloads those operators for its ParseResults type. If and when future problems cause me to revisit pyparsing, I'll take a closer look.

The entire listing now handily fits on a single page.

Metrics

I ran the file through sloccount and it says 15 non-comment, non-blank lines of source code. It also estimated that creating 15 lines of Python code like this would take about 0.65 months, which I figure is 2-3 weeks, which is scarily close to right. But if I wasn't taking the time to learn a new language and its modules and git, all at the same time, I'd like to believe I could knock out 15 lines of code in much less time.

(Of course, working on my own, my time is not getting sapped into Affirmative Action meetings, design reviews, questions from the peanut gallery and all those other things that motivated me to work at home when I was doing real design or real coding. So maybe in a real corporate environment, that 2-3 week estimate still would apply, even for a seasoned Pythonista, which I don't claim to be yet!)

My one regret is that I'm still not doing test-driven-development.

Python has the annoying property of accepting just about anything at "compile-time" and not telling you of problems until you drive execution into the problem code at runtime. That makes it super important to have excellent test cases to drive the execution into as many nooks and crannies of the code as you reasonably can manage to do.

My programs don't have built-in self-testing capability to watch out for any regressions as changes are made. I'll have to force myself to try that stuff in some future problems. At this point, I'm not even sure where the test code would go. A separate file in place of "__main__"? And, just to keep life interesting, Python has multiple unit-test modules available, so picking one intelligently will take some work. One of the unit-test packages is called "nose". If I pick that one will you go "Ewww!"?

Creeping up on OOP in Python - Part 1

Background and Spoiler Alert

Project Euler is a challenge set of problems, hundreds of them, that you probably need a program to solve each problem. You are allowed to write the program in any programming language of your choice. Some of the problems require reading an input which is given in a file linked to the problem description page. All of the programs produce an answer - a single numeric output (sometimes the answer is a very big number with many digits in it). The site poses the problems and you get to tell the site the number that is the answer. The site provides no guidance beyond feedback as to whether your answer is right or wrong until you give it the right answer. A right answer unlocks access to a bulletin board where you can share how you solved the problem. Lots of bragging there from folks about how few lines of code they used or how real mathematical insight made the program so much easier than it appeared to be at first blush.

My background is software development. I've worked with mathematicians, but make no claim to being a mathematician myself. So solutions that are founded on real mathematical insight are not the sorts of things to expect from me. Sometimes, armed with the mathematical insight explained on the bulletin board, I've found it worthwhile to revisit my solution to make my code better. Sometimes I revisit my code with a critical eye just to make it better to satisfy myself. I do miss having talented co-workers who can review code and make suggestions at the lunch table. But as a retiree, it falls on me to be my own reviewer. Fortunately, I have always had strong opinions of the quality of code and a thick skin, so I can provide my own harsh comments to myself and get some cleaner code out of the introspection.

This series of articles is going to look at Problem 22 of Project Euler and is, quite frankly, a spoiler. If you'd rather do it yourself without seeing somebody else's solution, do not open any of the links to the code samples here, and do not read the rest of this blog post if you consider description of the code of a solution to be off-limits too. Before posting this article, I Googled for:

project euler problem 22 solution

and can see I'm by no means the only person breaking the wall and revealing a solution on the Web.

My motivation for tackling problems in Project Euler was to learn the Python programming language. Shortly before my retirement, David James, then of the Bell Labs statistics department of the Murray Hill Math research center, had suggested to me that Python looked like a great programming language to learn. I had no reason to doubt that, but was knee deep in projects in other languages, so I didn't have time just then to stop and learn something entirely new to me. Now that I'm retired, I have time for such adventures. Sadly, except for whatever value there is in telling the tales of such adventures here around the campfire, it isn't exactly clear what good will come from my learning yet-another-programming-language. If nothing else, it has certainly shown to me that David James has an eye for value in programming languages. His recommendation of Python appears to have been well founded indeed. I'm still a long way from becoming an expert in Python programming, but I find it is certainly a pleasant programming language to use to solve problems. Python code is readable (unlike, say, Perl or APL) and tends to be quite compact (unlike Java). The language supports a broad range of programming styles and brings more possibilities for control structures than any language I've worked in except maybe for assembler language, where the language brings no real structure to the program and anything goes that you can dream up - but document your assembler code well so the folks who come later can figure out what you did!

Old School: Structured Programming

My roots are in "structured programming" from the days when "Goto considered harmful" was still considered to be a controversial position. Happily, I've long since accepted the truth of that position and so don't miss at all that Python has no goto statement.

Quite some time ago, I laid out a list of things I believed I needed to master to consider myself a Python expert. Perhaps surprisingly, the language itself is only a small part of the things to learn. I blogged my list in an article that started out to be about "literate programming", but that mutated as I created that article into my Python study guide.

So, my solution of Project Euler problem 22 started out as a small, reasonably clean structured program.

The problem statement for the problem is here: http://projecteuler.net/problem=22, complete with a link to the names.txt file that the program is to process.

By the way, I've been working with Python 2.7. Availability of libraries for Python 3 has been my reason for hanging back with Python 2. As time goes by, that presumably will become less and less of a good reason.

Wrapper Main Program

Since all of the Project Euler problems produce a single numeric answer, I base each of my Project Euler programs on a wrapper main routine that invokes the code for the problem, expecting the called code to return a value. The wrapper main program has a print statement to print the returned value and infrastructure to time the runtime for the called routine and print a report of the runtime. My code for the wrapper main routine can be found here: http://pastebin.com/trk7E1n9. The wrapper main routine expects a single argument from the command line to tell it where the actual program code is located. The wrapper assumes that the program to be run is in the file named by the command line argument and that the name of the program to be invoked from that file is main().

I've not been entirely delighted with my wrapper main program. It reports elapsed time for the test, not CPU time. And the time routines from the library seem rather coarse in their granularity, but Project Euler's guidance on runtimes is only that the data for these problems shouldn't take more than a minute to process on a typical PC or you should rethink your algorithm. My timer code may be a little crude, but it can certainly show whether I've met that guideline.

I've written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

If you really want to think about measuring time in your program, you ought to study this page: http://stackoverflow.com/questions/85451/python-time-clock-vs-time-time-accuracy

The Rest of the Problem Solution

My first-version code for problem 22 is here: http://pastebin.com/SgZ7y54b

There are commented-out print statements in the file that I used when I was doing my testing of the code.

One other tool that I learned to work with as part of my study of Python is the source-code-control tool git as provided by github. As I got used to the power of git, I found that the code really reads better if you remove the debugging print statements, not merely comment them out. But the edition of problem22.py that I'm showing is from earlier in the process than my reaching that realization.

The description of the input file for Problem 22 says the input is a sequence of names, each enclosed in double-quotes and separated from each other by commas. Now Python is great at that kind of parsing of input, but I dis-like writing and debugging the fiddly code needed to carefully parse an input file, particularly if the parser is to make reasonable recovery from errors in the input's punctuation. So, I invoked the computer science principle that "there's no problem so big or so complicated that it can't be run away from". My escape hatch was to apply the pyparsing library module. pyparsing is, in my opinion, very Pythonic in its approach. The library allows you to define a grammar in terms of Python objects and then apply that grammar against your input. There are library alternatives that may give better performance, but I found pyparsing to be reasonably well documented and a joy to apply to the straight-forward problem at hand. I ended up having to write delightfully little code to solve the problem. (I concede that later, as I worked through CS101 in Udacity.com that I came to understand that Python may be good enough at parsing input strings that perhaps I should have just gritted my teeth and written the straight-forward code to parse the input file. But I do suspect that familiarity with pyparsing will be useful to me in the future if I ever am faced with parsing a more complex input structure.

This pyparsing library was my first serious encounter with the objected-oriented-programming (OOP) aspects of the Python language. Python is gentle in providing for such modern stuff, yet not forcing you to really grok the feature before letting you write reasonable software in Python.

The Devil is in the Details

Python is a relatively small programming language. As I mentioned, I strongly believe that the Python language itself is only a small part of what I believe I have to learn to be a Python expert. Nevertheless, there were still details of the language that I sort of stumbled into understanding as I worked this problem. I kept notes that I'll share with you here...

The ParseInput routine effectively has only 4 lines of code:

    def ParseInput(filename):
         from pyparsing import (delimitedList, QuotedString)
         grammar=delimitedList(QuotedString('""))
         return(list(grammar.parsefile(filename, parseAll=True)))

The define statement is the boilerplate to define a function. The from import () statement is where I import the pyparsing module from the library. My first try was to say:

     from pyparsing import *

which I expected would import all the "public" names from the module into ParseInput's name space. That shortcut is frowned upon as a change in the library's module could bring a name conflict into my function, but I figured it would save me the trouble of having to name every little thing I wanted to try. To my surprise, the import * was rejected as only usable at a module level. I think its saying that if I'm writing my own module, I can import * all the names in another module, but if I'm just inside a function, I have to be more specific. Rats, shortcut denied. Next try I said:

     from pyparsing import (delimitedList, QuotedString, parseFile)

but it objected that I couldn't import parseFile like that. delimitedList and QuotedString are classes defined in the pyparsing module. They are subclasses of the ParseElement class. The advantage of importing the names into my function are that I can refer to the names without having to qualify the name with the pyparsing module name. pyparsing.delimitedList is kind of long winded in composing a grammar. parseFile though is different. It's a method (invocable function attribute) of the grammar. I'd have to dig into the source code to be sure I'm saying this right, but I think that the grammar built from the parserElements is itself a parserElement, so I believe parseFile and its brother, parseString, are methods that can be invoked for a parserElement.

In the 3rd line of code, I creatively name my grammar, "grammar". delimitedList defaults to a list of comma separated items. The grammar for each item is the argument you pass to delimitedList, so I passed in QuotedString('"'). The argument to Quoted String is the quote character it is to look for. Default is that it strips out the quotes and just returns the stuff enclosed in the quotes. My first try I didn't know that QuotedString required an argument, so I coded it as QuotedString() and got a message about a class being invoked with one argument where it expected two.

The object-oriented stuff in Python always implies an argument of "self", the object on which the method is being invoked. So, my missing argument was the missing "2nd" argument.

I mistakenly reasoned that maybe I should just pass in QuotedString without the (). That got me an obscure (to me) message that I can't "combine type 'type' with a ParserElement". I eventually figured out what it meant. QuotedString is a subclass of Token and Token is a subclass of ParserElement, but QuotedString with no arguments is a class definition, a type. That is type(QuotedString) is 'type'. I tried

     qs=QuotedString('"')

and got type(qs) is "QuotedString" and isinstance(qs, ParserElement) was true. Whew! Good thing this is all OpenSource, as I don't think I'd have made much progress at all if I couldn't follow Obiwan's advice and "Use the source, Luke".

delimitedList internally uses + to construct the grammar for what it is looking for. (pretty straight forward. It wants to find a match to the argument grammar, followed by a comma, which it suppresses [gobbles up], followed by another match to the argument grammar OR it will settle for a match to the argument grammar, not followed by the delimiter [to cover the last item in the list. No need for a trailing comma after the last item]. I'm oversimplifying as the list can have an arbitrary number of comma separated items in it, and optionally, you can name an alternative delimiter instead of sticking with the comma).

parserElement redefines the + operator to make it into an "and" concatenation of parserElements, but it didn't want to concatenate a type to a parserElement. Giving an argument to QuotedString causes an instantiation of the class so I have an object that is an instance of a ParserElement and so is acceptable to the overloaded + operator to concatenate that object to another ParserElement object.

The 4th line of code started out as:

     return(grammer.parseFile(filename, parseAll=True)

(The parseAll=True tells parseFile to throw an exception if the grammar doesn't successfully parse the whole of the input file. Default is it parses as far as the grammar will match in the file and leaves things such that another grammar can be applied next.

That return statement actually seemed to work, but the returned value wouldn't re-order when I invoked the sort method that is associated with lists. I used the type function to see what the type of the returned value was. It was a pyparsing.<something> type, which I'm guessing is a subclass of the built-in list type. It had no objection to my invoking a sort method on it, but it didn't sort the list. Solution was to explicitly convert the returned value to a plain old list using the list() function which you'll now find in that 4th line of code.

So 4 lines of code written, and I'm sure glad no one is measuring my lines of code per hour productivity.

nameScore Routine

The next function is nameScore. 5 lines of code that given a name computes a score for it. A=1, B=2, C=3, .... Score is the sum of the values for the characters in the name. Straight forward iteration over list(name). List knows how to bust a string up into the sequence of characters that I want to process one by one.

valuedict is a nifty Pythonic feature. Basically its a hash table. I wasn't quite sure where to define it, so I just put the initialization into main() and passed the valuedict as an argument to nameScore. Maybe if I was more object-oriented in my thinking, I'd have made nameScore into some kind of a class with an __init__ function that built that valuedict that stays with the nameScore object. In Part 2 of this article I'll go back and try it that way just to see what it looks like.

The names.txt file for this problem is fairly massive - 46KB containing 5000 names all on one very long line of text. For debugging, I constructed a smalllist.txt file that had only a few names in it. smalllist.txt is a small file in the syntax of the file given with the program. The real file had some 5000 names in it, all on one line. Looking at the discussion board for the problem, a disappointing number of people pre-processed the names.txt file (e.g. using Excel) to pull the words apart and alphabetize them. Some even left the words with the double quotes still there, just giving " a zero value in scoring the names.

main() Routine

That brings us to the main() routine. Line 30 runs ParseInput on the input file to get the list of names into nameList. Line 36 applies the sort method of lists to put nameList into alphabetical order. Line 46 to 50 initializes the valuedict. The given problem data only has upper case letters. I threw in values for lower case letters, numbers, and space and period so I could put "R. Drew Davis" into my smalllist.txt test data file. Lines 53-58 are the loop to tally up the weighted sum of all the name scores. And line 59 is where I returned the result. 14 lines of code in main(). Clear and straight-forward.

Object Lesson

The objective of this article was to get closer to understanding Object Oriented Programming and why it is useful in writing clean code. I haven't tried to provide a tutorial of the mechanics of using OOP in Python. Wesley Chun's book "Core Python Programming", 2nd edition, Chapter 13 is a decent reference for learning this stuff. Or if you are too cheap to invest in a reference book, dig into the Web with Google or your favorite search engine. There are plenty of web pages to be found that talk about Objects in Python.

In this article we looked at use of the pyparsing library's objects to define and apply a grammar. I haven't implemented an object and class on my own yet. We'll get to that in Part 2.

I'm still learning this stuff. If you spot anything that I've gotten wrong, please add a comment to let me know so I can correct both the article and my understanding of the topic. Thank-you.