代码高尔夫: Morris序列

Question

代码高尔夫: Morris序列

language-agnosticcode-golfrosetta-stone

46

挑战

以字符计数最短的代码输出莫里斯数字序列，也称为 外观数列，序列的前几项如下：

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

你可以无限生成这个序列（也就是说，你不必生成特定数量的数字）。

输入/输出期望

程序不需要接受任何输入（但如果能接受输入并提供从任意起始点或数字开始的选项，则加分）。至少，你的程序必须从 1 开始。

输出至少应该是序列本身：

额外加分

如果你想要获得额外的加分，你需要做如下操作：

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

$ morris 3
3
13
1113
3113
132113
...

- Vivin Paliath

1

输入和输出的期望是什么？单个值，单个输出吗？特定次数的迭代？ - Mike Clark

1

我认为如果你用“无限地”（模糊、不清楚）替换为“无穷尽地”（无限的，没有边界），它会更清晰。至于关闭问题：习惯就好了。在SO上，“代码高尔夫”问题是一个灰色区域。 - BalusC

3

输出应该是 [13, 1113, 3113...] 还是 [3, 13, 1113, 3113...]? - Instantsoup

@Bart - 我喜欢看到我的帖子被引用！很高兴看到人们仍然在帮助新手。 - Chris Lutz

6

@Nakilon，我想各种不同的方法（如下）并不意味着有多种方法可供选择。感谢您精彩的见解。 - Vivin Paliath

显示剩余9条评论

41个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user581149 · Answer 1

PHP 72 字节

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

这个脚本可能还可以进一步优化。但由于我们在 PHPGolf（{http://www.phpgolf.org/?p=challenges&challenge_id=28}）中有完全相同的序列，所以我会保持这种方式。

- Wok · Answer 2

C++，310个字符。

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

正确缩进：

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

- cthom06 · Answer 3

带有额外学分的C语言，242（或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);}}

如果省略掉 includes，你可以再节省大约 60 个字符，gcc 编译时仍会发出警告。

$ ./a.out 11111111 | head
81
1811
111821
31181211
132118111221
1113122118312211
31131122211813112221
132113213221181113213211
111312211312111322211831131211131221
3113112221131112311332211813211311123113112211

- vhallac · Answer 4

Python - 117

我的 Python 技能不够强，所以我为此进行了很多谷歌搜索。:)

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

这个想法是使用zip生成(a[i],a[i+1])对的列表，使用内部推导式在a[i]!=a[i+1]时插入一个空格，将结果列表连接成字符串，并在空格上拆分，使用另一个推导式在此拆分列表上替换每个元素为该元素的运行长度和第一个字符，最后连接以获取序列中的下一个值。

- John La Rooy · Answer 5

Python - 98个字符

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

为了获得奖励，需要编写106个字符的代码

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

- Markis · Answer 6

C#，204字节（加上额外的信用为256）

我的第一次尝试代码高尔夫

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

易读版本，不同于其他人的是我使用了 Linq 的 Aggregate 函数

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

- lpetru · Answer 7

Common Lisp - 124 122 115个字符

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

带格式：

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

- Tony Lee · Answer 8

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]

格式化的代码

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]

我仍然希望能够找到更好的打印列表或使用字符串/大整数的方法。

- P Daddy · Answer 9

Python - 92个字符

^{加上额外的学分为98}

输出无限。我建议将输出重定向到文件，并快速按下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

对于额外的加分版本，请替换

x=`1`

使用

x=`input()`

- P Daddy · Answer 10

C - 120个字符

^{如果有额外的学分，则为129个字符}

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

^{换行符只是为了方便阅读。}

这会在至少15次迭代后发生段错误而停止。如果您的C库使用缓冲I/O，则在段错误之前可能看不到任何输出。如果是这样，请使用此代码进行测试：

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

这会在每个输出后添加一个fflush。

未压缩的代码看起来可能是这样的：

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 */
    }
}

你可以在ideone上看到它的运行效果。

有了额外的加分项，代码看起来像这样：

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