/* 

  Fibonacci word in Picat.

  http://rosettacode.org/wiki/Fibonacci_word
  """
  The Fibonacci Word may be created in a manner analogous to the Fibonacci 
  Sequence as described here:
    Define F_Word1 as 1; 
    Define F_Word2 as 0; 
    Form F_Word3 as F_Word2 concatenated with F_Word1 i.e "01" 
    Form F_Wordn as F_Wordn-1 concatenated with F_wordn-2 

  For this task we shall do this for n = 37. You may display the first few but 
  not the larger values of n, doing so will get me into trouble with them what be (again!).

  Instead create a table for F_Words 1 to 37 which shows:

    - The number of characters in the word 
    - The word's Entropy. 
  """

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

*/


% import util.
% import cp.


main => go.

go =>
  foreach(N in 1..37)
     F = fib(N),
     E = entropy(F),
     if N <= 10 then
       printf("%3d %10d %0.16f %w\n",N,length(F),E,F)
     else
       printf("%3d %10d %0.16f\n",N,length(F),E)     
     end
  end,
  nl.

table
fib(1) = "1".
fib(2) = "0".
fib(N) = fib(N-1) ++ fib(N-2).

% probabilities of each element/character in L
% (See http://hakank.org/picat/entropy.pi )
entropy(L) = Entropy => 
  Len = L.length,
  Occ = new_map(),
  foreach(E in L)
    Occ.put(E, Occ.get(E,0) + 1)
  end,
  Entropy = -sum([P2*log2(P2) : _C=P in Occ, P2 = P/Len]).