Cramming Darwin into My Cell Phone

My father, a Professor of Biology, is fond of telling his students (and children): Darwin is always in the room. The idea, as he's explained to me, is that the basic elements of evolution (competition, mutation, adaptation, selection, etc.) are present in all biological processes, no matter how big or small. So if Darwin can be in the room, why not in my computer?

I give you the latest exercise from Programming Praxis: Dawkin's Weasel. This exercise requires that you implement the basic constructs of evolution in code:

I don’t know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence ‘Methinks it is like a weasel’, and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?
...
We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before … it duplicates it repeatedly, but with a certain chance of random error – ‘mutation’ – in the copying. The computer examines the mutant nonsense phrases, the ‘progeny’ of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.

Writing the prescribed algorithm was easy enough. You can find the complete source code here and the highlights below. Writing the code efficiently, on the other hand, turned out to be more elusive. My version creeps along, taking about 25 minutes to produce an answer. Why the sluggishness? I could blame it on the fact that I'm running it on an interpreter on my phone, but really, it's slow because I haven't take the time to make it fast. Still, after exactly 333 successive generations the system went from pure randomness to the target phrase (on run #2, it only took 211 generations to produce the right match). Slow and steady, that seems appropriate for the topic anyway.

As a programmer, I can't help but marvel at how simple and effective this algorithm is. By providing two key elements: (a) a way to introduce change and (b) a way to score the results, I'm able to write code that finds a solution even though I have no idea what the ideal path to producing that solution is. It's no surprise that there's a whole area of programming dedicated to this approach.

While I think this exercise nicely demonstrates some key aspects of evolution, my favorite experiment on the topic is still this one. In this case, the power of mutation (a key ingredient for evolution) is shown using the act of tracing a single vertical line. Spoiler alert: all those tiny errors introduce when a person tries and fails to copy the line exactly turn into significant changes. The results are pretty staggering. If you want to skip all the chit chat, and just see the effect in action, check out this video.

And here's the code for our computer monkeys:

; http://programmingpraxis.com/2014/11/14/dawkins-weasel/
;
; requires sort from:
;  https://raw.githubusercontent.com/benjisimon/code/master/programming-praxis/dawkins-weasle.scm

(define goal (string->list "METHINKS IT IS LIKE A WEASEL"))

(define (range low high)
 (if (> low high) '()
     (cons low (range (+ 1 low) high))))

(define (rand-char)
 (let ((offset (random-integer 27)))
  (if (= offset 26) #\space
      (integer->char (+ 65 offset)))))
      
(define (mutate input)
 (map (lambda (x)
       (let ((rand (random-integer 100)))
        (if (< rand 5) (rand-char) x)))
       input))
  
(define (score input)
 (let loop ((value 0) (input input) (goal goal))
  (cond ((null? input) value)
        (else
         (loop (if (equal? (car input) (car goal))
                   (+ 1 value) 0)
               (cdr input) (cdr goal))))))
               
(define (bang)
 (map (lambda (c) (rand-char)) goal))
 

(define (tick input)
 (let ((attempts
         (sort (map (lambda (i) (mutate input)) (range 1 100))
               (lambda (x y)
                 (> (score x) (score y))))))
   (car attempts)))
 
(define (solve)
 (let loop ((generation 0) (input (bang)))
  (cond ((equal? goal input) generation)
        (else
         (display (list generation (score input))) (newline)
         (loop (+ 1 generation)
               (tick input))))))