[Exercise] Morris Number Sequence

Joe

Write a code that outputs the n first numbers of the Morris Number Sequence.

1 (one)
11 (one one)
21 (two ones)
1211 (one two, one one)
111221 (one one, one two, two ones)
312211 (three ones, two twos, one one)
13112221 (one three, one one , two twos, two ones)
1113213211 (one one, one three, two ones, three twos, one one)
...

Bonus: Code Golf!

Make it in as little characters as possible (different languages cannot really compete, but it still makes for a very nice addition).

Print the number of characters in your (short) codes.

Joe

...

Edit: Cleaned up my code a bit. Here it is:

def morrnext(input, val="", count=0, output=""):
    if len(input) == 0:
        return output + str(count) + val

    if input[0] != val:
        if len(val) != 0:
            output += str(count) + val
        return morrnext(input[1:], input[0], 1, output)

    return morrnext(input[1:], val, count+1, output)


def morrseq(n, x="1"):
    for i in range(n):
        print x
        x = morrnext(x)

output:

>>> morrseq(10)
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

Next step: Code golf!

geek

NestList[FromDigits@Flatten[Reverse@@@Tally/@Split@IntegerDigits@#]&,1,n]

73 characters
5 ms for 23
40 ms for 31
70 ms for 33
640 ms for 41
1100 ms for 43

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211
311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221
132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221
3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211

if you're into code golf, have a look at J and GolfScript.
by the way, you will never get a digit greater than 3. why?

jsaade

c++ does not love 1 liners :)

   string nbr = "1";
    string nextnbr="";
    cout<<1<<endl;
    for(size_t times = 0; times < 10; ++times){
        size_t i = 0;
        nextnbr = "";
        while(i < nbr.length()){
            size_t count = 0;
            char current = nbr[i];
            while(nbr[i++] == current && nbr.length()) 
                ++count;
            --i;
            stringstream tmp;
            tmp<<count<<current;
            nextnbr.append(tmp.str());
        }
        cout<<nextnbr<<endl;
        nbr = nextnbr;
    }

arithma

by the way, you will never get a digit greater than 3. why?

Because of contradiction. If you get any number greater than 3, it means it has four consecutive digits.
XXXX. The algorithm should have outputted: (2*X)(X). Unless of course the initial string (instead of 1) had more than 3 of the same digits. This is an informal inductive proof.

arithma

Here's a JS solution:

<html>
	<body>
		<script>
			function morris(str){
				var out = "";
				while(str.length > 0){
					count = morris_extr(str.substr(0, 1), 0, str);
					out += count + str.substr(0, 1);
					str = str.substr(count);
				}
				return out;
			}
			
			function morris_extr(start, cnt, str){
				if(str.length > 0 && str.substr(0, 1) == start){
					return morris_extr(start, cnt + 1, str.substr(1))
				}
				else{
					return cnt;
				}
			}
			
			var x = "1";
			
			for(var i = 0; i < 10; i++){
				console.log(x);
				x = morris(x);
			}
		</script>
	</body>
</html>

Ayman

Nice exercise! Here is a Php solution using Regex and Closures.

<?php
$num = 1; 
$n = 10;
for ($i = 0; $i < $n; $i++) {
    print"$num<br />";
    $num = preg_replace_callback('/([\d])\1*/',function($match){return strlen($match[0]).$match[1];},$num);
}
?>

Joe

On my way to a one liner (hopefully), here's what I got so far:

def f (a,b=["",0,""]):
    if len(a) == 0:
        return b[2] + str(b[1]) + b[0]

    g= lambda i, j : {True: [j[0], j[1] + 1, j[2]],
                      i! = j[0]: [i, 1, j[2] + str(j[1]) + j[0]],
                      len(j[0]) == 0: [i, 1, j[2]] }[True]

    return f(a[1:], g(a[0], b))

I can call the function like this:

def morrseq(n, x="1"):
    for i in range(n):
        print x
        x = f(x)

>>> morrseq(10)
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

This is the first time I write anything like that. I would love some criticism on function f() (if anyone can understand the gibberish mess I wrote). Thanks :)

Joe

f = lambda a, b=["",0,""]:(
    b[2] + str(b[1]) + b[0] if not a else
    (lambda g:(
            f(a[1:], g(a[0], b)))
     )( lambda i, j : {True: [j[0], j[1] + 1, j[2]],
                      i != j[0]: [i, 1, j[2] + str(j[1]) + j[0]],
                      len(j[0]) == 0: [i, 1, j[2]] }[True]))

Now I understand what Higher Order Functions really means. It took all day today but it was worth it. Technically it took 24 years to get here, but heck it was still worth it.

raja

Here's my equivalent of rahmu's f() function:

f = lambda n:  "".join(map(lambda a: map(lambda b: str(b.count(b[0]))+b[0], [a.group()])[0], re.finditer(r"([0-9])\1*", n)))

Here's a use of it by another one-liner:

f = lambda n,dummy=None:  "".join(map(lambda a: map(lambda b: str(b.count(b[0]))+b[0], [a.group()])[0], re.finditer(r"([0-9])\1*", n)))
morrseq = lambda n: reduce(f, ["1"] + range(n))

Result:

>>> morrseq(1)
'11'
>>> morrseq(2)
'21'
>>> morrseq(3)
'1211'
>>> morrseq(4)
'111221'
>>>

All of it in a single one-liner:

morrseq = lambda m: reduce(lambda n,dummy=None:  "".join(map(lambda a: map(lambda b: str(b.count(b[0]))+b[0], [a.group()])[0], re.finditer(r"([0-9])\1*", n))), ["1"] + range(m))

Edit:
PS: Including the "import re" this clocks in at 168 characters(excluding newlines and spaces). Better than rahmu's 184(And that's without the use of the f() function which would've added even more) but doesn't even get close to geek's 87

xterm

In groovy, not proud of it.

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

83 characters
327ms for 43

Note: This is a transformation of the JS algo used here.