String evolution as described in Richard Dawkins: "The Blind Watchmaker"

watchmaker.rb

# from: http://www.informit.com/articles/article.aspx?p=683059&seqNum=36
class String
  def levenshtein(other, ins=2, del=2, sub=1)
    # ins, del, sub are weighted costs
    return nil if self.nil?
    return nil if other.nil?
    dm = []        # distance matrix

    # Initialize first row values
    dm[0] = (0..self.length).collect { |i| i * ins }
    fill = [0] * (self.length - 1)

    # Initialize first column values
    for i in 1..other.length
      dm[i] = [i * del, fill.flatten]
    end

    # populate matrix
    for i in 1..other.length
      for j in 1..self.length
    # critical comparison
        dm[i][j] = [
             dm[i-1][j-1] +
               (self[j-1] == other[i-1] ? 0 : sub),
                 dm[i][j-1] + ins,
             dm[i-1][j] + del
       ].min
      end
    end

    # The last value in matrix is the
    # Levenshtein distance between the strings
    dm[other.length][self.length]
  end
end

#only use lower case letters and space
chrs='abcdefghijklmnopqrstuvwxyz '

# This is the string we want our other string to evolve to
master = "methinks it is like a weasel"

# Random string that should evolve
start =  "skeobnfj engjsjnd dfsdf werw"


# Get a baseline of how different they are
dist = master.levenshtein(start)
#loop while the strings are different
while dist > 0 do
  # pick a random character to change
  pos = rand(start.length)

  # insert a random character there
  chr = chrs[ rand(chrs.length) ]
  new_string = start.dup
  new_string[pos]=chr

  # calculate a new distance
  d = master.levenshtein(new_string)

  # if the distance is less, save the new string
  if d<dist then
    dist = d
    start = new_string
    puts start
  end
end