Look and say sequence [duplicate]

This question already has an answer here:

The look and say sequence is a basic form of run length encoding.

The sequence starts with the number 1 and each additional number encodes the number of digits that are repeated before each digit sequence. For example, "1" becomes "11", because there is one "1". Then "11" becomes "21", and so on.

The first few numbers are 1, 11, 21, 1211, 111221, 312211 and 13112221.

Write a program to output the first 20 numbers.

The catch is you may not use any number in your program, including other bases than base 10. You can only use letters and symbols. Also, the program can't directly contain the numbers (or fetch them from a web server, or from a file); it must actually compute them.

I will accept the answer which works and is the shortest; in case of a tie, vote counts will decide, and in case of a tie there, the winner will be chosen randomly.

marked as duplicate by Mego♦, Conor O'Brien, Adnan, GamrCorps, catFeb 4 '16 at 3:06

• By "number" do you mean "character 0-9" or "numeric literal"? – Peter Taylor Apr 28 '11 at 15:18
• @Peter Taylor: I suppose the former. It would be way too easy otherwise. – Lowjacker Apr 28 '11 at 15:22
• As per the FAQ, all questions on this site should have an objective primary winning criterion. – Nabb Apr 28 '11 at 15:32
• Previously on Stack Overflow as Code Golf: Morris Sequence. – dmckee Apr 28 '11 at 16:30
• @Thomas: My inclination here is to close this as based on too subjective a criterion. Discussion on meta that may be relevant. – dmckee Apr 28 '11 at 16:33

Golfscript, 44 43 40 41 38 37 36 chars

Since the criterion now requires golfing, here's the golfed version:

!:^;n).+{[^\{^$^$={;\)}^if\}*].n@}*;


The original, ungolfed, version actually dealt with strings rather than abusing Golfscript's formatting conventions for dumping the stack to stdout at program termination:

# Assumes nothing passed to stdin, so input length is zero
,):$''+ { .puts # Convert to an array of [count char count char ...] [$\{.@.@={;\)\}{$\}if}*] # Convert to an array of [[count char] [count char] ...] )/ # Form the next string ''\{(@\+\+}/ } # Nineteen times. There are a *lot* of ways of generating the number nineteen # but I like this one ).?.)*(*  • There's at least 5 characters to be saved -- ! for generating 1, n for generating 19, and another 3 characters in the middle ;) – Nabb Apr 30 '11 at 10:14 • @Nabb, I haven't got time to figure out the 3 in the middle right now, but thanks for the tips about ! and n. – Peter Taylor Apr 30 '11 at 10:31 Perl (60 characters) perl -e'print,s#(.)\g{y}*#&=~y///c.^N#egfor(++y./)x(^F.|)'  Look ma, no numbers. The algorithm is rather similar to the "chinese perl goth's" solution above with a few golf tweaks: • ^F.| == "20" == 20 in numeric context • ^N == last bracket matched • for loop over (1)x20 is much shorter than trying to use a range • ++y == 1 and use it both as a backreference \g{y} & to seed the generator • length is more cheaply spelt y///c I spent a bunch of time trying alternative short ways to write length() before settling on the usual y///c - numbers of the form x = nnnn...n (where there are k digits n) have a lovely property that k = x mod 9 / n. So you could write it as & % 9 / ^N. But now you have to get rid of the 9. (Fun to golf again - thanks to MtvViewMark for roping me back) Mathematica 88 82 t=Flatten;x=b/b; g@n_:=Grid@NestList[t@Map[Reverse,t[Tally/@Split@#,x],x]&,{x},n-x]  Usage g[9]  PHP 67 bytes <?for(;~Î/s=preg_filter(~Ð×ÑÖ£ÎÕÐš,~£ÏÚÆÐ£ÎßÑß£Î,s)?:~Îõ;)echos;  The above may be copied directly, and saved in an ansi format. Alternatively, it may generated with the following script, and then piped to a file: <?="<?for(;~\xce/$s=preg_filter(~\xd0\xd7\xd1\xd6\xa3\xce\xd5\xd0\x9a,~\xa3\xcf\xda\xc6\xd0\xa3\xce\xdf\xd1\xdf\xa3\xce,$s)?:~\xce\xf5;)echo$s;";


The script terminates when the current value of the series, $s, becomes larger than the largest representable floating point number, approximately 1e308. This quite coincidentally occurs just after the 20th value. Sample usage: $ php look-and-say.php
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211

• Coincidence? I think not! :P – WorldSEnder Aug 13 '14 at 0:34

import List
l=length
main=mapM putStrLn$map(show=<<)$take(l['a'..'t'])f


The trick of using ['a'..'t'] to extract the right number of elements was lifted from MtnViewMark's solution. Obviously superior to my original choice of "a really long string".

C: 213 characters

main(){char*a,*b=calloc(' ',' '),*c=calloc(' ',' '),*d,*e,*f;*b='Q'-' ';for(a="                    ";*a;++a){printf("%s\n",b);e=f=b;d=c;while(*e){while(*f==*e){++f;}d+=sprintf(d,"%d%c",f-e,*e);e=f;}e=b;b=c;c=e;}}

• Could you replace the space characters with 32? – Thomas O Jan 24 '13 at 22:49
• @ThomasO: You could, and there's other stuff you could reduce it by a bit further. I was just being obscure. – Skizz Jan 25 '13 at 8:35

Perl (73)

Named capture buffers rock.

perl -le '$_++;$c=a;$r="(?<f>.)\$_*";print,s/r/length(&).+{f}/eg whilec++ne u'  A bit of explanation: _++; incrementing _ which is undefined at the start, to make it contain 1. c=a; - abusing perl's barewords in a horrible way to make c contain 'a'. r="(?<f>.)\$_*" - constructing a regular expression matching repeated characters. normally i'd write it as (.)\1* but I can't use digits, so i've declared a capture buffer with the name of f. this also could be written as (?<f>.)\k<f>* but it'll make the regex one char longer, so I've used \$_ which evaluates to \1. print,s/r/length(&).+{f}/eg whilec++ne u Ungolfed: while(c++ne u) { - taking advantage of the fact that it's possible to increment strings in perl - incrementing a scalar containing 'a' will make it contain 'b', and so on - so the loop will go from 'a' to 'u' print; - print _ s/r/length(&).+{f}/eg - operating on _, replace whatever is matched by the previously constructed regular expression (repeated characters) by its length, followed by first char of it. & means the whole match, +{f} means "a named capture buffer with a name f". } • Some of these tricks are costing you more than they bring. Using \k<f> would let you not save the regex in a variable. Using forc(a..u) instead of c=a; plus whilec++ne u is shorter. – Gilles Aug 24 '13 at 16:50 Javascript, 105 z=c=+[];r=x="";s=i=-~c+r;for(e=-~s+r+c;e--;){alert(s);c=z;for(x=r;y=s[c++];++i)y!=s[c]&&(x+=i+y,i=z);s=x}  Output (change alert to console.log) 1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211 11131221133112132113212221 3113112221232112111312211312113211 1321132132111213122112311311222113111221131221 11131221131211131231121113112221121321132132211331222113112211 311311222113111231131112132112311321322112111312211312111322212311322113212221 132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211 11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221 31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211 1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221 11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211  Mathematica 62 x=a/a;Grid@NestList[Join@@({Length@#,#〚x〛}&/@Split@#)&,{x},#]&  Perl _=w=cos"a";fora(w..(ord('<')-ord('('))){print"_ ";eval"s/(\\d)\$w*/length($&).$$w/ge"}


C++

By Chuck Morris

/*  This implements the power of
**    C H U C K  M O R R I S .
*/

#include <iostream>
#include <vector>

/*
**  Deep within the murks
**  Of an assembly programmer's heart
**  Lies an ancient hatred
**  Of recursion
**
**  Yet a true C++ programmer
**  Can appreciate the beauty
**  And elegance
**  Which the following manifests
*/
std::string stringpp(std::string sz, size_t last_digit=(size_t)'\0')
{
std::string bak = sz;

if(last_digit < sz.length())
{
char nextnum = sz[sz.length() - (size_t)'\x01' - last_digit];
++nextnum;

if(nextnum < ':')
{
sz = bak.substr((size_t)'\0', bak.length() - (size_t)'\x01' - last_digit);
sz += nextnum;
if(last_digit)
sz += bak.substr(bak.length() - last_digit, last_digit);
}
else
{
nextnum = '0';

sz = bak.substr((size_t)'\0', bak.length() - (size_t)'\x01' - last_digit);
sz += nextnum;
if(last_digit)
sz += bak.substr(bak.length() - last_digit, last_digit);

sz = stringpp(sz, last_digit + (size_t)'\x01');
}
}
else
{
sz = "1";
sz += bak;
}

return(sz);
}

class ChuckMorris
{
private:
std::string sz;
public:
ChuckMorris() { sz = "1"; }
void next();
std::string get();
};

void ChuckMorris::next()
{
std::string num;

std::string bak = sz;
sz = "";

for(size_t i = (size_t)'\0'; i < bak.length();)
{
num = "0";
size_t i2 = i;
for(; (i2 < bak.length()) && (bak.at(i) == bak.at(i2)); ++i2)
num = stringpp(num);
sz += num;
sz += bak.substr(i, 1);
i = i2;
}
}

std::string ChuckMorris::get()
{
return(sz);
}

int main(int argc, char* argv[])
{
ChuckMorris chucky;

// std::cout << stringpp("999").c_str() << std::endl;

for(char chucks = '\0'; chucks < '\x14';)
{
std::cout << chucky.get().c_str();
chucky.next();
++chucks;
if(chucks != '\x14')
std::cout << ", ";
}

std::cout << std::endl;

return(0);
}

/*  And some elvish for elegance:
**  A Elbereth Gilthoniel
**  silivren penna míriel
**  o menel aglar elenath!
**  Na-chaered palan-díriel
**  o galadhremmin ennorath,
**  Fanuilos, le linnathon
**  nef aear, sí nef aearon!
*/


This is an elegance only Chuck Morris himself can achieve with C++ code. He coded it (for free) in less than zero seconds, while sleeping.

It may not be as "elegant" as Golfscript/others, but it does everything... in a statically typed language!

• Having a crappy/clumsy set of builtins for manipulating basic types is nothing to do with statically typed languages. Seems to be a common omission in statically typed languages though for some reason. – gnibbler Apr 29 '11 at 6:00
• @gnibbler <s>I could have converted to number (for stringpp() to be a lot simpler), added, converted to string, but I don't think that's allowed in the challenge.</s> Hmmm... Oh well, it makes my code more (or less) elegant. :) – Mateen Ulhaq Apr 29 '11 at 6:03
• You used a lot of numbers in this. – Thomas O Apr 29 '11 at 10:28
• @Thomas Language requirements! :D (...And they're chars.) – Mateen Ulhaq Apr 29 '11 at 16:05
• you're just not trying hard enough! – Skizz May 3 '11 at 15:14

Python

from itertools import groupby
s=len(' ')
for x in'                    ':
print s
s=''.join(i+len(list(j)) for i,j in groupby(s))


and a version without the hacky strings

from math import *
from itertools import groupby
s=int(log(e))
for x in s*int(e**pi-e):
print s
s=''.join(i+len(list(j)) for i,j in groupby(s))


note that e**pi-pi is very close to 20 (19.99909997918947) but slightly smaller, so it's no good to use int with

Lua 138 chars

p=#' 'm=p c=''..p f=#'    'for k=p,f*f+f do n=''o=#n while o<#c do q=o+p l=c:sub(q,q)i,o=c:find(l.."+",q)n=n..o-i+p..l end c=n print(n)end


import List
q=show.length
l=q" ":map((>>=(\a->q a++[head a])).group)l
main=mapM_(putStrLn.snd)$zip['a'..'t']l  Not a digit in sight, not even as a character in a string! Prints the first 20 numbers, one per line. • Edit (118 -> 109) used suggestion of length to generate the initial 1, then factored out show.length • Might I suggest length[l] in place of fromEnum EQ? – user1011 Apr 29 '11 at 8:32 Clojure, 251 chars (def z~(count ""))(def t(read-string(str z "xa")))(println(take(+ t t)(iterate(fn[x](#(reduce(fn[a b](+ b(* a t)))%)(mapcat(juxt count first)(partition-by identity(#(loop[u %,d()](if(zero? u)(seq d)(recur(quot u t)(cons(mod u t)d))))x)))))(inc z))))  Heres the ungolfed version. This sure was fun to figure out. (def z ~(count "")) (def ten (read-string (str z "xa"))) (defn num->digits [n] " Takes a number and returns a sequence containing its digits in ascending order e.g., 123 -> (1 2 3)" (loop [num n, digits ()] (if (zero? num) (seq digits) (recur (quot num ten) (cons (mod num ten) digits))))) (defn digits->num [seq] " Takes a sequence of digits and returns the number they represent e.g., (1 2 3) -> 123 " (reduce (fn [a b](+ b (* a ten))) seq)) (defn look-seq [n] " Returns a sequence containing the look-say representation for n" (digits->num (mapcat (juxt count first) (partition-by identity (num->digits n))))) (defn look-n-say " Returns a lazy sequence representing Conway's look-and-say sequence starting at n" ([] (look-n-say (inc z))) ([n] (iterate look-seq n))) (println (take (+ ten ten) (look-n-say)))  Clojure, 172 characters (let[o(*)t(+ o o)f(+ t t)p partial c comp](dorun(take(+(Math/pow t f)f)(map(c println(p apply str))(iterate(c(p mapcat(juxt count first))(p partition-by identity))[o])))))  This is using the trick that the multiplicative identity is 1; therefore, Clojure has (*) evaluate to 1. I let this be o (one), and then let t (two) be (+ o o), and let f (four) be (+ t t). I also alias partial and comp to one-letter names (hurrah for first class functions!). I then use math to find the number 20, so I can use it for taking this number of elements from an infinite sequence of look-and-say strings: 2^4 + 4 = 20. The actual algorithm for finding look-and-say numbers, unobfuscated, looks like this: (iterate (comp (partial mapcat (juxt count first)) (partial partition-by identity)) [1])  The above produces the infinite sequence of sequences of digits corresponding to look-and-say numbers. K, 62 {,/,'[;?:'f]@$#:'f:(&~~':x)_x}\["J"$h,$"i"$"\t";,h:*$"i"$"\r"]  JavaScript (102 characters) Requires support for arrow functions. This will work unmodified in JavaScript Shell or otherwise when print is changed to alert. for(j=k=l=-~'',j=++j+j,j*=++j;j--;)print(k=(''+k).replace(RegExp('(.)\\'+l+'*','g'),(a,b)=>a.length+b))  • You have a 1 in your code... – mellamokb May 2 '11 at 17:38 • @mellamokb: Fixed at a cost of 18 characters. – PleaseStand May 2 '11 at 19:57 Ruby 1.9, 119 chars num = "#{?b.ord-?a.ord}" one = num.to_i limit = ?U.ord-?A.ord loop { puts num num = num.gsub(/(?<digit>.)\k<digit>*/) {$&.size.to_s + $+ } break if (limit -= one) == one - one }  A golfed version: k="#{?b.ord-?a.ord}" j=k.to_i i=?U.ord-?A.ord loop{puts k k=k.gsub(/(?<d>.)\k<d>*/){$&.size.to_s+$+} (i-=j)==j-j&&exit}  • Character count? – proud haskeller Aug 12 '14 at 20:25 CJam, 11 bytes X{NX$se}J*


Test it here.

This answer does not compete as CJam is much younger than this challenge (and e is a fairly recent feature). However, I thought the solution is really neat so I wanted to add it for completeness.

Explanation

X     e# Push 1 as the start of the sequence.
{     e# Repeat this block 19 times...
N   e#   Push a linefeed as a separator.
X$e# Copy the last value (which will be either a number or a nested array of numbers. s e# Convert it to a string, which will flatten the value if it's an array. e e# Run-length encode the string. }J*  This works because e happens to use the required order of run-length and value, and because the look-and-say sequence will never contain any "digits" greater than 3, so that we don't lose any information by simply flattening the RLE-result into a single string. Ruby 2.0, 82 characters. I took Lowjacker's regex and put it into this one-liner. (?(.ord>>p(n=??.size)).times{puts n=n.to_s.gsub(/(?<d>.)\k<d>*/){$&.size.to_s+$+}}  C# - 209 using System.Linq;class P{static void Main(){int i='a',N='b'-i,O=i-i, x=O;var C=N+"";while(i++<'u'){System.Console.WriteLine(C);var n="";(C+ " ").Aggregate((c,d)=>{x++;if(d!=c){n+=x+""+c;x=O;}return d;});C=n;}}}  Exploits the fact that char is implicitly convertible to int, and since a string is an IEnumerable collection of chars, I used the LINQ Aggregate() method to do the work. using System.Linq; class P { static void Main() { int i = 'a', // start loop counter at the int value for 'a' N = 'b' - i, // N is now literally 1 ('b' - 'a') O = i - i, // O is now literally 0 (1 - 1) x = O; // number counter var C = N + ""; // C is the current string. start with "1". while (i++ < 'u') // if 'a' is 1, 'u' is 20 { // print the current string System.Console.WriteLine(C); var n = ""; // this will be our next string // aggregate the current string (C + " ").Aggregate((c, d) => { // increment the number counter x++; if (d != c) { // when a different number is found, update the next string n += x + "" + c; // reset the count x = O; } // the current number is passed back in as the aggregate (c) return d; }); // move next to current C = n; } } }  Haskell, 103/114 characters this solution prints the numbers inside lists, like so: [1] [1,1] [2,1] ...  code: import Data.List l=length main=mapM print$take(l['a'..'t'])$iterate((>>= \v->[l v,head v]).group)[l[l]]  this version prints them outside lists, but has more characters: import Data.List l=length main=mapM(print.(>>=show))$take(l['a'..'t'])$iterate((>>= \v->[l v,head v]).group)[l[l]]  output: "1" "11" "21" ...  • How do you use this? Could not find module ‘List’ It is a member of the hidden package ‘haskell98-2.0.0.3’. – nyuszika7h Jan 8 '15 at 18:25 • @nyuszika7h sorry, should change it to Data.List – proud haskeller Jan 8 '15 at 18:31 Ruby 1.9+, 76 characters Like @daniero, I shamelessly stole @Lowjacker's regex. s=$-W.to_s
"\cT".ord.times{puts s;s.gsub!(/(?<d>.)\k<d>*/){$&.size.to_s+$+}}


K, 46 bytes

(-/_ic'"TA"){,/+(#:;*:)@'\:_[&o,~=':x]x}\,o:#


A very old question, but I thought I could improve on the existing K solution.

The phrase -/_ic'"ta" generates the constant 19- the difference between the ASCII characters "t" and "a". I also need the constant 1, so I use the length of the empty symbol. Without these contortions, the program would look like the following:

19{,/+(#:;*:)@'\:_[&1,~=':x]x}\,1


Only 33 bytes, and pretty easy to follow by K standards. For each term of the sequence, find the starting index of each run of identical values (&1,~=':x), slice the sequence into runs (_), and apply count (#:) and first (*:) to each element of the resulting sequence. (@'\:) Take the transpose (+) of that result to reshape it into a list of (count,item) tuples and then finally raze (,/) into a flat list.

In action:

  (-/_ic'"TA"){,/+(#:;*:)@'\:_[&o,~=':x]x}\,o:#
(,1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
1 1 1 3 1 2 2 1 1 3 3 1 1 2 1 3 2 1 1 3 2 1 2 2 2 1
...

• Is this k5? I can't get it to run in k4, ic is undefined There's a k4 solution for 29 bytes that includes numbers 19{,/{(#x),*x}'(&~~':x)_x}\,1 – tmartin Jun 25 '15 at 16:20
• It is k2. It also works correctly in Kona. _ic is a builtin for converting characters into integers. In k5 it would be even easier, since characters will naturally coerce to numbers- you could just do -/"ta". – JohnE Jun 25 '15 at 18:03
• Also, the k4 solution you included is a slight improvement, but on Kona/K2 it requires tweaks- _x needs to be altered to _ x to avoid confusing "cut x" with a reserved variable called _x, and "cut" needs an initial 0 in its index list. Works just fine in k5! Combining your ideas with mine, you can get a 36 character k5 solution, but k5 is too new to be an official answer. – JohnE Jun 25 '15 at 18:10