代码高尔夫: 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 提供, 点击上面的

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

- Plutor · Answer 1

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)

- Hasturkun · Answer 2

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

- user372743 · Answer 3

Java

我第一次尝试“代码高尔夫”，在我的IB CS课上的某个时间段内，我随便写了以下内容：

238压缩字符

压缩后的代码:

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

格式正确：

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

- pdehaan · Answer 4

Perl（额外加分），47个字符

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

- supercat · Answer 5

如果一个字符串只包含数字1-3，并且不包含超过三个连续数字，则称其为“Morris-ish”。如果初始字符串是Morris-ish，则从中生成的所有字符串也将是Morris-ish。同样，如果初始字符串不是Morris-ish，则除非将大于十的数字视为数字组合（例如，如果11111111111被视为折叠成三个一而不是一个“十一”和一个一），否则不会生成任何Morris-ish字符串。

鉴于此观察结果，每个以Morris-ish种子开始的迭代都可以作为以下查找/替换操作序列完成：

111 -> CA 11 -> BA 1 -> AA 222 -> CB 22 -> BB 2 -> AB 333 -> CC 33 -> BC 3 -> AC A -> 1 B -> 2 C -> 3

请注意，在进行上述替换之前，序列是Morris-ish的，每个生成的对的第二个字符将与前一个和后一个对的第二个字符不同；因此不可能有超过三个相同的字符序列。

我想知道有多少个不相交的Morris-ish序列？

- David · Answer 6

J, 44个字符带额外加分项

(([:,#;.1@{:,.{:#{.)@(,:0<1,[:|2-/\]))^:(<9)

不幸的是，它仅生成了9次迭代，但迭代计数<9可以调整为任何值。将其设置为a:会生成无限序列，但显然无法打印。

用法：

   (([:,#;.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

- Andreas Rejbrand · Answer 7

Delphi

Delphi是一种不太适合用于高尔夫比赛的编程语言，但仍然有其独特之处:

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.

这段代码大小为211字节（并且可以直接编译）。

- Harmen · Answer 8

PHP: 111

这是我第一次尝试代码高尔夫，对结果感到相当满意。

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

提供：

> php htdocs/golf.php
1
11
21
... (endless loop)

PHP加分项：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--);}}

提供：

> php htdocs/golf.php 4
4
14
1114
3114
... (to infinity and beyond)

- BalusC · Answer 9

Java - 167个字符（附加信用）

_{（不包括类/主要样板，共122个字符）}

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

带有换行符：

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

- BoltClock · Answer 10

PHP, 128 122 112 字节（含起始标签）

~~122~~ ~~116~~ 106 字节（不含起始标签和前导空格），这是我的第一次尝试 Code Golf，希望您在评价中给予宽容。

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

虽然有点可惜，但我必须将$a初始化为字符串，这样会多消耗2个字节，否则我无法使用索引符号。

输出

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

PHP（额外加分），使用开标签117字节

不包括开头的<?php标签和前导空格，共111字节。

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

输出

$ php morris.php 3
3
13
1113
3113
132113
1113122113
...
^C
$ php morris.php 614
614
161114
11163114
3116132114
1321161113122114
1113122116311311222114
...

PHP (额外加分)，带有开闭标签的未压缩版本

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

?>