Monday, September 7, 2009

Spanking Dawkins's Weasel

One of the problems with learning a new programming language is coming up with interesting "beginner" programs. Most beginning programs do something exciting like printing out "Howdy, Howdy, Howdy, Joe". Heart stopping stuff ain't it?

To ease this a bit, whenever I come up with an interesting idea for a beginner program, I'll write it up and you can give it a shot.

My hands down favorite simple program is something called Dawkins's Weasel.

Richard Dawkins is a evolutionary biologist from Oxford. He wanted to come up with a program to show the difference between a random mutation and a random mutation with selection. The result is a simple, straight forward program called "Dawkins's Weasel".

Note: Whenever I say "letter" below, I mean letters and/or spaces. Saying letter and/or space all over the place makes for a tedious read.

First we start with a target sentence, which we'll call "Target". This is what all good little sentences want to be when they grow up. Dawkins used "methinks it is like a weasel" and so will we.

Next we create a parent sentence called "Parent". This is a gibberish sentence of random letters that is the same length as Target. "y ksqmjwepqtgtyylmfexstvktpa" will work, as will "aaaaaaaaaaaaaaaaaaaaaaaaaaaa".

Our goal is going to be to evolve Parent into Target.

Parent will produce a litter of children. The fittest of the litter will then become the next parent. This continues until we produce a Parent that equals Target. It's survival of the fittest and all that jazz.

Unfortunately the sex life of a sentence is pretty dull. The way a sentence has a baby sentence is by copying itself and then changing a single letter at random. Not exactly the stuff of pornos. We'll call the baby sentence "Child".

As for who's the fittest? We'll use something simple. We'll count the number of letters in Child that match Target. For example, the sentence "aaaaaaaaaaaaaaaaaaaaaaaaaaa" would score a 2. "methinks it is like a measel" would score 27. If there is more than one pick of the litter, choose one. It doesn't matter how.

That's pretty much it. The only real variable you get to play with is the size of the litter. If you start with a litter of 50 then you tend to finish in less that 100 generations. Once you get the code working, starting dialing playing with the litter size to see how it effects the generation count.

I'll try to keep my eye out for other interesting algorithms worthy of posting. If you know of any that are fun, the add a comment.