Programming Praxis

6 Responses to “Dawkins’ Weasel”

1. James Curtis-Smith said

   November 14, 2014 at 10:01 AM

   String manipulation suits Perl down to the ground, here we use implicit lambda functions (which is one of the beauties of perl)

   Duration approx 0.15-0.25 seconds depending on randomness…

   use strict;
   use warnings;
   
   my @letters = (q( ),'A'..'Z');
   my $string = join q(), map {($letters[(rand @letters)])} 1..28;
   my $WEASEL = 'METHINKS IT IS LIKE A WEASEL';
   my $iter = 0;
   
   while( $string ne $WEASEL ) {
     $iter++;
     my( $max_score, $max_word ) = (0,q());
     foreach my $word ( map {( join q(), map {((rand 20 < 1) ? $letters[(rand @letters)] : $_ )} split m{}ms, $string)} 1..100 ) {
       my $score = grep { ! ord $_ } split m{}ms, ($word^$WEASEL);
       ( $max_word, $max_score ) = ($word, $score ) if $score >= $max_score;
     }
     $string = $max_word;
     printf "%4d %2d %s\n", $iter, $max_score, $string;
   }
   
2. Joost Kremers said

   November 14, 2014 at 1:36 PM

   A Common Lisp version I wrote a number of years ago for a class on the evolution of language:

   (defpackage "WEASEL"
     (:use "COMMON-LISP")
     (:export "EVOLUTION"))
   
   (in-package weasel)
   
   (defvar *target* "METHINKS IT IS LIKE A WEASEL")
   
   (defvar *characters* (cons #\Space
   			   (loop
   			      for c from (char-code #\A) to (char-code #\Z)
   			      collect (code-char c))))
   (defun create (length)
     (concatenate 'string (loop
   			  for i from 1 to length
   			  collect (nth (random (length *characters*)) *characters*))))
   
   (defun procreate (text error-rate n-offspring)
     (loop
        for i from 1 to n-offspring
        collect (map 'string #'(lambda (c)
   			      (if (< (random 100) error-rate)
   				  (nth (random (length *characters*)) *characters*)
   				  c))
   		  text)))
   
   (defun select (candidates)
     (car (sort candidates #'(lambda (x y)
   			    (< (fitness x) (fitness y))))))
   
   (defun fitness (string)
     (loop
        for c1 across string
        for c2 across *target*
        count (char/= c1 c2)))
   
   (defun report (entity generation stream)
     (format stream "Generation: ~A~%Entity: ~A~%Fitness (0 is best): ~A~%~%"
   	  generation entity (fitness entity)))
   
   (defun evolution (&key target (error-rate 1) (report-after 10)
   		  (n-offspring 10) max-generations log)
     (let ((*target* (if target
   		      (remove-if-not #'(lambda (c) (member c *characters*)) target)
   		      *target*)))
       (flet ((evolve (output-stream)
   	     (let ((first (create (length *target*))))
   	       (report first 1 output-stream)
   	       (do ((fittest first (select offspring))
   		    (offspring (procreate first error-rate n-offspring)
   			       (procreate fittest error-rate n-offspring))
   		    (generation 1 (1+ generation)))
   		   ((or (and max-generations (= generation max-generations))
   			(= (fitness fittest) 0))
   		    (report fittest generation output-stream))
   		 (when (and report-after
   			    (= (rem generation report-after) 0))
   		   (report fittest generation output-stream))))))
         (if log
   	  (with-open-file (stream log :direction :output :if-exists :overwrite
   				  :if-does-not-exist :create)
   	    (evolve stream))
   	  (evolve *standard-output*)))))
   
3. Graham said

   November 14, 2014 at 1:57 PM

   This is a fun genetic algorithm experiment! Thanks for posting it.

   #!/usr/bin/env python3
   
   from random import choice, random
   from string import ascii_uppercase
   
   GENES = "".join([ascii_uppercase, " "])
   TARGET = "ME THINKS IT IS LIKE A WEASEL"
   LENGTH = len(target)
   
   def reproduce(sequence):
       return [sequence] * 100
   
   def mutate(sequence):
       return "".join(choice(GENES) if random() < 0.05 else c for c in sequence)
   
   def fitness(sequence):
       return sum(c == t for (c, t) in zip(sequence, TARGET))
   
   def evolve(max_iters=int(1e3)):
       sequence = "".join(choice(GENES) for _ in range(LENGTH))
       for i in range(max_iters):
           population = map(mutate, reproduce(sequence))
           sequence = max(population, key=fitness)
           score = fitness(sequence)
           print("{0:5}: ({1:5}) {2}".format(i, score, sequence))
           if score == LENGTH:
               return
   
   if __name__ == "__main__":
       evolve()
   
4. Graham said

   November 14, 2014 at 2:40 PM

   oops! s/ME THINKS/METHINKS
5. Catalin (@catalin_c) said

   November 16, 2014 at 5:00 PM

   A Java solution:

   public class DawkinWeasel {
   
       private static final Random RANDOM = new Random();
   
       private static final String ASCII_UPPERCASE = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
   
       private static int score(String s1, String s2) {
           int score = 0;
           for (int i = 0; i < s1.length(); i++) {
               if (s1.charAt(i) == s2.charAt(i)) score++;
           }
           return score;
       }
   
       private static String mutate(String s, int p) {
           StringBuilder sb = new StringBuilder();
           for (int i = 0; i < s.length(); i++) {
               if (RANDOM.nextInt(100) < p) {
                   sb.append(randomChar());
               } else {
                   sb.append(s.charAt(i));
               }
           }
           return sb.toString();
       }
   
       private static char randomChar() {
           return ASCII_UPPERCASE.charAt(RANDOM.nextInt(ASCII_UPPERCASE.length()));
       }
   
       private static String randomString(int length) {
           StringBuilder sb = new StringBuilder();
           for (int i = 0; i < length; i++) {
               sb.append(randomChar());
           }
           return sb.toString();
       }
   
       private static int evolveTo(String ref) {
           String s = randomString(ref.length()),
                  bestMatch = s;
           int iterations = 0,
               bestScore = score(s, ref);
           while (true) {
               iterations++;
               for (int i = 0; i < 100; i++) {
                   String mutatedCopy = mutate(s, 5);
                   int score = score(mutatedCopy, ref);
                   if (score == ref.length()) {
                       // Perfect match
                       return iterations;
                   }
                   if (score > bestScore) {
                       bestScore = score;
                       bestMatch = mutatedCopy;
                   }
               }
               s = bestMatch;
           }
       }
   
       public static void main(String[] args) {
           String ref = "METHINKS IT IS LIKE A WEASEL";
           System.out.println("Evolved in " + evolveTo(ref) + " iterations");
       }
   }
   
6. Tom said

   November 20, 2014 at 3:04 PM

   My attempt at a clojure version here (apologies for formatting):

   
   (ns weasel)
   
   (defn rand-char [] (.charAt "ABCDEFGHIJKLMNOPQRSTUVWXYZ " (rand-int 27)))
   
   (defn mutate [chr-vec]
     (assoc chr-vec (rand-int (count chr-vec)) (rand-char)))
   
   (defn score [target candidate]
     (reduce + (map #(if (= %1 %2) 1 0) target candidate)))
   
   (defn next-gen-best [target candidate]
     (apply max-key #(score target %1) (vec (repeatedly 100 #(mutate candidate)))))
   
   (defn best-fit [target first second]
     (if (> (score target first) (score target second)) first second))
   
   (defn run [target-str]
     (let [target (vec (char-array target-str))
           initial (vec (repeatedly (count target) rand-char))]
     (loop [best initial
            i 0]
       (if (= (score target best) (count target))
         i
         (recur (best-fit target best (next-gen-best target best)) (inc i))))))
   
   ; (run "METHINKS IT IS LIKE A WEASEL")
   

Leave a Reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

Cancel

Connecting to %s

Notify me of new comments via email.

Notify me of new posts via email.

Δ