News & Articles:

Kata: Dawkins Weasel

Dawkins Weasel seeks to demonstrate the principles behind evolution. Coding it is a fun exercise; the results are quite surprising.

A Weasel Yesterday

A Weasel Yesterday

Introduction

We don’t need to get into the rights or wrongs of Prof Dawkins’ views here (check the link above if you want to know more), we’re interested in this algorithm.  This explores how small random changes in a random string can eventually turn the string into some desired target. The usual example starts with a string of 28 random characters and aims to transform this into “METHINKS IT IS LIKE A WEASEL”.

Task

The task is to code the algorithm. The algorithm runs like this (to keep things simple only upper case letters and spaces are allowed in the string):

  1. Generate a random string of 28 characters.
  2. Make 100 copies of the string.
  3. For each character in each string, mutate the character to a random replacement with probability 5%.
  4. Find the string in the 100 that is closest to “METHINKS IT IS LIKE A WEASEL” (“closest” here can be defined as having the most correct letters in the correct position).
  5. If this string is “METHINKS IT IS LIKE A WEASEL”, exit. Otherwise, return to step 2 with this as the initial string.

Note: In step 3, it is possible that a correct letter in the string will mutate and be replaced with an incorrect letter.

For fun, before coding, jot down how many iterations you think will be needed on average to reach the target (if indeed it ever will be reached). Once you have a program, you might extend it to find the average number of iterations needed.

Creative Commons Licence
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Posted in Technical

Tags: , ,