Code Golf: Morris Sequence

Question

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

Yolanda

What is the input and output expectation? Single value, single output? Specific number of iterations? – Lodged

@Mike: Well, I'd presume for non-strict (lazy) languages, or ones which support generators, you can just write the function for generating the whole (infinite) sequence. For strict-only languages, print out elements until interrupted by the user, or something like that. – Hyo

@Mike I stated that you can generate the sequence indefinitely :) There is no specific number of iterations. – Yolanda

@whoever If you're going to vote to close, at least say why. – Yolanda

I think it's more clear if you replace "indefinitely" (vague, unclear) by "infinitely" (endless, no borders). As to the closers: get used to it. code-golf questions are a gray area in SO. – Paulie

@Paulie thanks! I will reword it! – Yolanda

@Vivin, normally I say why I vote to close, but your original post lacked so many details, I simply didn't feel like explaining myself. Also see meta.stackexchange.com/questions/24242/… for some "rules" on proper code-golf posts. – Intergrade

Should the output be [13,1113,3113...] or [3,13,1113,3113...]? – Strongbox

@Bart thanks. IMO I felt that the problem was sufficiently simple (generate this sequence) to require no additional explanation. Thanks for the link! @instantsoup my bad! I fixed it – Yolanda

@Bart - I love seeing my post referenced! Glad to see people helping out the newbies still. – Takakotakakura

Nobody adventurous to try lisp? – Doorstone

-1 "be complex enough to admit more than one reasonable way to accomplish it" stackoverflow.com/tags/code-golf/info – Swordplay

@Swordplay I guess the numerous different ways of doing it (below) doesn't mean that there is more than one way to do it. Thank you for your wonderful insight. – Yolanda

This question appears to be off-topic because it is about Code Golf; a site that has its own questions. – Irrelative

Answer 1

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

Jesselyn

Ah, looks like another golfscript/J shootout – Dyak

Could you explain what's happening here, for us golfscript newbies? :-) – Cassation

@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). – Jesselyn

Looks like the shortest so far :) Will accept this tomorrow if I don't see anything shorter! – Yolanda

Answer 2

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"

Angeliaangelic

Some tricks I added: List vs Data.List; do notation instead of concatMap; use of iterate. – Fulton

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). – Applicant

Answer 3

Perl (46 characters)

$_="1$/";s/(.)\1*/length($&).$1/eg while print

Extra Credit (52 characters)

$_=(pop||1).$/;s/(.)\1*/length($&).$1/eg while print

Swayder

Did this before reading the other solutions. Taking the 'redo' advice in another perl answer will reduce these solutions by 3 characters. – Swayder

I think -l usually costs three characters. – Jesselyn

Answer 4

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

Vinasse

substr() is shorter than substring() and it does the same job if you pass in one argument. – Handmaid

Answer 5

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 /@ Split@#] &, #2, #] &

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

Edit: 50 chars

NestList[Flatten@Reverse[Tally /@ Split@#, 3] &, #2, #] &

Dissection: (read comments upwards)

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

Edit: refactored

NestList[Flatten[{Length@#, #[[1]]} & /@ Split@#, 1] &, #2, #1] &

End edit ///

NestList[Flatten@Riffle[Length /@ (c = Split@#), 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} :)

Rhizo

Answer 6

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$_,$/

Beabeach

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). – Inguinal

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

You can remove two semicolons, use for(;;), and sentence modifiers (while at end of sentence) don't need parenthesis, for 4 chars less. – Aircraftman

@ninjalj: As per my comments above, you can just use redo in a block for the same effect, saving two more characters. :-) – Inguinal

Still one character too many. As said above, sentence modifiers don't need no parenthesis. – Aircraftman

Also, the ^ anchor isn't needed, s/// remembers the last character it examined. – Aircraftman

This one doesn't print "1" (or the input value) on the first line of output. – Lattice

This one doesn't print "1" (or the input value) on the first line of output. You should swap the print and the s/// around the while. Also, $+[0]-$-[0] is longer than length($&). – Lattice

Answer 7

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

Soluble

Renaming the args parameter will save you another 6 characters. – Masinissa

Converting "int i = value.TakeWhile(d => d == value[0]).Count();" to int i = 0; while (i < v.Length && v[i] == v[0]) i++; will let you remove the Linq using. – Hickey

@MikeP, I actually wanted to use LINQ for that, just as an exercise. – Soluble

Answer 8

Python, 97 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+=`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

Encouragement

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

Tabs can be replaced by spaces. Just indent one space at the first level, two at the second etc... – Amandaamandi

@Amandaamandi Tabs and spaces are both one character each. Alternating space / tab / space+tab though will save a few characters though. – Jesselyn

Answer 9

Ruby — 52

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

Task is too simple, and too perlish...

Swordplay

Answer 10

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)

Lattice

Answer 11

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.

Spellbind

I was going to up vote but I hate prolog so much I just couldn't do it. – Williams

Answer 12

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

Beabeach

Answer 13

Perl (extra credit), 47 chars

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

Headsman

Answer 14

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?

Lithia

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

@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. – Lithia

Answer 15

Java

My first attempt at a 'Code-Golf' I just threw this together during part of my IB CS class:

238 condensed

Condensed:

String a="1",b="1",z;int i,c;while(true){System.out.println(b);for(c=0,i=0,b="",z=a.substring(0,1);i<a.length();i++){if(z.equals(a.substring(i,i+1)))c++;else{b+=Integer.toString(c)+z;z=a.substring(i,i+1);c=1;}}b+=Integer.toString(c)+z;a=b;}

Properly formatted:

    String a = "1", b = "1", z;
    int i, c;

    while (true) {      
      System.out.println(b);

      for (c = 0, i = 0, b = "", z = a.substring(0, 1); i < a.length(); i++) {
        if (z.equals(a.substring(i, i + 1))) c++;
        else {
          b += Integer.toString(c) + z;
          z = a.substring(i, i + 1);
          c = 1;
        }
      }

      b += Integer.toString(c) + z;
      a = b;
    }

Edin

Please explore other topics tagged code-golf to learn what they meant with "code-golf". – Paulie

Man, I wish my IB curriculum included CS. – Zweig

@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 – Palatial

@Daniel Not all schools offer it. – Selfhood

@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. – Zweig

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

@ChristopheD: the OP edited the answer afterwards :) Check edit history 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. – Paulie

@BalusC: ah ok, that explains a lot (the initial revision didn't look that golfed)... – Smashing

Answer 16

J, 44 characters with extra credit

(([:,#;.1@{:,.{:#{.)@(,: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:

   (([:,#;.1@{:,.{:#{.)@(,: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

   (([:,#;.1@{:,.{:#{.)@(,: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

Resemblance

That's the longest J code I've ever seen! Sheesh, can't this language be made more terse? – Janice

Answer 17

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

Paulie

It saves semicolons and braces :) – Paulie

Answer 18

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)

Handmaid

Have a +1 for beating my answer :) – Misrepresent

Answer 19

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

Sidoney

undeclared identifier Int32 @ Delphi 2007 for win32 – Magness

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; – Magness

upped your score, check it out, mine's 164. – Magness

@himself: In Delphi 2009, a Int32 is an integer. – Sidoney

Answer 20

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

?>

Misrepresent

Coule you explain what for(;;) does? Tried Googling but it's not the easiest thing to search for! – Abjuration

@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 :) – Misrepresent

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

You can write the if-else statement a little shorter: $a[$j]==$a[$j+1]?$x++:($c.=$x.$a[$j])&&$x=1;. It saves you 6 characters – Handmaid

@Harmen: Thanks for that, somehow I couldn't get my head around using the ternary operator before :) – Misrepresent

@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 – Misrepresent

@BoltClock, nice D:, I wish I could upvote twice :P -- why no use the php shorttag? <? – Handmaid

@Harmen: I don't wanna get downvoted by short opening tag haters :P – Misrepresent

@BoltClock, I ported it to Javascript: only 87 characters. – Handmaid

Answer 21

PHP 72 bytes

<?for(;;)echo$a=preg_filter('#(.)\1*#e','strlen("$0"). $1',$a)?:5554,~õ;

This script might be further optmized. But since we've got at PHPGolf ({http://www.phpgolf.org/?p=challenges&challenge_id=28}) exactly the same sequence, I keep it this way.

Cypriot

Answer 22

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.

Skricki

Answer 23

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

Mention

Answer 24

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

Medicable

Answer 25

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

Medicable

Answer 26

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

Cordovan

Answer 27

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

Dyak

Answer 28

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.

Yarborough

Answer 29

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

Pharyngeal

Answer 30

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

Cardinal

I think that you should #include <algorithm> for distance. – Ives

Not sure. It compiles with gcc. – Cardinal

Answer 31

Groovy (86 characters) with extra credit:

def f={m,n->n.times{println m;m=(m=~/(\d)\1*/).collect{it[0].size()+""+it[1]}.join()}}

Invoke with: f(1,10)orf(x,n)for credit.

Om

Answer 32

Lua, 114 bytes (with bonus)

Condensed:

x=arg[1]while 1 do print(x)i=1 y=''while i<=#x do a=x:sub(i,i)s,e=x:find(a..'+',i)y=y..e+1-s..a;i=e+1 end x=y end

Properly formated:

x=arg[1]
for k=1,10 do
    print(x)
    i=1
    y=''
    while i <= #x do
        a=x:sub(i,i)
        s,e=x:find(a..'+',i)
        y=y..e+1-s ..a
        i=e+1
    end
    x=y
end

Allgood

Answer 33

J, 61 chars

J: las=: ,@((# , {.);.1~ 1 , 2 ~:/\ ])&.(10x&#.inv)@]^:(1+i.@[)

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

Source here: http://rosettacode.org/wiki/Look-and-say_sequence#J

Zaragoza

Answer 34

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

Dice

Answer 35

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

Handcraft

Answer 36

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

Unfit

Answer 37

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)

Handmaid

Answer 38

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:=@q[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;

Magness

Since 0 = 00, you can easily save one more character. – Sidoney

Answer 39

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

Harmattan

Answer 40

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

Williams

Answer 41

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:

matteo@teoubuntu:~/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:

matteo@teoubuntu:~/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

Ives