October 7, 2007

The Evolution of a Programming Puzzle

Posted in Coding tagged , , at 10:59 am by mj

Mark-Jason Dominus is currently examining a series of programs attempting to solve Van der Waerden’s problem: four that he wrote in 1988, and one he wrote this year.

Van der Waerden’s theorem says that for any number of colors, say C, a sufficiently-long row of colored dots will contain n evenly-spaced same-color dots for any n. Or, put another way, if you partition the integers into C disjoint classes, at least one class will contain arbitrarily long arithmetic progressions.

So far, he’s only written an introduction and dissected two of his 1988 programs, but it’s already a memorable series. Not only does it show the iterative process of solving an interesting problem (suitable for a SSE interview?), but it tells the story of his evolution as a programmer.

Mark’s blog is one of my favorites, and even though his posts tend to be long and interesting, I never mark them as “toread” the way I do most other long posts when I’m catching up on feeds. I always reflect on them, even if it means making negative progress on my feed reading.

Some quotes to set the mood:

In yesterday’s article I wrote about a crappy program to search for “good” strings in van der Waerden’s problem. It was crappy because it searched the entire space of all 327 3^27 strings, with no pruning. I can’t remember whether I expected this to be practical at the time. Did I really think it would work?
I was thinking this afternoon how it’s intersting the way I wrote this. It’s written the way it would have been done, had I been using a functional programming language. In a functional language, you would never mutate the same string for each function call; you always copy the old structure and construct a new one, just as I did in this program. This is why C programmers abominate functional languages.


On an unrelated note, I’m thinking about auto-posting items from my Google Reader shared items to this blog. Good idea? Bad idea? Should I do so on a daily basis, or put a bit more work into rating them and posting the top N weekly? Or do it all manually?

Update (2007-10-13): Mark pointed out that the exponent did not survive my copy and paste, so it appeared he was only searching through 327 strings, instead of 3^27. D’oh!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: