代码高尔夫: Morris序列

Question

挑战

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

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

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

输入/输出期望

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

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

1
11
21
1211
111221
312211
...

额外加分

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

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

$ morris 3
3
13
1113
3113
132113
...

- Vivin Paliath

---

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

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

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

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

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

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 文档获得确切的细节。（注意，| 用作变量。）

- Nabb

---

啊，看起来又是另一场GolfScript/J语言的比试。 - John La Rooy

你能为我们这些golfscript新手解释一下这里发生了什么吗？ :-) - Michael Foukarakis

@Michael，我添加了算法的简要描述，但如果你想了解具体发生了什么（幸运的是代码只有41个字符），你需要参考gs文档。 - Nabb

目前看来这是最短的了 :) 如果我没有看到更短的，明天就会接受这个！ - Vivin Paliath

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"

这是一个无穷序列。我知道它可以被改进得更好 - 我对Haskell还比较新。

更简洁一点，使用inline方式写出mapM和iterate:

更简短的写法是内联使用mapM和iterate函数：

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

- CiscoIPPhone

---

我加入了一些技巧：List vs Data.List； 使用do表示法而不是concatMap；使用迭代。 - Josh Lee

一些小改进来得到85：m x=do a:b<-group x;show(length b+1)++[a]（模式匹配）和 main=mapM putStrLn$iterate m"1"（main 可以是 IO a 而不是 IO ()，而 $ 可以省略括号）。 - Olathe

Answer 3

Perl（46个字符）

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

额外加分（52个字符）

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

- Bizangles

---

在阅读其他解决方案之前，我已经完成了这个任务。采用另一个Perl答案中的“重做”建议可以将这些解决方案减少3个字符。 - Bizangles

我认为“-l”通常需要三个字符。 - Nabb

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

- David Murdoch

---

substr()比substring()短，如果您只传入一个参数，则执行相同的作业。 - Harmen

Answer 5

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

- Dr. belisarius

Answer 6

Perl, 46 characters

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

额外加分，51个字符：

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

- Hasturkun

---

你可以去掉两个分号，使用for(;;)，并且句子修饰语（在句子末尾）不需要括号，可以减少4个字符。 - ninjalj

根据我上面的评论，你可以在一个块中使用redo来达到相同的效果，节省两个字符。 :-) - Platinum Azure

还是多了一个字符。如上所述，句子修饰语不需要括号。 - ninjalj

此外，^ 锚点不是必需的，s/// 记住它上次检查的字符。 - ninjalj

这个程序在输出的第一行没有打印出“1”（或输入值）。你应该将print和s///交换放置在while循环中。此外，$+[0]-$-[0]比length($&)更长。 - Plutor

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

E.g.:

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

- user319799

---

尽可能将语句放在同一行以减少字符数。您可以将几个换行符/制表符组合替换为分号。如果能在深度缩进的行中实现这一点，效果会更好。 - Chris Lutz

制表符可以被空格替代。只需在第一级缩进一个空格，在第二级缩进两个空格，以此类推... - phkahler

@phkahler 选项卡和空格都是一个字符。然而，交替使用空格/制表符/空格+制表符可以稍微节省一些字符。 - Nabb

Answer 8

这是我使用LINQ的C#尝试和第一次尝试代码高尔夫：

C# - 包括C#样板在内，共198字节（包括额外积分）

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

- GeReV

---

将args参数重命名可以再节省6个字符。 - Dirk Vollmar

将 "int i = value.TakeWhile(d => d == value[0]).Count();" 转换为 "int i = 0; while (i < v.Length && v[i] == v[0]) i++;" 可以让您删除使用的Linq。 - MikeP

@MikeP，我实际上想要使用LINQ来做这件事，只是作为一种练习。 - GeReV

Answer 9

这里是我的实现（使用Prolog）：

使用DCGs的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).

普通基础的Prolog，代码更易读（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]).

输出莫里斯序列： m(D)。其中D是“起始”数字。

- gusbro

---

我原本想点赞，但我太讨厌Prolog了，所以我做不到。 - rerun

Answer 10

Ruby — 52

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

任务太简单，而且过于 Perl 风格...

- Nakilon