algorithm - 代码高尔夫：格雷代码

Question

挑战

按字符数计算的最短程序，输出 n 位格雷码。n将是一个小于（由于用户建议）从标准输入中获取的任意数字。格雷码将打印在标准输出中，如示例中所示。~~1000~~100000

注意：我不希望程序在合理的时间内打印格雷码（n=100000有点矫枉过正）；我确实希望它开始打印。

例子

输入：

预期输出：

score 23 · Accepted Answer

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['']

score 17 · Accepted Answer

17

于 2010-11-08T00:13:57.377 回答

score 14 · Accepted Answer

不可能的！语言（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!仍在开发中，但我还是想发布它..）

score 14 · Accepted Answer

Golfscript - 27 个字符

从标准输入读取，写入标准输出

~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

score 12 · Accepted Answer

红宝石 - 49 个字符

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

这适用于 n=100000 没有问题

score 7 · Accepted Answer

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

score 6 · Accepted Answer

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

用interact 剪出两笔，一笔用unlines。

较旧：89 个字符：

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

请注意，懒惰让您免费获得即时输出。

score 5 · Accepted Answer

Mathematica 50 Chars

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

Thanks to A. Rex for suggestions!

Previous attempts

Here is my attempt in Mathematica (140 characters). I know that it isn't the shortest, but I think it is the easiest to follow if you are familiar with functional programming (though that could be my language bias showing). The addbit function takes an n-bit gray code and returns an n+1 bit gray code using the logic from the wikipedia page.. The make gray code function applies the addbit function in a nested manner to a 1 bit gray code, {{0}, {1}}, until an n-bit version is created. The charactercode function prints just the numbers without the braces and commas that are in the output of the addbit function.

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

score 4 · Accepted Answer

在 Wikipedia 上Constructing an n- bit Gray code中描述的简单 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

score 4 · Accepted Answer

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

score 3 · Accepted Answer

C#，149 143 个字符

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

score 2 · Accepted Answer

这是我的 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
    }
  }

score 2 · Accepted Answer

F#, 152 characters

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

score 2 · Accepted Answer

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

score 0 · Accepted Answer

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

score 0 · Accepted Answer

在无剪切的 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).

score -1 · Accepted Answer

-1

红宝石，50 个字符

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

于 2011-01-18T21:07:34.740 回答