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.
You are encouraged to solve this task according to the task description, using any language you may know.
- 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
Write a program to generate successive members of the look-and-say sequence.
Ada
<lang ada> with Ada.Text_IO, Ada.Strings.Fixed; use Ada.Text_IO, Ada.Strings, Ada.Strings.Fixed;
function "+" (S : String) return String is
Item : constant Character := S (S'First);
begin
for Index in S'First + 1..S'Last loop
if Item /= S (Index) then
return Trim (Integer'Image (Index - S'First), Both) & Item & (+(S (Index..S'Last)));
end if;
end loop;
return Trim (Integer'Image (S'Length), Both) & Item;
end "+"; </lang> This function can be used as follows: <lang ada> Put_Line (+"1"); Put_Line (+(+"1")); Put_Line (+(+(+"1"))); Put_Line (+(+(+(+"1")))); Put_Line (+(+(+(+(+"1"))))); Put_Line (+(+(+(+(+(+"1")))))); Put_Line (+(+(+(+(+(+(+"1"))))))); Put_Line (+(+(+(+(+(+(+(+"1")))))))); Put_Line (+(+(+(+(+(+(+(+(+"1"))))))))); Put_Line (+(+(+(+(+(+(+(+(+(+"1")))))))))); </lang> Sample output:
11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211 11131221133112132113212221
ALGOL 68
<lang algol>OP + = (STRING s)STRING: BEGIN
CHAR item = s[LWB s];
STRING out;
FOR index FROM LWB s + 1 TO UPB s DO
IF item /= s [index] THEN
out := whole(index - LWB s, 0) + item + (+(s [index:UPB s]));
GO TO return out
FI
OD;
out := whole (UPB s, 0) + item;
return out: out
END # + #;
OP + = (CHAR s)STRING:
+ STRING(s);
print ((+"1", new line)); print ((+(+"1"), new line)); print ((+(+(+"1")), new line)); print ((+(+(+(+"1"))), new line)); print ((+(+(+(+(+"1")))), new line)); print ((+(+(+(+(+(+"1"))))), new line)); print ((+(+(+(+(+(+(+"1")))))), new line)); print ((+(+(+(+(+(+(+(+"1"))))))), new line)); print ((+(+(+(+(+(+(+(+(+"1")))))))), new line)); print ((+(+(+(+(+(+(+(+(+(+"1"))))))))), new line))</lang> Output:
11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211 11131221133112132113212221
AWK
<lang awk>function lookandsay(a) {
s = ""
c = 1
p = substr(a, 1, 1)
for(i=2; i <= length(a); i++) {
if ( p == substr(a, i, 1) ) {
c++
} else {
s = s sprintf("%d%s", c, p)
p = substr(a, i, 1)
c = 1
}
}
s = s sprintf("%d%s", c, p)
return s
}
BEGIN {
b = "1"
print b
for(k=1; k <= 10; k++) {
b = lookandsay(b)
print b
}
}</lang>
C
There are no checks for memory allocation failure or "out of bound" in case more than the worst case happens.
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
char *lookandsay(const char *s) {
int i, c, l, fi; char *r = NULL; char p;
l = strlen(s);
if ( l == 0 ) return NULL;
r = malloc(l*3); /* worst case considered: each number gets a two digit counter */
memset(r, 0, l*3);
p = s[0];
fi = 0;
c = 1;
for(i=1; i < l; i++) {
if ( p == s[i] ) {
c++;
} else {
fi += sprintf(&r[fi], "%d%c", c, p);
c = 1;
p = s[i];
}
}
fi += sprintf(&r[fi], "%d%c", c, p);
r[fi] = 0;
free(s);
return r;
}
int main() {
int i; const char *laf = "1";
printf("%s\n", laf);
for(i=0; i < 10; i++) {
laf = lookandsay(laf);
printf("%s\n", laf);
}
free(laf);
return 0;
}</lang>
C++
<lang cpp>#include <string>
- include <sstream>
std::string lookandsay(const std::string &s) {
std::ostringstream r;
for (unsigned int i = 0; i != s.length(); ) {
unsigned int new_i = s.find_first_not_of(s[i], i+1);
if (new_i == std::string::npos)
new_i = s.length();
r << new_i - i << s[i]; i = new_i; } return r.str();
}
- include <iostream>
int main() {
std::string laf = "1";
std::cout << laf << std::endl;
for (int i = 0; i < 10; i++) {
laf = lookandsay(laf);
std::cout << laf << std::endl;
}
return 0;
}</lang>
C#
<lang csharp>using System; using System.Text; using System.Linq;
class Program {
static string lookandsay(string number)
{
StringBuilder result = new StringBuilder();
char repeat = number[0];
number = number.Substring(1, number.Length-1)+" ";
int times = 1;
foreach (char actual in number)
{
if (actual != repeat)
{
result.Append(Convert.ToString(times)+repeat);
times = 1;
repeat = actual;
}
else
{
times += 1;
}
}
return result.ToString();
}
static void Main(string[] args)
{
string num = "1";
foreach (int i in Enumerable.Range(1, 10)) {
Console.WriteLine(num);
num = lookandsay(num);
}
}
}</lang>
Output:
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
Common Lisp
<lang lisp>(defun compress (array &key (test 'eql) &aux (l (length array)))
"Compresses array by returning a list of conses each of whose car is
a number of occurrences and whose cdr is the element occurring. For instance, (compress \"abb\") produces ((1 . #\a) (2 . #\b))."
(if (zerop l) nil
(do* ((i 1 (1+ i))
(segments (acons 1 (aref array 0) '())))
((eql i l) (nreverse segments))
(if (funcall test (aref array i) (cdar segments))
(incf (caar segments))
(setf segments (acons 1 (aref array i) segments))))))
(defun next-look-and-say (number)
(reduce #'(lambda (n pair)
(+ (* 100 n)
(* 10 (car pair))
(parse-integer (string (cdr pair)))))
(compress (princ-to-string number))
:initial-value 0))</lang>
Example use:
<lang lisp>(next-look-and-say 9887776666) ;=> 19283746</lang>
D
<lang d> import std.stdio; import std.string; void main() {
char[]las = "1";
writefln("%s",las);
las = lookandsay(las);
writefln("%s",las);
las = lookandsay(las);
writefln("%s",las);
las = lookandsay(las);
writefln("%s",las);
las = lookandsay(las);
writefln("%s",las);
}
char[]lookandsay(char[]input) {
char last = input[$-1];
char[]output;
int count = 0;
foreach_reverse(i;input) {
if (i == last) {
count++;
} else {
output = toString(count)~last~output;
count = 1;
last = i;
}
}
output = toString(count)~last~output;
return output;
} </lang>
E
<lang e>def lookAndSayNext(number :int) {
var seen := null
var count := 0
var result := ""
def put() {
if (seen != null) {
result += count.toString(10) + E.toString(seen)
}
}
for ch in number.toString(10) {
if (ch != seen) {
put()
seen := ch
count := 0
}
count += 1
}
put()
return __makeInt(result, 10)
}
var number := 1 for _ in 1..20 {
println(number) number := lookAndSayNext(number)
}</lang>
Forth
<lang forth> create buf1 256 allot create buf2 256 allot buf1 value src buf2 value dest
s" 1" src place
- append-run ( digit run -- )
dest count + tuck c! 1+ c! dest c@ 2 + dest c! ;
- next-look-and-say
0 dest c! src 1+ c@ [char] 0 ( digit run ) src count bounds do over i c@ = if 1+ else append-run i c@ [char] 1 then loop append-run src dest to src to dest ;
- look-and-say ( n -- )
0 do next-look-and-say cr src count type loop ;
10 look-and-say </lang>
Fortran
<lang fortran>module LookAndSay
implicit none
contains
subroutine look_and_say(in, out) character(len=*), intent(in) :: in character(len=*), intent(out) :: out
integer :: i, c character(len=1) :: x character(len=2) :: d
out = ""
c = 1
x = in(1:1)
do i = 2, len(trim(in))
if ( x == in(i:i) ) then
c = c + 1
else
write(d, "(I2)") c
out = trim(out) // trim(adjustl(d)) // trim(x)
c = 1
x = in(i:i)
end if
end do
write(d, "(I2)") c
out = trim(out) // trim(adjustl(d)) // trim(x)
end subroutine look_and_say
end module LookAndSay</lang>
<lang fortran>program LookAndSayTest
use LookAndSay
implicit none
integer :: i
character(len=200) :: t, r
t = "1"
print *,trim(t)
call look_and_say(t, r)
print *, trim(r)
do i = 1, 10
call look_and_say(r, t)
r = t
print *, trim(r)
end do
end program LookAndSayTest </lang>
Haskell
<lang haskell> import Control.Monad (liftM2) import Data.List (group)
-- this function is composed out of many functions; data flows from the bottom up lookAndSay :: Integer -> Integer lookAndSay = read -- convert digits to integer
. concatMap -- concatenate for each run,
(liftM2 (++) (show . length) -- the length of it
(take 1)) -- and an example member
. group -- collect runs of the same digit
. show -- convert integer to digits
-- less comments lookAndSay2 :: Integer -> Integer lookAndSay2 = read . concatMap (liftM2 (++) (show . length)
(take 1))
. group . show
-- same thing with more variable names
lookAndSay3 :: Integer -> Integer
lookAndSay3 n = read (concatMap describe (group (show n)))
where describe run = show (length run) ++ take 1 run
main = mapM_ print (iterate lookAndSay 1) -- display sequence until interrupted </lang>
J
Solution:
las=.(,,@((#,{.);.1~1,2~:/\])&.(10x&#.^:_1)@:{:)@]^:[
Example:
10 las 1 1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211 11131221133112132113212221
Note the result is an actual numeric sequence (cf. the textual solutions given in other languages).
Java
<lang java5>public static String lookandsay(String number){ StringBuilder result= new StringBuilder();
char repeat= number.charAt(0); number= number.substring(1) + " "; int times= 1;
for(char actual: number.toCharArray()){ if(actual != repeat){ result.append(times + "" + repeat); times= 1; repeat= actual; }else{ times+= 1; } } return result.toString(); }</lang> Testing: <lang java5>public static void main(String[] args){ String num = "1";
for (int i=1;i<=10;i++) { System.out.println(num); num = lookandsay(num); } }</lang> Output:
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
M4
Using regular expressions:
<lang M4> divert(-1) define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`las',
`patsubst(`$1',`\(\(.\)\2*\)',`len(\1)`'\2')')
define(`v',1)
divert
for(`x',1,10,
`v
define(`v',las(v))')dnl v </lang>
Mathematica
Custom Functions: <lang Mathematica>
RunLengthEncode[x_List]:=(Through[{First,Length}[#]]&)/@Split[x]
LookAndSay[n_,d_:1]:=NestList[Flatten[Reverse/@RunLengthEncode[#]]&,{d},n-1]
</lang> If second argument is omitted the sequence is started with 1. Second argument is supposed to be a digits from 0 to 9. If however a larger number is supplied it will be seen as 1 number, not multiple digits. However if one wants to start with a 2 or more digit number, one could reverse the sequence to go back to a single digit start. First example will create the first 13 numbers of the sequence starting with 1, the next example starts with 7: <lang Mathematica>
FromDigits /@ LookAndSay[13] // Column FromDigits /@ LookAndSay[13, 7] // Column
</lang> gives back: <lang Mathematica> 1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211 11131221133112132113212221 3113112221232112111312211312113211 1321132132111213122112311311222113111221131221
7 17 1117 3117 132117 1113122117 311311222117 13211321322117 1113122113121113222117 31131122211311123113322117 132113213221133112132123222117 11131221131211132221232112111312111213322117 31131122211311123113321112131221123113111231121123222117 </lang>
MAXScript
fn lookAndSay num =
(
local result = ""
num += " "
local current = num[1]
local numReps = 1
for digit in 2 to num.count do
(
if num[digit] != current then
(
result += (numReps as string) + current
numReps = 1
current = num[digit]
)
else
(
numReps += 1
)
)
result
)
local num = "1"
for i in 1 to 10 do
(
print num
num = lookAndSay num
)
Metafont
<lang metafont>vardef lookandsay(expr s) = string r; r := ""; if string s:
i := 0;
forever: exitif not (i < length(s));
c := i+1;
forever: exitif ( (substring(c,c+1) of s) <> (substring(i,i+1) of s) );
c := c + 1;
endfor
r := r & decimal (c-i) & substring(i,i+1) of s;
i := c;
endfor
fi r enddef;
string p; p := "1"; for el := 1 upto 10:
message p; p := lookandsay(p);
endfor
end</lang>
Perl
<lang perl>sub lookandsay {
my $str = shift; $str =~ s/((.)\2*)/length($1) . $2/ge; return $str;
}
my $num = "1"; foreach (1..10) {
print "$num\n"; $num = lookandsay($num);
}</lang>
PHP
<lang php><?php function lookandsay($str) {
return preg_replace('/(.)\1*/e', 'strlen($0) . $1', $str);
}
$num = "1"; foreach (range(1,10) as $i) {
echo "$num\n"; $num = lookandsay($num);
} ?></lang>
PowerShell
<lang powershell>function Get-LookAndSay ($n = 1) {
$re = [regex] '(.)\1*'
$ret = ""
foreach ($m in $re.Matches($n)) {
$ret += [string] $m.Length + $m.Value[0]
}
return $ret
}
function Get-MultipleLookAndSay ($n) {
if ($n -eq 0) {
return @()
} else {
$a = 1
$a
for ($i = 1; $i -lt $n; $i++) {
$a = Get-LookAndSay $a
$a
}
}
}</lang> Output:
PS> Get-MultipleLookAndSay 8 1 11 21 1211 111221 312211 13112221 1113213211
Python
<lang python>def lookandsay(number):
result = ""
repeat = number[0] number = number[1:]+" " times = 1
for actual in number:
if actual != repeat:
result += str(times)+repeat
times = 1
repeat = actual
else:
times += 1
return result
num = "1"
for i in range(10):
print num num = lookandsay(num)</lang>
Functional
<lang python>>>> from itertools import groupby >>> def lookandsay(number): return .join( str(len(list(g))) + k for k,g in groupby(number) )
>>> numberstring='1' >>> for i in range(10): print numberstring numberstring = lookandsay(numberstring)</lang>
Output:
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
Using regular expressions:
<lang python>import re
def foo(match):
return str(len(match.group(0))) + match.group(1)
def lookandsay(str):
return re.sub(r'(.)\1*', foo, str)
num = "1" for i in range(10):
print num num = lookandsay(num)</lang>
R
Returning the value as an integer limits how long the sequence can get, so the option for integer or character return values are provided. <lang R> look.and.say <- function(x, return.an.int=FALSE) {
#convert number to character vector xstr <- unlist(strsplit(as.character(x), "")) #get run length encoding rlex <- rle(xstr) #form new string odds <- as.character(rlex$lengths) evens <- rlex$values newstr <- as.vector(rbind(odds, evens)) #collapse to scalar newstr <- paste(newstr, collapse="") #convert to number, if desired if(return.an.int) as.integer(newstr) else newstr
} </lang> Example usage. <lang R> x <- 1 for(i in 1:10) {
x <- look.and.say(x) print(x)
} </lang>
Ruby
<lang ruby>def lookandsay(str)
str.gsub(/(.)\1*/) {$&.length.to_s + $1}
end
num = "1" 10.times do
puts num num = lookandsay(num)
end</lang>
Smalltalk
<lang smalltalk>String extend [
lookAndSay [ |anElement nextElement counter coll newColl|
coll := (self asOrderedCollection).
newColl := OrderedCollection new.
counter := 0.
anElement := (coll first).
[ coll size > 0 ]
whileTrue: [
nextElement := coll removeFirst.
( anElement == nextElement ) ifTrue: [
counter := counter + 1.
] ifFalse: [
newColl add: (counter displayString). newColl add: (anElement asString). anElement := nextElement. counter := 1.
]
].
newColl add: (counter displayString).
newColl add: (anElement asString).
^(newColl join)
]
].
|r| r := '1'. 10 timesRepeat: [
r displayNl. r := r lookAndSay.
]</lang>
Tcl
<lang tcl>proc lookandsay n {
set new ""
while {[string length $n] > 0} {
set char [string index $n 0]
for {set count 1} {[string index $n $count] eq $char} {incr count} {}
append new $count $char
set n [string range $n $count end]
}
interp alias {} next_lookandsay {} lookandsay $new
return $new
}
puts 1 ;# ==> 1 puts [lookandsay 1] ;# ==> 11 puts [next_lookandsay] ;# ==> 21 puts [next_lookandsay] ;# ==> 1211 puts [next_lookandsay] ;# ==> 111221 puts [next_lookandsay] ;# ==> 312211</lang>
Ursala
The look_and_say function returns the first n results by iterating the function that maps a given sequence to its successor. <lang Ursala>#import std
- import nat
look_and_say "n" = ~&H\'1' next"n" rlc~&E; *= ^lhPrT\~&hNC %nP+ length
- show+
main = look_and_say 10</lang> output:
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
Vedit macro language
This implementation generates look-and-say sequence starting from the sequence on cursor line in edit buffer. Each new sequence is inserted as a new line. 10 sequences are created in this example.
<lang vedit> Repeat(10) {
BOL
Reg_Empty(20)
While (!At_EOL) {
Match("(.)\1*", REGEXP+ADVANCE)
Num_Str(Chars_Matched, 20, LEFT+APPEND)
Reg_Copy_Block(20, CP-1, CP, APPEND)
}
Ins_Newline Reg_Ins(20)
} </lang>
Output:
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211 11131221133112132113212221