object Evolution {
  import scala.util.Random.{nextBoolean, nextInt, nextDouble}

  /** Generate a random string. */
  def randomString(n: Int) = (1 to n).map(_ => (nextInt(96)+32).toChar).mkString

  /** Generate a random, initial population of DNA sequences. */
  def initialPopulation(n: Int): IndexedSeq[String] = {
    for (_ <- 1 to n) yield randomString(nextInt(20) + 10)
  }

  /** An implicit class to add functionality to a DNA string. */
  implicit class DNA(s: String) {

    /** Calculate how close this string is to a target string. Calculate the
      * delta between each character and when one string is longer than the
      * other assume null (\u0000) for the character.
      *
      * A fitness value of 0.0 is a perfect match. As the strings diverge,
      * make the fitness exponentially larger.
      */
    def fitness(target: String): Double = {
      (0 until target.size.max(s.size)).foldLeft(0.0) { (f, i) =>
        val a = s.lift(i).map(_.toInt).getOrElse(0)
        val b = target.lift(i).map(_.toInt).getOrElse(0)

        // square the delta between two characters
        f + (a - b) * (a - b)
      }
    }

    /** Since a new DNA sequence is a combination of "mom" and "dad", the
      * first step is to crossover two DNA sequences: take a slice of one
      * and a slice of the other and combine them together.
      */
    def cross(c: String): String = {
      val i = nextInt(c.size.min(s.size))

      // take some from one string and some from the other
      if (nextBoolean) {
          c.take(i) + s.drop(i)
      } else {
          s.take(i) + c.drop(i)
      }
    }

    /** Mutations are a random change within a DNA sequence. One or more
      * bases within the original DNA strand are removed and a new sequence
      * replaces it. The new sequence can be shorter or longer.
      */
    def mutate(mutationRate: Double = 0.1): String = {
      if (nextDouble >= mutationRate) {
        return s
      }

      // what character(s) to replace (i), how many (r), and with how many (n)
      val i = nextInt(s.size)
      val r = nextInt(3)+1
      val n = nextInt(3)

      // patch the string with a new sequence
      s.patch(i, randomString(n), r)
    }
  }

  /** An implicit class for manipulating populations of DNA sequences. */
  implicit class Population(xs: IndexedSeq[String]) {

    /** Returns a population sorted by fitness to a particular string. */
    def fitToString(target: String): IndexedSeq[String] = {
      xs.map(it => (it fitness target, it)).sortBy(_._1).map(_._2)
    }

    /** Return the best parent randomly from a few choices. Assuming
      * the population is sorted (fitToString), then the smallest
      * index chosen is considered the "best".
      *
      * This is meant to simulate selective breeding. In the wild,
      * animals have multiple choices for mating, and fight for
      * rights to choose mate that will provide their children the
      * greatest chances of survival.
      */
    def parent(n: Int) = xs((1 to n).map(_ => nextInt(xs.size)).min)

    /** Create a child from two random parents. This is done by first
      * selecting the parents, crossing them, and then (optionally) 
      * introducing a random mutation.
      */
    def breed(selections: Int, mutationRate: Double) = {
      parent(selections).cross(parent(selections)).mutate(mutationRate)
    }

    /** Breed a new population from the current one. */
    def nextGen(selections: Int, mutationRate: Double) = {
      (1 to xs.size).map(_ => breed(selections, mutationRate)).filter(_.size > 0)
    }
  }
}

@ randomString(10)
String = "CRcp(4av~]"

@ "Test".fitness("Test")
Double = 0.0

@ "Test".fitness("foobar")
Double = 261.0

@ "abcde".cross("12345678")
String = "123de"

@ "abcde".mutate(1.0)
String = "a]cd"

@ initialPopulation(5)
IndexedSeq[String] = Vector(
  "$%iJzT<EUF/",
  "m:n]VpeKy1jY_|{QJn|l^M",
  "o|Qo\"P02) d/a%[^8VzMI\u007fO!sQ2zv",
  "Vt)vRi:FgT#<.1ep`ADl`",
  "\u007f<H9JAoJ*ETaL)*0\";@\\{C,y~;S"
)

@ initialPopulation(5).fitToString("Hello").nextGen(2, 0.1)
IndexedSeq[String] = Vector(
  "UN=q]T0W9I~rte$K'biSBmh",
  "2Cu;pre\u007fNz<,fm*+-&iSBmh",
  "tQ)|!o?ei`hjo+&!FUw",
  "tQ)|!o0W9I~rte$K'b9SsKK7Q\"h",
  "0X|jprKvqu"
)

import scala.io.StdIn

def run = {
  print("Enter something to evolve: ")

  // read the fitness target
  val target = StdIn.readLine

  // some parameters worth tweaking to see the results
  val generations = 10000
  val populationSize = 200
  val breedingSelections = 3
  val mutationRate = 0.1

  // create an initial population of strings
  var pop = initialPopulation(populationSize).fitToString(target)

  // run for N generations
  for (i <- 1 to generations) {
    pop = pop.nextGen(breedingSelections, mutationRate).fitToString(target)

    // output the "best" child for each generation
    println(s"generation $i: ${pop.head}")
  }
}