Saturday, December 22, 2007

How the legacy of a dead mathematician can make you a better programmer

When was the last time you were challenged by an algorithm? As professional programmers, we often spend our day tackling things like:

The list goes on and on.

But again I ask, when was the last time you were challenged by an algorithm?

I remember when I was 13 and writing a program for my aunt to help her schedule appointments for people. I had to make sure that people weren't scheduled on holidays like Christmas. I was writing the program in BASIC and it required me to learn things like Julian dates. Days like Christmas and the 4th of July were easy because they always fell on the same day each year. The first one to really give me problems was Thanksgiving. Every stinkin' year it was on a different date!

The solution baffled me at the time. I even made use of my access to this new thing called the "Internet" and asked puzzle gurus there for help. I believe later that day I went to Old Country Buffet with my family and kept thinking about it. After loading up on food, we were walking back to our car and it hit me: "start with the first Thursday in December and subtract 7 days!!" I already had code that told me what day of the week a Julian date fell on, so this was easy. After realizing this wouldn't work for Thanksgiving 1995 which was two months away, I think I corrected it to find the first Thursday in November and then calculate the right number of days afterwards.

I'm sure you're laughing at my early struggles. It's probably "intuitively obvious to [you,] the most casual observer" what the right algorithm is, but for my 13 year old self, it was hard.In college, I especially remember being challenged by algorithm problems like figuring out what words to suggest for a mispelled word. The algorithms were non-obvious and took time to figure out. However, in the end, I usually ended up growing in my understanding of computer science as a result of solving them and in the process added a few more tools to my algorithmic toolkit.

After graduating and entering "the real world," I rarely had to wrestle with an algorithm and instead focused on more tactical issues like the bullet points above. This always nagged at me; I felt as if I was somehow "rotting" in my computer science abilities. My thinking was that if I kept getting bogged down in the tactical, day-to-day stuff, I'd never be able to "hit the high notes" as a developer. It's been this fear of skills rot that has pushed me to look into Lisp, Haskell, F#, Erlang, and other languages to avoid The Blub Paradox. It's what drives me to attempt to attack code bloat, read modern papers and watch videos of people way smarter than myself. It's what makes me think of books like Code Complete, Code Craft, and Framework Design Guidelines each time I write code.

And lately, it's what drove me to the legacy of a dead mathematician. I found ProjectEuler.net last week. It is a website dedicated to problems that can be solved efficiently with a good algorithm that runs for less than a minute. It's in memory of the master mathematician, Leonhard Euler, who loved to "tinker" with mathematics and algorithms. I'm sure he'd probably work at Google if he were alive today.

What I love about ProjectEuler is that while some of the problems are very challenging, they are at least possible for me to solve. I've seen way too many contests that just are no fun because they take too long to solve or are just too hard.

Some took me only a few seconds to figure out, some have taken me an hour, and some I still haven't been able to solve. The real fun part is that once you solve the problem, you are granted access to a forum where people discuss their solutions. It's there where I've been most humbled. I might have taken 40 lines of code to figure out something someone did in a few minutes using a one line program in J, a language that I had never even heard of before. Still others will do it in Haskell or Python in a couple lines of code. Some brave guy consistently writes his solution in x86 assembler.

My approach has been to use C# 3.0's new features whenever possible. I was thrilled to be able to solve problem #19 in 1 line using LINQ concepts. I also really had fun with #56, writing an algorithm to decode a secret message. Although the site looks heavy on math, it's more about thinking algorithmically and no problems require fancy math beyond what you would have learned by high school.

I'm not saying ProjectEuler.net is the only way to improve as a developer. I'm sure some folks have very busy schedules with kids and other activities that make it almost impossible to study anything outside of work. However, I've found tackling a ProjectEuler problem can easily be more fun than watching an average weeknight TV show or just surfing the web in general, but that's just me.

What do you do to sharpen your algorithm saw? Are you registered on ProjectEuler? If so, what's your username? (Here's my profile) I'd love to learn from you if you post your solutions on the forums. It could be fun to have a friendly competition.


kick it on DotNetKicks.com

19 comments:

gumuz said...

This post made me remeber I once started solving these Euler challenges... need to pick that up again, thanx

http://projecteuler.net/index.php?section=profile&profile=3168

Jeff Moser said...

gumuz: Thanks for the comment! I'll keep a lookout for you on ProjectEuler

Anonymous said...

You probably want to check out www.topcoder.com/tc There are contests which are 75 minutes long, with two divisions for the beginners and the advanced people with a very nice community.

Jeff Moser said...

TopCoder seems like it's much more competition/time sensitive in the "who can solve a rubik's cube the fastest?" sort of way. Maybe I'm missing something?

What I like about ProjectEuler is that the site has been around for about 3 years and it's all on your own pace.

I'll keep an eye on TC's feed though. Thanks for the suggestion.

Jeff Moser said...

Actually, it looks like there is no single problem feed on TC.

Another source that I found interesting was CodeKata, but it hasn't been updated in a long time.

Anonymous said...

You said "although the site looks heavy on math, it's more about thinking algorithmically and no problems require fancy math beyond what you would have learned by high school."

That's true at the start; but some of the higher number problems require math well beyond high school level - but nothing that a good coder can't research and understand with the aid of Wikipedia and Google.

Learning the new stuff can be a fun adventure all of its own - and when you then get the right answer, a huge satisfaction.

Some of the later problems are really challenging. 161 has been holding me at bay for weeks now...

This is me on Project Euler.

Cornick said...

This post made me remember something like this one:
This is the Problem!

Greg C said...

Have you had a look at: http://www.programming-challenges.com/pg.php?page=index

BioGeek said...

Solved 41 problems (24%) so far, mostly in Python. I'm a biologist with no formal programming training, so each new problem now takes me longer and longer. Also, I often succeed in coding a brute force attack, but which takes much much longer then 1 minute to run. I let it run anyway (sometimes for days) so that I can enter the forums and learn new algorithmical tricks that I then can use to tackle new problems.

Jeff Moser said...

Thanks for the comments everyone (including the folks on Reddit and YCombinator)

Thumbo: Wow! I'm impressed to have such a ProjectEuler celebrity comment. Awesome job on getting the 99% genius rating. You leave me in the dust! You're right on the high school comment. People (myself included) have to look up some of the terms since I'd never heard of things like pandigital numbers, but they're within reach to at least understand the problem.

BioGeek: Great to hear your story. It looks like we're close on the site in stats. I'll keep an eye out for you.

I hadn't looked at the programming challenges website or the Sphere Online Judge that the reddit folks recommended. While both have some interesting problems, they seem to lack the strong and diverse community that ProjectEuler.net has.

It was also interesting/suprising coincidence that there was a podcast released about ProjectEuler just a few hours after I posted.

Keep up with the great comments everyone. I appreciate the feedback.

Anonymous said...

Jeff-

Very cool that you posted this entry on the same day of the Thirsty Developer podcast on the same subject.

My Euler ID is larryclarkin

-Larry Clarkin

Anonymous said...

Jeff: No, I'm no celebrity (but thanks for the kind words). I found Project Euler some time ago, so I just had a head start. I'm not a mathematician, just a coder, and if I can do those problems anyone can, with patience and persistence.

Talking of persistence - I finally cracked 161 today, after fighting it on and off for the three months since it was released.

100% now. Yay!

Thumbo on Project Euler

Jeff Moser said...

Thumbo: Congratulations!! I thought about it for a few minutes but didn't come up with any solution yet. I'm sure I'll continue to think about it some more as I run out of problems that are a little less difficult.

I'm way below you in the ranking. My next goal is to break 1000th place.

It's been fun to attach a story with a profile name for you and BioGeek.

Keep up the good work! One day I might be close to you. I've got a lot of catching up to do.

Mike Petry said...

Great post. This interest in algorithms kind of fits in with the increased interest in functional languages like Erlang. That is where my head is today. As I learn Erlang, I will try to apply its unique capabilities to classic software algorithms and see what comes out!

Mike Petry said...

btw, I noticed a little familial resemblance between yourself and the great Euler. Perhaps there is a genetic connection. It would account for your talents. But please do not consider going about in your bathrobe with a pair of short pants on your head.

thomas said...

Hmm..could someone tell me if these problems are possible to solve with perl? I just started getting into programming about 6 months ago, and decided to start with perl. I feel that I am somewhat close to cleansing myself of the beginner tag taht I am known by (by myself anyway) and hope that these problems could help with that.

Jeff Moser said...

Thomas: I'd say all of them are solvable in Perl. If you look at the rankings you'll see quite a few people that use Perl. Some folks even are doing them in PHP. My language of choice is C#, but just about any modern general purpose language will do.

Gustavo Duarte said...

Awesome post!

I was feeling the exact way you describe and just started checking out these challenge sites myself a couple of days ago. I wanted some challenges and also to get my mathematics back in shape, since it's sort of like a language and after a while you start losing it.

Here are some random points that were floating in my head on this stuff:

1. Have you ever used Mathematica? It's an absolutely amazing piece of software with a LISPish language and beautiful architecture. I started on Project Euler too and I'm amazed at how many of the problems are one liners in Mathematica.

2. Have you read "The Algorithm Design Manual" by Skiena? It's an awesome book, fun to read and mind expanding. Great stuff. He also has a book on Programming Challenges that I just saw on Amazon (looking for other books) but I don't have that one, so not sure how good it is.

3. Math. I really want to be able to read/write math again with fluidity.

Over the holidays I got Mathematica up and running and started cranking through some proofs and new algorithms (basically the second half of "Introduction to Algorithms" by Cormen et al.

Good luck in your challenges :)

cheers.

Jeff Moser said...

Gustavo Duarte:

1. I used Mathematica a lot in college. Its native syntax is basically describing an abstract syntax tree (sort of like s-expressions) that gets evaluated. Simple, but quite effective. I like its raw power and built in capabilities (numerics, combinatorics, symbolic integration, etc..). I'd love to tinker with Mathematica more, but its price is too restrictive for my hobby use. I asked Wolfram for the equivalent of an "Express Edition" of Mathematica but to no avail.

I ended up writing my own utility library for Project Euler problems in C# and using a big number library from Mono.

2. I have been eyeing that book ever since Steve Yegge mentioned it (and then saw the 2nd edition was coming out in Aug '08). I don't have it yet but plan on getting it sometime in 2009 if I can get through my book backlog.

3. I think math has a timeless beauty that doesn't rot -- much like a good computer algorithm. That's what drew me into it in school and even now as a casual player. I'll never hit Euler's or even Fermat's level, but its fun to think mathematically.

Congrats on the Cormen et al book adventures! I've flipped through it, but haven't gone through it in depth (I used Udi Manber's book in school). My plan is to go through Skiena's since it seems like a good refresher.

Thanks for comments!

(P.S. By the way, I really like your blog and the research you put into each post. Keep up the great work!)