Code Golf:格雷码

Question

挑战

输出n位格雷码的字符数最短的程序.n将是一个小于(由于用户建议)从标准输入中获取的任意数字.格雷码将以标准输出打印,如示例中所示.1000100000

注意:我不希望程序在合理的时间内打印格雷码(n=100000过度杀伤); 我确实希望它开始打印.

例

输入:

4

预期产出:

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

Answer 1

Python - 53个字符

n=1<<input()
for x in range(n):print bin(n+x^x/2)[3:]

这个54 char版本克服了Python2中范围的限制,因此n = 100000可以工作!

x,n=0,1<<input()
while n>x:print bin(n+x^x/2)[3:];x+=1

69个字符

G=lambda n:n and[x+y for x in'01'for y in G(n-1)[::1-2*int(x)]]or['']

75个字符

G=lambda n:n and['0'+x for x in G(n-1)]+['1'+x for x in G(n-1)[::-1]]or['']

Answer 2

APL(29个字符)

使用函数F as(?是'rotate'char)

z?x F y
z?(0,¨y),1,¨?y

这会产生5位数的格雷码(?现在是'rho'字符)

F/5??0,1

数字'5'可以改变或是变量.

(抱歉,不可打印的APL字符.所以不允许我以新用户的身份发布图片)

Answer 3

不可能!语言(54 58个字符)

#l{'0,'1}1[;@l<][%;~['1%+].>.%['0%+].>.+//%1+]<>%[^].>

测试运行:

./impossible gray.i! 5
Impossible v0.1.28
00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000

(实际上我不知道是否允许使用个人语言,因为Impossible!仍处于开发阶段,但无论如何我想发布它...)

Answer 4

Golfscript - 27个字符

从stdin读取,写入stdout

~2\?:),{.2/^)+2base''*1>n}%

样品运行

$ echo 4 | ruby golfscript.rb gray.gs 
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

Answer 5

红宝石 - 49个字符

(1<<n=gets.to_i).times{|x|puts"%.#{n}b"%(x^x/2)}

这适用于n = 100000,没有问题

Answer 6

C++,168个字符,不包括空格:

#include <iostream>
#include <string>

int r;

void x(std::string p, char f=48)
{
    if(!r--)std::cout<<p<<'\n';else
    {x(p+f);x(p+char(f^1),49);}
    r++;
}
int main() {
    std::cin>>r;
    x("");
    return 0;
}

Answer 7

Haskell,82个字符:

f a=map('0':)a++map('1':)(reverse a)
main=interact$unlines.(iterate f[""]!!).read

获胜的无点风格!(或至少减少4次击球).感谢FUZxxl.

上一个:86个字符:

f a=map('0':)a++map('1':)(reverse a)
main=interact$ \s->unlines$iterate f[""]!!read s

用相互作用剪切两个笔画,一个用unlines剪辑.

年龄:89个字符:

f a=map('0':)a++map('1':)(reverse a)
main=readLn>>= \s->putStr$concat$iterate f["\n"]!!s

请注意,懒惰可以免费为您提供即时输出.

Answer 8

Mathematica 50 Chars

Nest[Join["0"<>#&/@#,"1"<>#&/@Reverse@#]&,{""},#]&

感谢A. Rex的建议!

以前的尝试

这是我在Mathematica(140个字符)中的尝试.我知道它不是最短的,但我认为如果你熟悉函数式编程,这是最容易理解的(虽然这可能是我的语言偏见).addbit函数采用n位格雷码并使用维基百科页面中的逻辑返回n + 1位格雷码.make格雷码函数以嵌套方式将addbit函数应用于1位格雷码{{{ 0},{1}},直到创建n位版本.字符代码功能只打印数字,而不显示addbit函数输出中的大括号和逗号.

addbit[set_] := 
 Join[Map[Prepend[#, 0] &, set], Map[Prepend[#, 1] &, Reverse[set]]]
MakeGray[n_] := 
 Map[FromCharacterCode, Nest[addbit, {{0}, {1}}, n - 1] + 48]

Answer 9

维基百科上构造n位格雷码中描述内容的直接 Python 实现：

import sys

def _gray(n):
  if n == 1:
    return [0, 1]
  else:
    p = _gray(n-1)
    pr = [x + (1<<(n-1)) for x in p[::-1]]
    return p + pr

n = int(sys.argv[1])
for i in [("0"*n + bin(a)[2:])[-n:] for a in _gray(n)]:
  print i

（233 个字符）

测试：

$ python gray.py 4
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000