views:

2169

answers:

37

The Challenge

The shortest code by character count that will output the Morris Number Sequence. The Morris Number Sequence, also known as the Look-and-say sequence is a sequence of numbers that starts as follows:

1, 11, 21, 1211, 111221, 312211, ...

You can generate the sequence infinitely (i.e, you don't have to generate a specific number).

I/O Expectations

The program doesn't need to take any input (but bonus points for accepting input and thereby providing the option to start from any arbitrary starting point or number). At the very least your program must start from 1.

Output is at the very least expected to be the sequence:

1
11
21
1211
111221
312211
...

Extra Credit

If you're going for extra credit, you would need to do something like this:

$ morris 1
1
11
21
1211
111221
312211
...

$ morris 3
3
13
1113
3113
132113
...
+3  A: 
Glenn Nelson
Language? (I assume Java)
Platinum Azure
Please explore other topics tagged [code-golf](http://stackoverflow.com/questions/tagged/code-golf) to learn what they meant with "code-golf".
BalusC
Man, I wish my IB curriculum included CS.
sdolan
@Paltinum it is Java
Glenn Nelson
@sdolan it's been an option in the curriculum for well over a decade (12+ years ago when I got my IB Diploma) - I assume it wasn't removed any time between then and now
Daniel DiPaolo
@Daniel Not all schools offer it.
Glenn Nelson
@Daniel: I was in the the inaugural class @ my high school (~ 5 years ago). The only option we had was Spanish vs Latin for our FL requirement.
sdolan
I feel the comment by BalusC might be a little harsh: this solution isn't half bad (code golfing in Java is hard) although it probably could be made shorter....
ChristopheD
@ChristopheD: the OP edited the answer afterwards :) Check [edit history](http://stackoverflow.com/revisions/12dd462c-5239-4a0b-bf7c-ed29538e04c3/view-source) for the original answer. All variables are full out written and whitespace is kept. How Golfy was that? Anyway, for a shorter solution, see [my answer](http://stackoverflow.com/questions/3908513/code-golf-morris-sequence/3919936#3919936).
BalusC
@BalusC: ah ok, that explains a lot (the initial revision didn't look that golfed)...
ChristopheD
+4  A: 

Here goes my implementation (in Prolog):

Prolog with DCGs (174 chars):

m(D):-write(D),nl,m(1,write(D),T,[nl|T],_).
m(C,D,T)-->[D],{succ(C,N)},!,m(N,D,T).
m(C,D,[G,D|T])-->[N],{G=write(C),G,D,(N=nl->(M-T-O=0-[N|R]-_,N);M-T-O=1-R-N)},!,m(M,O,R).

Plain vanilla prolog, code much more readeable (225 chars):

m(D):-
  ((D=1->write(D),nl);true),
  m([], [1,D]).

m([], [C,D|M]):-
  write(C), write(D),nl,
  reverse([D,C|M],[N|X]),
  !,
  m([N|X],[0,N]).
m([D|T], [C,D|M]):-
  succ(C,N),
  !,
  m(T,[N,D|M]).
m([Y|T],[C,D|M]):-
  write(C), write(D),
  !,
  m(T,[1,Y,D,C|M]).

To output the Morris sequence: m(D). where D is the 'starting' digit.

gusbro
I was going to up vote but I hate prolog so much I just couldn't do it.
rerun
+10  A: 

Perl, 46 characters

$_=1;s/(.)\1*/$&=~y!!!c.$1/ge while print$_,$/

Extra credit, 51 characters:

$_=pop||1;s/(.)\1*/$&=~y!!!c.$1/ge while print$_,$/
Hasturkun
Note to self: Learn regex special variables. However, I can think of a few things you can do. One, `while(1){...}` can be shortened to `{...;redo}` (-3 characters). Two, both the last statement in a block and blocks themselves do not need semicolons after them (-2 characters).
Platinum Azure
Also worth looking into: `my$n` instead of `$n=""`? I believe lexically scoping to the block will effectively undefine it every time (and of course using operator `.=` will concatenate to empty string if the variable is `undef`). You save one character that way, but I don't know if semantically it will work 100%. Also, you can change the inline while from `while(s///)` to `while s///`, saving one character.
Platinum Azure
You can remove two semicolons, use for(;;), and sentence modifiers (while at end of sentence) don't need parenthesis, for 4 chars less.
ninjalj
@ninjalj: As per my comments above, you can just use redo in a block for the same effect, saving two more characters. :-)
Platinum Azure
Thanks for the suggestions, updated
Hasturkun
Still one character too many. As said above, sentence modifiers don't need no parenthesis.
ninjalj
Also, the ^ anchor isn't needed, s/// remembers the last character it examined.
ninjalj
This one doesn't print "1" (or the input value) on the first line of output.
Plutor
Plutor
@Plutor: You're right, I'll correct that
Hasturkun
+6  A: 

Python, 102 115

Whitespace is supposed to be tabs:

x='1'
while 1:
    print x
    y=d=''
    for c in x+'_':
        if c!=d:
            if d:y+=str(n)+d
            n,d=0,c
        n+=1
    x=y

E.g.:

$ python morris.py | head
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
doublep
Cut characters by putting statements on the same line when possible. You can change a few newline/tab combinations to just a semicolon. It's especially useful if you can do it in deeply indented lines.
Chris Lutz
Tabs can be replaced by spaces. Just indent one space at the first level, two at the second etc...
phkahler
@phkahler Tabs and spaces are both one character each. Alternating space / tab / space+tab though will save a few characters though.
Nabb
+6  A: 

Perl, 67 characters

including -l flag.

sub f{$_=pop;print;my$n;$n.=$+[0].$1while(s/(.)\1*//);f($n)}f(1)

Perl, 72 characters with extra credit

sub f{$_=pop;print;my$n;$n.=$+[0].$1while(s/(.)\1*//);f($n)}f(pop||1)
Plutor
+2  A: 

C++, 310 characters.

#include <iostream>
#include <list>
using namespace std;
int main(){list<int> l(1,1);cout<<1<<endl;while(1){list<int> t;for(list<int>::iterator i=l.begin();i!=l.end();){list<int>::iterator p=i;++i;while((i!=l.end())&&(*i==*p)){++i;}int c=distance(p,i);cout<<c<<*p;t.push_back(c);t.push_back(*p);}cout<<'\n';l=t;}}

Correctly indented:

#include <iostream>
#include <list>
using namespace std;

int main() {
    list <int> l(1,1);
    cout << 1 << endl;
    while(1) {
        list <int> t;
        for (list <int>::iterator i = l.begin(); i != l.end();) {
            const list <int>::iterator p = i;
            ++i;
            while ((i != l.end()) && (*i == *p)) {
                ++i;
            }
            int c = distance(p, i);
            cout << c << *p;
            t.push_back(c);
            t.push_back(*p);
        }
        cout << '\n';
        l = t;
    }
}
wok
I think that you should `#include <algorithm>` for `distance`.
Matteo Italia
Not sure. It compiles with gcc.
wok
+13  A: 

Haskell: 115 88 85

import List
m x=do a:b<-group x;show(length b+1)++[a]
main=mapM putStrLn$iterate m"1"

This is the infinite sequence. I know it can be improved a lot - I'm fairly new to Haskell.

Bit shorter, inlining mapM and iterate:

import List
m(a:b)=show(length b+1)++[a]
f x=putStrLn x>>f(group x>>=m)
main=f"1"
CiscoIPPhone
@Cisco Some tricks I added: List vs Data.List; do notation instead of concatMap; use of iterate.
jleedev
Nice job jleedev.
CiscoIPPhone
A few minor improvements to get 85: `m x=do a:b<-group x;show(length b+1)++[a]` (pattern matching) and `main=mapM putStrLn$iterate m"1"` (`main` can be `IO a` rather than `IO ()` and `$` can eliminate parentheses).
Olathe
I added another version.
sdcvvc
+1  A: 

C w/ Extra Credit, 242 (or 184)

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define s malloc(1<<20)
main(int z,char**v){char*j=s,*k=s;strcpy(k,*++v);for(;;){strcpy(j,k);z=1;*k=0;while(*j){if(*j-*++j)sprintf(k+strlen(k),"%d%c",z,*(j-1)),z=1;else++z;}puts(k);}}

You can save another ~60 characters if you omit the includes, gcc will still compile with warnings.

$ ./a.out 11111111 | head
81
1811
111821
31181211
132118111221
1113122118312211
31131122211813112221
132113213221181113213211
111312211312111322211831131211131221
3113112221131112311332211813211311123113112211
cthom06
+10  A: 

Javascript 100 97

for(x=prompt();confirm(y=x);)for(x="";y;){for(c=0;y[c++]&&y[c]==y[0];);x+=c+y[0];y=y.substr(c--)}

Allows interrupting the sequence (by clicking "Cancel") so we don't lock the user-agent and peg the CPU. It also allows starting from any positive integer (extra credit).

Live Example: http://jsbin.com/izeqo/2

David Murdoch
`substr()` is shorter than `substring()` and it does the same job if you pass in one argument.
Harmen
@Harmen: thanks.
David Murdoch
A: 

C++, 264

#include <iostream>
#include <sstream>
#include <string>
using namespace std;int main(){string l="1\n";for(;;){ostringstream o;int e=1;char m;cout<<l;for(int i=1;i<l.size();i++){m=l[i-1];if(l[i]==m)e++;else if(e){if(m!='\n')o<<e<<m;e=1;}}l=o.str()+'\n';}return 0;}

with proper indentation:

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    string l="1\n";
    for(;;)
    {
        ostringstream o;
        int e=1;
        char m;
        cout<<l;
        for(int i=1; i<l.size(); i++)
        {
            m=l[i-1];
            if(l[i]==m)
                e++;
            else if(e)
            {
                if(m!='\n')
                    o<<e<<m;
                e=1;
            }
        }
        l=o.str()+'\n';
    }
    return 0;
}

Sample output:

[email protected]:~/cpp$ g++ morris.cpp -O3 -o morris.x && ./morris.x | head1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

C++, 276 (with extra credit)

#include <iostream>
#include <sstream>
#include <string>
using namespace std;int main(){string l;getline(cin,l);for(;;){ostringstream o;int e=1;char m;l+='\n';cout<<l;for(int i=1;i<l.size();i++){m=l[i-1];if(l[i]==m)e++;else if(e){if(m!='\n')o<<e<<m;e=1;}}l=o.str();}return 0;}

with proper indentation:

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    string l;
    getline(cin,l);
    for(;;)
    {
        ostringstream o;
        int e=1;
        char m;
        l+='\n';
        cout<<l;
        for(int i=1; i<l.size(); i++)
        {
            m=l[i-1];
            if(l[i]==m)
                e++;
            else if(e)
            {
                if(m!='\n')
                    o<<e<<m;
                e=1;
            }
        }
        l=o.str();
    }
    return 0;
}

Sample output:

[email protected]:~/cpp$ g++ morris.cpp -O3 -o morris.x && ./morris.x | head
7754 <-- notice: this was inserted manually
7754
271514
121711151114
1112111731153114
31123117132115132114
13211213211711131221151113122114
11131221121113122117311311222115311311222114
3113112221123113112221171321132132211513211321322114
132113213221121321132132211711131221131211132221151113122113121113222114
111312211312111322211211131221131211132221173113112221131112311332211531131122211311123113322114
Matteo Italia
+1  A: 

Here's my very first attempt at code golf, so please don't be too hard on me!

PHP, 128 122 112 bytes with opening tag

122 116 106 bytes without opening tag and leading whitespace.

<?php for($a="1";!$c="";print"$a\n",$a=$c)for($j=0,$x=1;$a[$j];++$j)$a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])&&$x=1;

(Quite a pity I have to initialize $a as a string though, costing me 2 extra bytes, otherwise I can't use index notation on it.)

Output

$ php morris.php
1
11
21
1211
111221
312211
...

PHP (extra credit), 133 127 117 bytes with opening tag

127 121 111 bytes without opening <?php tag and leading whitespace.

<?php for($a=$argv[1];!$c="";print"$a\n",$a=$c)for($j=0,$x=1;$a[$j];++$j)$a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])&&$x=1;

Output

$ php morris.php 3
3
13
1113
3113
132113
1113122113
...
^C
$ php morris.php 614
614
161114
11163114
3116132114
1321161113122114
1113122116311311222114
...

PHP (extra credit), ungolfed with opening and closing tags

<?php

for ($a = $argv[1]; !$c = ""; print "$a\n", $a = $c)
{
    for ($j = 0, $x = 1; $a[$j]; ++$j)
    {
        // NB: this was golfed using ternary and logical AND operators:
        // $a[$j] == $a[$j + 1] ? $x++ : ($c .= $x . $a[$j]) && $x = 1;
        if ($a[$j] == $a[$j + 1])
        {
            $x++;
        }
        else
        {
            $c .= $x . $a[$j];
            $x = 1;
        }
    }
}

?>
BoltClock
Coule you explain what `for(;;)` does? Tried Googling but it's not the easiest thing to search for!
chigley
@chigley: It just indicates an infinite loop. The blank expressions between the semicolons indicate to do nothing to control the loop — just let it run forever. It's like `while(1)`, except 1 character shorter :)
BoltClock
Hah! I beat you to it :]. You should try to remove the double `echo` somehow. Maybe you'll end up with a better solution that way.
Harmen
You can write the if-else statement a little shorter: `$a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])`. It saves you 6 characters
Harmen
@Harmen: Thanks for that, somehow I couldn't get my head around using the ternary operator before :)
BoltClock
@Harmen: I fiddled with my code again and now have a single `print` statement instead of two `echo` statements. I've also beaten you this time :P
BoltClock
@BoltClock, nice D:, I wish I could upvote twice :P -- why no use the php shorttag? `<?`
Harmen
@Harmen: I don't wanna get downvoted by short opening tag haters :P
BoltClock
@BoltClock, I ported it to Javascript: only 87 characters.
Harmen
+1  A: 

Python - 117

My python-fu is not strong, so I did a lot of googling for this. :)

a='1'
while 1:
 print a
 a=''.join([`len(s)`+s[0]for s in''.join([x+' '*(x!=y)for x,y in zip(a,(2*a)[1:])]).split()])

The idea is to use zip to generate a list of (a[i],a[i+1]) pairs, use the inner comprehension to insert a space when a[i]!=a[i+1], join the resulting list to a string, and split on spaces, use another comprehension on this split list to replace each element with the run length of the element, and the first character, and finally join to get the next value in sequence.

Dysaster
+4  A: 

C, 128 characters

uses a static buffer, guaranteed to cause segmentation fault

main(){char*c,v[4096],*o,*b,d[4096]="1";for(;o=v,puts(d);strcpy(d,v))for(c=d;*c;o+=sprintf(o,"%d%c",c-b,*b))for(b=c;*++c==*b;);}
Hasturkun
+14  A: 
Bizangles
Did this before reading the other solutions. Taking the 'redo' advice in another perl answer will reduce these solutions by 3 characters.
Bizangles
I think `-l ` usually costs three characters.
Nabb
+4  A: 

Call a string "Morris-ish" if it contains nothing but digits 1-3, and does not contain any runs of more than three of a digit. If the initial string is Morris-ish, all strings iteratively generated from it will likewise be Morris-ish. Likewise, if the initial string is not Morris-ish then no generated string will be Morris-ish unless numbers greater than ten are regarded as combinations of digits (e.g. if 11111111111 is regarded as collapsing into three ones, rather than an "eleven" and a one).

Given that observation, every iteration starting with a Morris-ish seed can be done as the following sequence of find/replace operations:

111 -> CA
11 -> BA
1 -> AA
222 -> CB
22 -> BB
2 -> AB
333 -> CC
33 -> BC
3 -> AC
A -> 1
B -> 2
C -> 3

Note that a sequence is Morris-ish before the above substitution, the second character of each generated pair will be different from the second character of the preceding and following pairs; it is thus not possible to have more than three identical characters in sequence.

I wonder how many disjoint Morris-ish sequences there are?

supercat
There are countably infinitely many. Let `M` be the set of Morris-ish strings and let `f:M->M` be the "say-what-you-see" function that iteratively generates the Morris sequence. Observe that if `m` is an element of `M`, then `f(m)` has even length. Thus the string `1212121...1`, in which there are `n` 1s and `n-1` 2s for some nonnegative `n`, is the beginning of a Morris-ish sequence (it is not `f(m)` for any `m`). This gives countably infinitely many startpoints for Morris-ish sequences; that the sequences are disjoint only requires that `f` be injective, which is straightforwardly true.
Hammerite
@Hammerite: Nice proof. Parity arguments would seem pretty powerful when dealing with such sequences, given the observation that adjacent pairs must end with different characters.
supercat
A: 

c# 315 236 228

ok first try at code golf


static void Main(string[]args)
    {string o,s="1";int l=11;while(l-- >0)
    {Console.WriteLine(s);o="";while(s!=""){var c=s.Substring(0,1);int i=Regex.Match(s,"("+c+"*)").Length;o+=i.ToString()+c;s=s.Substring(i);}s=o;}}

here is the source with line breaks spaces the >8.9999999999


static void main( string[] args )
    {
        string sp = "1";
        string ou = "";
        int It = 11;
        while ( It-- > 0 )
        {

            Console.WriteLine(sp);
            ou = "";
            while ( sp != "" )
            {
                var c = sp.Substring(0, 1);
                int i = Regex.Match(sp, "(" + c + "*)").Length;
                ou += i.ToString() + c;
                sp = sp.Substring(i);

            }
            sp = ou;
        }
    }

Extra Credit

static void Main(string[]a)
{string o,s=a[0];int l=11;while(l-- >0)
{Console.WriteLine(s);o="";while(s!=""){var c=s.Substring(0,1);int i=Regex.Match(s,"("+c+"*)").Length;o+=i.ToString()+c;s=s.Substring(i);}s=o;}}
rerun
There's still tons of whitespace in your golfed code :)
BoltClock
Yes I think I got it all now
rerun
+8  A: 

Here's my C# attempt using LINQ and first attempt at Code Golf:

C# - 205 194 211 198 bytes with extra credit (including C# boilerplate)

using System.Linq;class C{static void Main(string[]a){var v=a[0];for(;;){var r="";while(v!=""){int i=v.TakeWhile(d=>d==v[0]).Count();r+=i;r+=v[0];v=v.Remove(0,i);}System.Console.WriteLine(r);v=r;}}}

Readable version:

static void Main(string[] args)
{
    string value = args[0];
    for (;;)
    {
        string result = "";
        while (value != "")
        {
            int i = value.TakeWhile(d => d == value[0]).Count();
            result += i;
            result += value[0];
            value = value.Remove(0, i);
        }
        Console.WriteLine(result);
        value = result;
    }
}

Sample output:

11
21
1211
111221
312211
13112221
1113213211
...
GeReV
Renaming the `args` parameter will save you another 6 characters.
0xA3
Did not think of that. Nice.
GeReV
Converting "int i = value.TakeWhile(d => d == value[0]).Count();" to int i = 0; while (i < v.Length will let you remove the Linq using.
MikeP
@MikeP, I actually wanted to use LINQ for that, just as an exercise.
GeReV
+8  A: 

Mathematica - 62 53 50 chars - Extra credit included

Edit: 40 chars ... but right to left :(

Curiously if we read the sequence right to left (i.e. 1,11,12,1121, ..), 40 chars is enough

NestList[Flatten[Tally /@ [email protected]#] &, #2, #] &

That is because Tally generates a list {elem,counter} !

Edit: 50 chars

NestList[[email protected][Tally /@ [email protected]#, 3] &, #2, #] &

Dissection: (read comments upwards)

NestList[               // 5-Recursively get the first N iterations
    [email protected]            // 4-Convert to one big list
       Reverse          // 3-Reverse to get {counter,element}
          [Tally /@     // 2-Count each run (generates {element,counter})
               [email protected]#, // 1-Split list in runs of equal elements
                 3] &,
                     #2,// Input param: Starting Number 
                     #] // Input param: Number of iterations

Edit: refactored

NestList[Flatten[{[email protected]#, #[[1]]} & /@ [email protected]#, 1] &, #2, #1] &

End edit ///

NestList[[email protected][Length /@ (c = [email protected]#), First /@ c] &, #2, #1] &

Spaces not needed / added for clarity

Invoke with

%[NumberOfRuns,{Seed}]

My first time using "Riffle", to combine {1,2,3} and {a,b,c} into {1,a,2,b,3,c} :)

belisarius
A: 

C#, 140 working characters (177 171 with boilerplate)

class C{static void Main(){var x="1\n";for(;;){System.Console.Write(x);var y="";for(int n,i=0;i<x.Length-1;y+=n+""+x[i],i+=n)n=x[i+1]!=x[i]?1:x[i+2]!=x[i]?2:3;x=y+"\n";}}}

This exploit's Conway's observation (IIRC) that no number larger than 3 can appear in the sequence.

        var x = "1\n";
        for (; ; )
        {
            Console.Write(x);
            var y = "";
            var i = 0;
            while (i < x.Length - 1)
            {
                var n = x[i + 1] != x[i] ? 1 : x[i + 2] != x[i] ? 2 : 3;
                y += n + "" + x[i];
                i += n;
            }
            x = y + "\n";
        }
Rafe
+2  A: 

Delphi

Delphi is a terrible golfing language, but still:

var i,n:Int32;s,t,k:string;u:char;label l;begin s:='1';l:writeln(s);t:='';u:=s[1
];n:=1;for i:=2to length(s)do if s[i]=u then inc(n)else begin str(n,k);t:=t+k+u;
u:=s[i];n:=1;end;str(n,k);t:=t+k+u;s:=t;goto l;end.

This is 211 bytes (and it compiles as it stands).

Andreas Rejbrand
undeclared identifier Int32 @ Delphi 2007 for win32
himself
Also instead of the middle FOR you can do this to save a bit: n:=0;i:=2;z:Inc(n);Inc(i);if s[i]=u then goto z;str(n,k);t:=t+k+u;u:=s[i];n:=0;goto z;
himself
upped your score, check it out, mine's 164.
himself
@himself: In Delphi 2009, a Int32 is an integer.
Andreas Rejbrand
+4  A: 

Perl (extra credit), 47 chars

$_=pop.$/;{print;s/(.)\1*/$&=~y|||c.$1/ge;redo}
pdehaan
+5  A: 

Ruby — 52

s=?1;loop{puts s;s.gsub!(/(.)\1*/){"#{$&.size}"+$1}}

Task is too simple, and too perlish...

Nakilon
+13  A: 

GolfScript - 41 (extra credit: 40)

1{.p`n+0:c:P;{:|P=c{c`P|:P!}if):c;}%~1}do
{~.p`n+0:c:P;{:|P=c{c`P|:P!}if):c;}%1}do

What?
The procedure for getting the next number in the sequence: Convert the current number to a string, append a newline and loop over the characters. For each digit, if the previous digit P is the same, increment the counter c. Otherwise, add c and P to what will be next number, then update these variables. The newline we append allows the last group of digits to be added to the next number.

The exact details can be obtained examining the GolfScript documentation. (Note that | is used as a variable.)

Nabb
Ah, looks like another golfscript/J shootout
gnibbler
I find it amusing that the extra credit makes it shorter.
Brian
Could you explain what's happening here, for us golfscript newbies? :-)
Michael Foukarakis
@Michael I added a brief description of the algorithm, but you'll have to refer to gs documentation if you want to understand what exactly is happening (luckily the code is only 41 characters).
Nabb
Looks like the shortest so far :) Will accept this tomorrow if I don't see anything shorter!
Vivin Paliath
A: 

Delphi, 163 bytes (166 with extra)

Significantly reworked Andreas Rejbrand version. It's good str() does not check parameter type, or I'd have to cast integer(s)-integer(u).

var q,t,k:string;s,u:pchar;label l,z;begin t:='1';l:writeln(t);q:=t;s:[email protected][1];
t:='';z:u:=s;while s^=u^do Inc(s);str(s-u,k);t:=t+k+u^;if s^=#0then goto l;
goto z;end.

For extra, change t:='1'; to t:=readln;

himself
Since 0 = 00, you can easily save one more character.
Andreas Rejbrand
+3  A: 

J, 44 characters with extra credit

(([:,#;[email protected]{:,.{:#{.)@(,:0<1,[:|2-/\]))^:(<9)

Unfortunately this only generates 9 iterations, but the iteration count <9 can be tweaked to be anything. Setting it to a: generates an infinite sequence but obviously this can't be printed.

Usage:

   (([:,#;[email protected]{:,.{:#{.)@(,:0<1,[:|2-/\]))^:(<9) 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 0 0 0 0 0
1 2 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 2 2 1 0 0 0 0 0 0 0 0
3 1 2 2 1 1 0 0 0 0 0 0 0 0
1 3 1 1 2 2 2 1 0 0 0 0 0 0
1 1 1 3 2 1 3 2 1 1 0 0 0 0
3 1 1 3 1 2 1 1 1 3 1 2 2 1

   (([:,#;[email protected]{:,.{:#{.)@(,:0<1,[:|2-/\]))^:(<11) 4
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 1 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 3 1 1 2 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 2 1 1 3 2 1 3 2 2 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 4 0 0 0 0 0 0 0 0
3 1 1 3 1 1 2 2 2 1 1 3 1 1 1 2 3 1 1 3 3 2 2 1 1 4 0 0 0 0
1 3 2 1 1 3 2 1 3 2 2 1 1 3 3 1 1 2 1 3 2 1 2 3 2 2 2 1 1 4
David
That's the longest J code I've ever seen! Sheesh, can't this language be made more terse?
fbrereto
+1  A: 

PHP: 111

My first attempt ever on a code golf, quite happy with the result.

for($x=1;;){echo$y=$x,"\n";for($x="";$y;){for($c=0;$y[$c++]&&$y[$c]==$y[0];);$x.=$c.$y[0];$y=substr($y,$c--);}}

Gives:

> php htdocs/golf.php
1
11
21
... (endless loop)

PHP with extra credit: 118

for($x=$argv[1];;){echo$y=$x,"\n";for($x="";$y;){for($c=0;$y[$c++]&&$y[$c]==$y[0];);$x.=$c.$y[0];$y=substr($y,$c--);}}

Gives:

> php htdocs/golf.php 4
4
14
1114
3114
... (to infinity and beyond)
Harmen
Have a +1 for beating my answer :)
BoltClock
I just noticed your counts don't include the opening `<?php` tag (mine do)...
BoltClock
+2  A: 

Python - 98 chars

from itertools import *
L='1'
while 1:print L;L=''.join('%s'%len(list(y))+x for x,y in groupby(L))

106 chars for the bonus

from itertools import *
L=raw_input()
while 1:print L;L=''.join('%s'%len(list(y))+x for x,y in groupby(L))
gnibbler
A: 

Javascript: 87

This is inspired by the code of BoltClock and my own PHP attempts.

for(a="1";!(c="");alert(a),a=c)for(j=0,x=1;a[j];j++)a[j]==a[j+1]?x++:(c+=x+a[j])&&(x=1)

Javascript with extra: 92

for(a=prompt();!(c="");alert(a),a=c)for(j=0,x=1;a[j];j++)a[j]==a[j+1]?x++:(c+=x+a[j])&&(x=1)

Beautified:

// Start with a=1, an set c to "" every start of the loop
// alert a and set a=c at the end of a loop
for (a = "1"; !(c = ""); alert(a), a = c)

  // Set iterator j to 0, set counter x to 1 at the initialisation
  // detect if a[j] exists at the start of the loop and incremement j at the end
  for (j = 0, x = 1; a[j]; j++)

    // check if the jth and (j+1)th characters are equal
    // if so, increment x,
    // if not, the end of a row is found, add it to c and set x to 1 again
    a[j] == a[j + 1] ? x++ : (c += x + a[j]) && (x = 1)
Harmen
+1  A: 

C#, 204 bytes (256 with extra credit)

My first attempt at code golf

static void Main(){var v="1";for(;;){Console.Write(v + "\n");var r=v.Aggregate("", (x, y) => x.LastOrDefault()==y?x.Remove(0, x.Length-2)+(int.Parse(x[x.Length-2].ToString())+1).ToString()+y:x+="1"+y);v=r;}}

Readable version, the difference from others is that I use Linq's Aggregate function

static void Main(){
    var value="1";
    for(;;)
    {
        Console.Write(value + "\n");
        var result = value.Aggregate("", (seed, character) => 
                        seed.LastOrDefault() == character ? 
                            seed.Remove(seed.Length-2) + (int.Parse(seed[seed.Length-2].ToString())+1).ToString() + character
                            : seed += "1" + character
                    );
        value = result;
    }
}
MarkisT
+3  A: 

Java - 167 chars (with credit)

(122 without class/main boilerplate)


class M{public static void main(String[]a){for(String i=a[0],o="";;System.out.println(i=o),o="")for(String p:i.split("(?<=(.)(?!\\1))"))o+=p.length()+""+p.charAt(0);}}

With newlines:

class M{
 public static void main(String[]a){
  for(String i=a[0],o="";;System.out.println(i=o),o="")
   for(String p:i.split("(?<=(.)(?!\\1))"))
    o+=p.length()+""+p.charAt(0);
 }
}
BalusC
+1 I would of never thought to use a for loop like that
TheLQ
It saves semicolons and braces :)
BalusC
A: 

Clojure 111 chars

(loop[a"1"](pr a)(let[x(reduce(fn[a b](str a(count(first b))(nth b 1)))(str)(re-seq #"(.)\1*" a))](recur x)))

Bonus 119 chars

(loop[a(read-line)](pr a)(let[x(reduce(fn[a b](str a(count(first b))(nth b 1)))(str)(re-seq #"(.)\1*" a))](recur x)))
Mongus Pong
A: 

285 248 Chars is the best I can do in C# (That's without the extra as well!)

Edit: This is my first code golf as well.. Quite enjoyed doing that :D

static void Main(){string s="1",x=s;for(;;){char[]c=x.ToCharArray();char d=c[0];x="";int a=0;for(inti=0;i<=c.Length;i++){char q;if(i!=c.Length)q=c[i];else q='0';if (d != q){x+=a.ToString();x+=d.ToString();d=q;a=1;}else a++;}Console.WriteLine(x);}}

Readable code:

using System;
class Program
{
    static void Main()
    {
        string startPoint = "1";
        string currentPoint = startPoint;
        while (true)
        {
            char[] currentPointAsCharArray = currentPoint.ToCharArray();
            char previousCharacter = currentPointAsCharArray[0];
            currentPoint = "";
            int countOfCharInGroup = 0;
            for(int i=0;i<=currentPointAsCharArray.Length;i++)
            {
                char c;
                if (i != currentPointAsCharArray.Length)
                    c = currentPointAsCharArray[i];
                else
                    c = '0';
                if (previousCharacter != c)
                {
                    currentPoint += countOfCharInGroup.ToString();
                    currentPoint += previousCharacter.ToString();
                    previousCharacter = c;
                    countOfCharInGroup = 1;
                }
                else
                    countOfCharInGroup++;
            }
            Console.Write(currentPoint + "\n");
        }
    }
}
teishu
+1  A: 

Python - 92 characters

98 with extra credit

Outputs infinitely. I recommend redirecting output to a file, and quickly hitting Ctrl+C.

x=`1`;t=''
while 1:
 print x
 while x:c=x[0];n=len(x);x=x.lstrip(c);t+=`n-len(x)`+c
 x,t=t,x

For the extra credit version, replace

x=`1`

with

x=`input()`
P Daddy
Very nice use of lstrip. :)
Dysaster
Thanks​​​​​​​​​
P Daddy
A: 

C - 120 characters

129 with extra credit

main(){char*p,*s,*r,x[99]="1",t[99];for(;r=t,puts(p=x);strcpy(x,t))
for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

The newline is there only for readability's sake.

This stops when it segfaults (after at least 15 iterations). If your C libraries use buffered I/O, then you may not see any output before the segfault. If so, test with this code:

#include<stdio.h>
main(){char*p,*s,*r,x[99]="1",t[99];for(;r=t,puts(p=x),fflush(stdout),1;
strcpy(x,t))for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}

This adds an fflush after every output.

Ungolfed, it would look something like this:

int main(){
    char *p, *start, *result, number[99] = "1", temp[99];

    while(1){ /* loop forever */
        puts(number);

        result = temp; /* we'll be incrementing this pointer as we write */
        p = number;    /* we'll be incrementing this pointer as we read */

        while(*p){ /* loop till end of string */
            start = p; /* keep track of where we started */

            while(*p == *start) /* find all occurrences of this character */
                p++;

            *result++ = '0' + p - start; /* write the count of characters, */
            *result++ = *start;          /* the character just counted, */
            *result   = 0;               /* and a terminating null */
        }

        strcpy(number, temp); /* copy the result back to our working buffer */
    }
}

You can see it in action on ideone.

With the extra credit, the code looks like this:

main(){char*p,*s,*r,x[99],t[99];for(scanf("%s",x);r=t,puts(p=x);strcpy(x,t))
for(;*p;*r++=p-s+48,*r++=*s,*r=0)for(s=p;*++p==*s;);}
P Daddy
+1  A: 

Common Lisp - 124 122 115 Chars

(do((l'(1)(do(a r)((not l)r)(setf a(1+(mismatch(cdr l)l))r(,@r,a,(car l))l(nthcdr a l)))))((format t"~{~s~}~%"l)))

With formatting:

(do ((l '(1) (do (a r) ((not l) r) (setf a (1+ (mismatch (cdr l) l))
                                         r `(,@r ,a ,(car l)) l (nthcdr a l)))))
    ((format t "~{~s~}~%" l)))
lpetru
+1  A: 

F# - 135

let rec m l=Seq.iter(printf "%i")l;printfn"";m(List.foldBack(fun x s->match s with|c::v::t when x=v->(c+1)::v::t|_->1::x::s)l [])
m[1]

Formatted Code

let rec m l=
    Seq.iter(printf "%i")l;printfn"";
    m (List.foldBack(fun x s->
        match s with
        |c::v::t when x=v->(c+1)::v::t
        |_->1::x::s) l [])
m[1]

Still hopeful I can find a better way to print the list or use string/bigint instead.

Tony Lee
A: 

Scala - 97 chars

Heavily inspired by @BalusC's impressive answer:

def m(s:String){println(s);m((""/:(s split"(?<=(.)(?!\\1))")){(a,s)=>a+s.size+s(0)})};m(args(0))
Don Mackenzie