代码高尔夫:莫里斯序列

Question

挑战

按字符数排序的最短代码将输出Morris数字序列.在莫里斯数列,又称外观数列是数字的顺序启动,如下所示:

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

您可以无限生成序列(即,您不必生成特定的数字).

I/O期望

该程序不需要任何输入(但是接受输入的奖励点,从而提供从任意任意起点或数字开始的选项).至少你的程序必须从1.

输出至少是预期的顺序:

1
11
21
1211
111221
312211
...

额外信用

如果你需要额外的功劳,你需要做这样的事情:

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

$ morris 3
3
13
1113
3113
132113
...

Answer 1

GolfScript - 41(额外积分: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

什么？
获取序列中下一个数字的过程:将当前数字转换为字符串,附加换行符并循环遍历字符.对于每个数字,如果前一个数字P相同,则递增计数器c.否则,添加c和P下一个数字,然后更新这些变量.我们追加的换行符允许将最后一组数字添加到下一个数字.

可以通过检查GolfScript文档获得确切的详细信息.(注意,|它用作变量.)

Answer 2

哈斯克尔:115 88 85

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

这是无限的序列.我知道它可以得到很多改进 - 我对Haskell来说还是新手.

比较短,内联mapM和迭代:

import List
m(a:b)=show(length b+1)++[a]
f x=putStrLn x>>f(group x>>=m)
main=f"1"

Answer 3

Perl(46个字符)

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

额外积分(52个字符)

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

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

允许中断序列(通过单击"取消"),因此我们不会锁定用户代理并固定CPU.它还允许从任何正整数(额外信用)开始.

实例:http://jsbin.com/izeqo/2

Answer 5

Perl,46个字符

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

额外信用,51个字符:

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

Answer 6

Mathematica - 62 53 50个字符 - 包括额外的信用

编辑:40个字符......但是从右到左:(

奇怪的是,如果我们从右到左阅读序列(即1,11,12,1121,..),40个字符就足够了

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

那是因为Tally生成了一个列表{elem,counter}!

编辑:50个字符

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

解剖:(阅读评论向上)

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

编辑:重构

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

结束编辑///

NestList[Flatten@Riffle[Length /@ (c = Split@#), First /@ c] &, #2, #1] &

为清晰起见,不需要/添加空间

调用

%[NumberOfRuns,{Seed}]

我第一次使用"Riffle"将{1,2,3}和{a,b,c}组合成{1,a,2,b,3,c} :)

Answer 7

Python,97 102 115

空格应该是标签:

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

例如:

$ python morris.py | head
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

Answer 8

这是我使用LINQ的C#尝试并首次尝试Code Golf:

C# - 205 194 211 198字节带额外功劳(包括C#样板)

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

可读版本:

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

样本输出:

11
21
1211
111221
312211
13112221
1113213211
...

Answer 9

这是我的实现(在Prolog中):

带DCG的Prolog(174个字符):

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

普通香草序言,代码更易于翻译(225个字符):

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

输出Morris序列:m(D).其中D是'起始'数字.

Answer 10

Perl,67个字符

包括-l国旗.

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

Perl,72个字符,额外信用

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

Answer 11

Ruby - 52

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

任务太简单了,太过于...

Answer 12

C,128个字符

使用静态缓冲区,保证导致分段错误

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