class GA
  def initialize(goal)
    @goal = goal.split(//)
    @len = goal.length
    @pop = Array.new(100).map { random_string }
  end

  def fitness(string)
    count = 0
    @goal.zip(string.split('')) do |a, b|
      count += 1 if a == b
    end
    count / @len.to_f
  end

  def random_string
    r = Array.new(@len).map { randchr }.join
  end

  def randchr
    (rand(27) + ?A).chr.send(rand(2) == 0 ? :upcase : :downcase).gsub('[', ' ')
  end

  def trim_bad
    @pop = @pop[0, 20]
  end

  def breed(a, b)
    combine_point = rand(@len)
    ret = a[0, combine_point]
    ret += b[combine_point, @len]
    ret
  end

  def mutate(a)
    a[rand(@len)] = randchr
    a
  end

  def evolve
    if fitness(@pop.first) == 1
      puts "---------"
      puts "Goal reached!"
      puts "Output: #{@pop.first}"
      break
    end

    puts "Best fit: #{@pop.first}"
    while @pop.size < 100
      a = rand(20)
      b = rand(20)
      @pop << mutate(breed(@pop[a], @pop[b]))
      @pop.uniq!
    end
    @pop.sort! do |a, b|
      fitness(b) <=> fitness(a)
    end
    trim_bad
  end
end

ga = GA.new('Hello world')
loop { ga.evolve }