Hey Everybody, I will be attending the US PyCon starting tomorrow. If anyone of my readers are in town for the convention and are interested, I would happily meet up with you for drinks, food, or whatever. Send me a tweet.
It’s time once again for a favorite blog theme, The Project Euler post. This time around I am answering problem twelve. The website states the problem as:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
What is the value of the first triangle number to have over five hundred divisors?
o spice things up I decided to use a language I haven't used for these in a while, Perl. I also included the usual suspects: Python and Haskell. So, here's the Perl code:
Nothing really new or interesting to mention in this code. Here is the Python code:
Pretty standard stuff for the most part. I think the only non-standard thing worth mentioning is the infinite triangle number generator. This took a little finangling, but I got it to work in the end.
Here is the Haskell code:
After creating these solutions, I did my usual, highly accurate, testing method to determine the speed of the computation. I was surprised by my results:
Normally the Haskell solution would be significantly faster, and I have a theory as to why the Haskell times are so close. In Perl and Python I’m doing two additions – one for the increase of the index number and another to increase the total number. In Haskell I’m doing 1 + n additions; the first is to increase the index, and the remaining additions (n) are those used to calculate the sum of all the numbers between (and including) 1 and the index. As the index variable gets larger, that calculation takes more and more time to perform. I would write this up as suboptimal. After spending some time traveling “the tubes,” I discovered the State Monad, which is the reason why this blog post took me so long. I had to spend a week going through random blogs, skimming books, and beating my head against a wall (more than usual) to figure this out.
Quick diversion, for those of you who do not know what the State Monad is, let me take a moment to to try and explain what it is and why it’s important in this context. Those of us that come from an imperative language (I am one of you in this regard) are used to being able to do a simple addition such as (in pseudo code):
Variable = 2
We can’t do this in Haskell; instead we have to create a new variable name for each new variable assignment. We could also create a function that recursively goes forward, generating the next number in the sequence and bringing our needed variables with us before going deeper down the recursion rabbit hole. With the State Monad, however, we can write our function in such a way that the necessary variables are implicitly passed. Take a look at the new solution to see what I mean:
The tick function does not have any input parameters. All the information that the function needs comes from the “get” function call, which grabs the current state from the State Monad. If the tick function does not find a number of divisors greater than five hundred, it inserts new values back into the State Monad, and goes down to the next level of recursion.
It took me a long time to figure this out, mostly because of the lack of examples on the internet concerning the State Monad. If I wanted to create a random number generator I would have been set, but sadly I just wanted to create something that would hold a tuple of numbers and increment them accordingly. So I highly modified one of the “random number generator” examples.
My “highly accurate” speed test results for the new version is:
which is a vast improvement (> 11s) over the previous implementation.
While a Project Euler problem may not have been the best way to learn about using the State Monad, I'm glad I stumbled upon it. I hope that it can be used as an example for others if they want to learn how to use the this particular monad to create things other than pseudo-random number generators.
One last thing – some of the brighter crayons in the box (which is most of you, based on the level of comments that I receive) might have noticed that I skipped problem 11. There is a simple response to that. I still haven’t solved it.
I believe that one of the key requirements for writing pythonic code is readability, as briefly mentioned in “The Zen of Python” by Tim Peters. I also believe that this little poem (I use that term loosely here) gives some pretty good hints on how to write pythonic code. (This is for more of the thought process outside the general coding style stuff defined in PEP-8). Here is the Zen of Python:
Since this post is about pythonic code, I want to take a quick moment to show you what I mean, saving you a google search or two in the process. Here is a class method that I would consider non-pythonic code:
Now here is a more pythonic version of the same code:
While the first version of the code above is not wrong and would probably be the correct way to do this in other programming languages, it’s not the best way to do it in python. (I also expect to see quite a few comments on how other python programmers might improve the first or second versions of these functions.)
Now that we have that little example out of the way, let me share with you the motivation for this blog post. At work one day I saw some code that looked like this:
oddly enough, I remembered De Morgan’s Law from my formal logic courses, so I used it to simplify the expression. Here is the proof (in formal logic notation because it’s quicker):
After the logic juggling above I renamed the variables and then modified the code to resemble the ending result:
After the change we can immediately see that I’ve reduced number of not calls. While I’m sure there is some performance improvement, I seriously doubt that it’s something that might be noticed by a human being, so we’ll just discount this as any form of optimization. I believe I’ve also made the code easier to read. The line itself is smaller, so a maintainer would have less “things” to juggle in their head to verify that the expression should pass or fail. Thus this code change has fulfilled some of the ideas in the “Zen of Python,” particularly the parts about “Simple is better than complex,” and “Readability counts.” However, in the final product I’ve had to add some parentheses in order for the logic to be correct, and this is where my ultimate question lies. In a lot of “pythonic” code examples on the web, one doesn’t really see “if” statements written like this one. So a somewhat self-conscious part of me thinks that I even though I have gone through the trouble of trying to make the code cleaner, I still haven’t gotten the code to be “pythonic”.
After thinking about it a little more, I decided that my version is pythonic. While I did add some clutter by adding parentheses, I also removed 3 “not calls” and made the line easier to understand. I believe this follows the spirit of pythonic code, even if it does not follow the the code to the letter.
Top photo credit goes to: mromtz
The most recent problem I got to sink my teeth into (found it on a recruiting site, but not going to share where I got it; wouldn’t be fair to the company posting the problem) is for finding pangrams in sentences. If you don’t know what a pangram is Wikipedia defines them as, “a sentence using every letter of the alphabet at least once.” Yeah, I didn’t know what they were either until I started programming this little puzzle. Here is the code:
I came up with the solution pretty quickly by using Sets. Having a set of the alphabet and finding the difference of the letters used in the sentence makes the problem almost trivial. The hard part for me was figuring out how to filter out the spaces and change all characters to lower case in the buildList function. I eventually figured it out, but it took some head against wall action to get it right.
This is going to be my last post for this year. I would like to wish you all Happy Holidays and a Happy New Year. Thank for reading and see you again in 2012. I would also like to thank everyone from planet.haskell.org who decided to read this. Welcome!