require 'levenshtein'

PHRASE = "METHINKS IT IS LIKE A WEASEL"
MUTATION_RANGE = (-1..1)

class Array
  def keys
    (0...length).to_a
  end
end

class Range
  def sample
    to_a.sample
  end
end

class String
  def mutate!(amount = 20)
    arr = split('')
    while amount > 0 do
      key = arr.keys.sample
      cur = arr[key].ord

      arr[key] = (cur + MUTATION_RANGE.sample).chr

      amount -= 1
    end

    replace(arr.join)
  end

  def mutate(amount = 20)
    dup.mutate!(amount)
  end
end

class Evolution
  def initialize(target, per_turn: 20)
    @turn     = 0
    @per_turn = per_turn

    @target = target
    @string = (0...@target.length).map { ('A'..'Z').sample }.join
    puts "Starting string: #{@string}"
  end

  def go!
    loop do
      break if done?
      turn
    end
  end

  private

  def turn
    best = best_mutation(n_mutations)
    puts "#{@turn}: #{best}"

    @turn += 1
  end

  def done?
    @target == @string
  end

  def n_mutations
    ([@string] * @per_turn).map(&:mutate)
  end

  def best_mutation(muts)
    muts.inject { |last, cur|
      Levenshtein.distance(last, @target) >
      Levenshtein.distance(cur, @target)  ?
      last                                :
      cur
    }
  end
end

Evolution.new(PHRASE).go!