/*
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).