/* 

  Evolutionary algorithm in Picat.

   http://rosettacode.org/wiki/Evolutionary_algorithm
   """
   Starting with:
  
    * The target string: 'METHINKS IT IS LIKE A WEASEL'.
    * An array of random characters chosen from the set of upper-case 
      letters together with the space, and of the same length as the 
      target string. (Call it the parent).
    * A fitness function that computes the ‘closeness’ of its argument 
      to the target string.
    * A mutate function that given a string and a mutation rate returns 
      a copy of the string, with some characters probably mutated.
    * While the parent is not yet the target: 
       * copy the parent C times, each time allowing some random 
         probability that another character might be substituted using mutate.
       * Assess the fitness of the parent and all the copies to the 
         target and make the most fit string the new parent, discarding 
         the others.
       * repeat until the parent converges, (hopefully), to the target. 
   """
  
  This solution was inspired the Icon/Unicon solution:
  http://rosettacode.org/wiki/Evolutionary_algorithm#Icon_and_Unicon

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


main => go.

go =>
  _ = random2(),
  Target = "METHINKS IT IS LIKE A WEASEL",
  Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ",
  C = 50, % Population size in each generation
  M = 80,  % Mutation rate per individual in a generation (0.8)

  evo(Target,Chars,C,M),

  nl.


evo(Target,Chars,C,M) => 
  if member(T,Target), not member(T, Chars) then
     printf("The character %w is not in the character set: %w\n", T, Chars);
     halt
  end,

  % first random string
  TargetLen = Target.length,
  Parent = random_chars(Chars,TargetLen),
 
  % 
  % Until current fitness reaches a score of perfect match 
  % with the target string keep generating new populations
  % 
  CurrentFitness = 0,
  Gen = 1,
  while (CurrentFitness < TargetLen)
    println([gen=Gen, currentFitness=CurrentFitness, parent=Parent]),
    Gen := Gen + 1,
    [Parent2,CurrentFitness2] = generation(C,Chars,Target,M,Parent),
    CurrentFitness := CurrentFitness2,
    Parent := Parent2
  end,

  println([gen=Gen, currentFitness=CurrentFitness, parent=Parent]),
  printf("\nFound a perfect fitness (%d) at generation %d\n", CurrentFitness, Gen),
  
  nl.

%
% generate a random string
%
random_chars(Chars, N) = [Chars[my_rand(Len)] : _ in 1..N] =>
  Len = Chars.length.

%
% Increment the fitness for every position in the string 
% S that matches the target
%
fitness(S,Target) = sum([1: I in 1..Target.length, S[I] == Target[I]]).


%
% If a random number between 1 and 100 is inside the 
% bounds of mutation randomly alter a character in the string  
%
mutate(S,M,Chars) = S2 =>
  S2 = copy_term(S),
  if my_rand(100) <= M then 
    S2[my_rand(S.length)] := Chars[my_rand(Chars.length)]
  end.

my_rand(N) = 1+(random() mod N).

%
% Create the next population of parent
%
generation(C,Chars,Target,M,Parent) = [NextParent,NextFitness] =>
  % generate a random population 
  Population = [mutate(Parent,M,Chars) : _ in 1..C],

  % Find the member of the population with highest fitness, 
  NextParent = Parent,
  NextFitness = fitness(Parent,Target),
  foreach(X in Population)
    XF = fitness(X,Target),
    if XF > NextFitness then
      NextParent := X,
      NextFitness := XF
    end
  end.