/*

  Look and say sequence in Picat.


  From http://rosettacode.org/wiki/Look-and-say_sequence
  """
  Sequence Definition

  * Take a decimal number
  * Look at the number, visually grouping consecutive runs of the 
    same digit.
  * Say the number, from left to right, group by group; as how 
    many of that digit there are - followed by the digit grouped. 

  * This becomes the next number of the sequence. 

  The sequence is from John Conway, of Conway's Game of Life fame.

  An example:

   * Starting with the number 1, you have one 1 which produces 11.
   * Starting with 11, you have two 1's i.e. 21
   * Starting with 21, you have one 2, then one 1 i.e. (12)(11) 
     which becomes 1211
   * Starting with 1211 you have one 1, one 2, then two 1's i.e. 
     (11)(12)(21) which becomes 111221 
  """

  Also, see:
    http://en.wikipedia.org/wiki/Look-and-say_sequence
    http://www.research.att.com/~njas/sequences/A005150

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

*/

import util.

main => go.

go => 

   S1 = "1",
   foreach(_I in 1..11) 
      println(S1),
      S1 := runs(S1)
   end,
   println(S1),
   
   nl,
   S2 := "1",
   foreach(_I in 1..20) 
      println(S2),
      S2 := runs(S2)
   end,
   println(S2),

   nl.

go2 => 
   S1 = "1",
   foreach(_I in 1..11) 
      println(S1),
      S1 := runs2(S1)
   end,
   println(S1),

   nl,
   S2 = "1",
   foreach(_I in 1..20) 
      println(S2),
      S2 := runs2(S2)
   end,
   println(S2),

   nl.

% Runs of a string, direct approach
runs(X) = V =>
  S = "",
  Last = X[1], 
  C = 1,
  foreach(I in 2..X.length)
    if X[I] == Last then
       C := C + 1
    else 
       S := S ++ C.to_string() ++ [X[I-1]],
       C := 1,  
       Last := X[I]
    end
  end,
  V = S ++ C.to_string() ++ [Last].


%
% another approach, using same_seq_len/2
% This is slower than runs/1.
%
runs2(L) = V =>
  V = [],
  Pos = 1,
  Len = L.length,
  while (Pos <= Len)
    P = same_seq_len(L,Pos),
    V := V ++ [P.to_string(),L[Pos]].flatten(),
    Pos := Pos + P
  end.


% find the length of the sequence of (same) characters to the right of pos Pos in list L.
same_seq_len(L,Pos) = same_seq_len1(L ++ _, Pos) => 
  Pos <= L.length.

same_seq_len1(L,Pos) = M =>
  P = [I : I in Pos+1..L.length, L[I] != L[Pos]],
  M = cond(P.length > 0, P.first()-Pos, L.length-Pos+1).