高尔夫代码：格雷码

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 个字符版本克服了 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（⌽ 是“旋转”字符）

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

实际上我不'不知道是否允许使用个人语言，因为不可能！仍在开发中，但我还是想发布它..）

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

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

用交互剪切两笔画，用单行剪切一笔。

旧版本：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 位格雷码。 makegray 代码函数以嵌套方式将 addbit 函数应用于 1 位格雷码，{{ 0}、{1}}，直到创建 n 位版本。 charactercode 函数仅打印 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

直接 Python 实现构建n位格雷码维基百科上的 ：

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

Answer 10

C，203 个字符

这是 C 语言的祭品：

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    char s[256];
    int b, i, j, m, g;

    gets(s);
    b = atoi(s);

    for (i = 0; i < 1 << b; ++i)
    {
        g = i ^ (i / 2);
        m = 1 << (b - 1);

        for (j = 0; j < b; ++j)
        {
            s[j] = (g & m) ? '1' : '0';
            m >>= 1;
        }
        s[j] = '\0';
        puts(s);
    }
    return 0;
}

Answer 11

C#，149143 个字符

C# 并不是代码高尔夫的最佳语言，但我想我还是会尝试一下。

static void Main(){var s=1L<<int.Parse(Console.ReadLine());for(long i=0;i<s;i++){Console.WriteLine(Convert.ToString(s+i^i/2,2).Substring(1));}}

可读版本：

static void Main()
{
    var s = 1L << int.Parse(Console.ReadLine());
    for (long i = 0; i < s; i++)
    {
        Console.WriteLine(Convert.ToString(s + i ^ i / 2, 2).Substring(1));
    }
}

Answer 12

这是我的 Fantom 祭品

public static Str[]grayCode(Int i){if(i==1)return["0","1"];else{p:=grayCode(i-1);p.addAll(p.dup.reverse);p.each|s,c|{if(c<(p.size/2))p[c]="0"+s;else p[c]="1"+s;};return p}}

（177 个字符）

或扩展版本：

 public static Str[] grayCode(Int i)  
 {      
   if (i==1) return ["0","1"]
   else{
     p := grayCode(i-1);
     p.addAll(p.dup.reverse);
     p.each |s,c| 
     { 
       if(c<(p.size/2))   
       {
         p[c] = "0" + s
       }
       else
       {
         p[c] = "1" + s
       }  
     }
    return p
    }
  }

Answer 13

F#，152 个字符

let m=List.map;;let rec g l=function|1->l|x->g((m((+)"0")l)@(l|>List.rev|>m((+)"1")))(x - 1);;stdin.ReadLine()|>int|>g["0";"1"]|>List.iter(printfn "%s")

Answer 14

F# 180 175 字符过多

今天早上我做了另一个版本，简化了递归版本，但可惜的是，由于递归，它不会执行100000。

递归解决方案：

let rec g m n l =
    if(m = n) then l
    else List.map ((+)"0") l  @ List.map ((+)"1") (List.rev(l)) |> g (m+1) n
List.iter (fun x -> printfn "%s" x) (g 1 (int(stdin.ReadLine())) ["0";"1"]);;

完成后，我为“100000”要求创建了一个工作版本 - 它太长了，无法与此处显示的其他解决方案竞争，而且我可能多次重新发明轮子，但与我在这里看到的许多解决方案不同，它将使用非常非常多的位数，嘿，这对于 F# 菜鸟来说是一次很好的学习体验 - 我没有费心去缩短它，因为它太长了无论如何;-)

迭代解决方案：（使用 100000+）

let bits = stdin.ReadLine() |>int
let n = 1I <<< bits

let bitcount (n : bigint) =
    let mutable m = n
    let mutable c = 1
    while m > 1I do
        m <- m >>>1
        c<-c+1
    c

let rec traverseBits m (number: bigint) =
    let highbit = bigint(1 <<< m)
    if m > bitcount number
    then number
    else
        let lowbit = 1 <<< m-1
        if (highbit&&& number) > 0I
        then
            let newnum = number ^^^ bigint(lowbit)
            traverseBits (m+1) newnum
        else traverseBits (m+1) number

let res =  seq 
            { 
              for i in 0I..n do
                yield traverseBits 1 i
            }

let binary n m = seq 
                  {
                    for i = m-1 downto 0 do
                        let bit = bigint(1 <<< i)
                        if bit &&&n > 0I
                        then yield "1"
                        else yield "0"
                  }

Seq.iter (fun x -> printfn "%s"  (Seq.reduce (+) (binary x bits))) res

Answer 15

Lua，156 个字符

这是我在 Lua 中的尝试，尽可能接近它。

LuaJIT（或带 lua-bitop 的 lua）：156 字节

a=io.read()n,w,b=2^a,io.write,bit;for x=0,n-1 do t=b.bxor(n+x,b.rshift(x,1))for k=a-1,0,-1 do w(t%2^k==t%n and 0 or 1)t=t%2^k==t and t or t%2^k end w'\n'end

Lua 5.2：154 字节

a=io.read()n,w,b=2^a,io.write,bit32;for x=0,n-1 do t=b.XOR(n+x,b.SHR(x,1))for k=a-1,0,-1  do w(t%2^k==t%n and 0 or 1)t=t%2^k==t and t or t%2^k end w'\n'end

Answer 16

在无剪切的 Prolog 中（如果删除“<<”后的空格，则为 138 个字节；提交编辑器会截断最后一行而不包含它）：

b(N,D):-D=0->nl;Q is D-1,H is N>>Q/\1,write(H),b(N,Q).

c(N,D):-N=0;P is N xor(N//2),b(P,D),M is N-1,c(M,D).

:-read(N),X is 1<< N-1,c(X,N).

Answer 17

红宝石，50 个字符

(2**n=gets.to_i).times{|i|puts"%0#{n}d"%i.to_s(2)}