Look and say sequence [duplicate]

Question

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.

Answer 1

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
$).?.)*(*

Answer 2

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)

Answer 3

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]

Answer 4

PHP 67 bytes

<?for(;~Î/$s=preg_filter(~Ð×ÑÖ£ÎÕК,~£ÏÚÆУÎßÑߣÎ,$s)?:~Îõ;)echo$s;

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 20^th 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

Answer 5

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

Answer 6

Haskell, 116

import List
l=length
f=[l[f]]:map(((\x->[l x,head x])=<<).group)f
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".

Answer 7

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;}}

Answer 8

Perl (73)

Named capture buffers rock.

perl -le '$_++;$c=a;$r="(?<f>.)\\$_*";print,s/$r/length($&).$+{f}/eg while$c++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 while$c++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".

}

Answer 9

Mathematica 62

x=a/a;Grid@NestList[Join@@({Length@#,#〚x〛}&/@Split@#)&,{x},#]&

Answer 10

Perl, 94 bytes

$_=$w=cos"a";for$a($w..(ord('<')-ord('('))){print"$_ ";eval"s/(\\d)\\$w*/length(\$&).\$$w/ge"}

Answer 11

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!

Answer 12

Haskell, 109 characters

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

Answer 13

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)))

Answer 14

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.

Answer 15

K, 62

{,/,'[;?:'f]@$#:'f:(&~~':x)_x}\["J"$h,$"i"$"\t";,h:*$"i"$"\r"]

Answer 16

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))

Answer 17

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}

Answer 18

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+$+}}

Answer 19

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.

Answer 20

Lua, 138 bytes

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

Answer 21

Python 2.x

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

Answer 22

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+$+}}

Answer 23

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;
        }
    }
}

Answer 24

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"
...

Answer 25

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
 ...