#light

/// fold integer to given range
/// 
/// eg: fi (-2341) 3 7  => 4
let rec fi i low high =
  if low<=i && i<=high then i
  else if i>high then fi (high-i) low high
  else fi (low+i) low high

/// fits integer to allowed range
/// 
/// eg: fiti (-2341) => 33
let fiti i =
  fi i (int_of_char ' ') (int_of_char 'z')
  
/// in an integer list find the smallest integer , its position (0 based) and the (length of list-1)
///
/// eg: minl [4;2;1;3;5] => (1,2,5)
let minl l =
  List.fold_left (fun (min, midx, cidx) curr -> 
                    if curr<min then (curr, cidx, cidx+1) 
                    else (min, midx, cidx+1))
                  ((List.hd l), 0, 0) 
                  l

/// convert string to list of chars
///
///   eg: s2cl "apple" => ['a';'p';'p';'l';'e']
let s2cl (str:string) =
  let mutable lst = [] in
  for i = 0 to (str.Length)-1 do
    lst <- str.[str.Length-i-1] :: lst
  lst

/// convert list of characters to a string
///
///   eg: cl2s ['a';'p';'p';'l';'e'] => "apple"
let cl2s cl =
  List.fold_left (fun acc c -> acc + String.of_char c) "" cl

/// convert list of characters to list of integers
///
///   eg: cl2li ['a';'p';'p';'l';'e'] => [97;112;112;108;101]
let cl2il cl =
  List.map int_of_char cl

/// convert list of integers to list of character
///
///  eg: il2cl [97;112;112;108;101] => ['a';'p';'p';'l';'e']
let il2cl il =
  List.map char_of_int il

/// hamming distance (see: http://en.wikipedia.org/wiki/Hamming_distance) of 2 integer lists
///
///   eg: hd [97;112;112;108;101] [97;112;111;100;101] => 65
let hd il1 il2 =
  let sqr x = x * x
  List.fold_left2 (fun acc i1 i2 -> acc+sqr(i1-i2)) 0 il1 il2

let rand = new System.Random()

/// generate "appropriate" random integer
///
/// eg: ri 0 => 25
/// TODO: check when i is not present why yields the same number every time
let ri i =
  let x = rand.Next(20,123)
  fiti x
  
/// generate a random list of integers of length n
///
///   eg: rli 5 => [50;52;46;33;19]
let rli n =
  List.init n (fun i -> ri i)

/// mutate a list of integers
///   li - lit of integers to mutate
///   mr - mutant's max hamming distance from original
///   p - mutation probability [0,1]
///
/// eg: mli [50;52;46;33;19] 5 0.3 => [50;52;46;36;19]
let mli li mr p =
  List.map 
    (fun i -> 
      // mutate with probability p and range mr
      if rand.NextDouble()<=p then fiti (i+rand.Next(-mr,mr))
      else i) 
     li

let rec evolve individual nthgeneration target n mr mp =
  printf "generation: %d, current individual: %s\n" nthgeneration (cl2s (il2cl individual));
  // generate from individual n-1 mutants
  let mutants = List.init (n-1) (fun i -> mli individual mr mp)
  // new population is the individual and its mutants
  let population = individual :: mutants
  // evaluate population's fitness (hamming distance for each entity)
  let fitness_values_of_population = List.map (fun i -> hd i target) population
  // find fittest individual
  let (fitness_value_of_fittest, index_of_fittest, l) = minl fitness_values_of_population
  let fittest = List.nth population index_of_fittest
  // if fittest reached goal then stop and return individual
  if fitness_value_of_fittest=0 then fittest, nthgeneration
  // else choose fittest and evolve it further
  else evolve fittest (nthgeneration+1) target n mr mp

printf "target sentence [intelligent design]: ";
let ts = System.Console.ReadLine()
let target = cl2il (s2cl ts)

printf "size of population [60]: ";
let n = int_of_string (System.Console.ReadLine())

printf "mutation radius [2]: ";
let mr = int_of_string (System.Console.ReadLine())

printf "mutation probability [0.1]: ";
let mp = float_of_string (System.Console.ReadLine())

// start with random individual
let individual = rli (target.Length)

let (goal, nthgeneration) = evolve individual 0 target n mr mp
printf "generation: %d, current individual: %s\n" nthgeneration (cl2s (il2cl goal));
let str = System.Console.ReadLine()