Code Golf:格雷码

挑战 输出n位格雷码的字符数最短的程序。
n
将是一个小于
1000
100000
的任意数字(由于用户建议),它取自标准输入。格雷码将以标准输出打印,如示例中所示。 注意:我不希望程序在合理的时间内打印格雷码(
n=100000
是过度杀伤);我确实希望它开始打印。 例 输入:
4
预期产出:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
    
已邀请:
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['']
    
APL(29个字符) 使用函数F as(
是'rotate'char)
z←x F y
z←(0,¨y),1,¨⌽y
这产生了5位数的格雷码(
现在是'rho'字符)
F/5⍴⊂0,1
数字'5'可以改变或是变量。 (抱歉,不可打印的APL字符。所以不允许我以新用户的身份发布图片)     
不可能!语言(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!仍在开发中,但无论如何我想发布它。)     
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
    
红宝石 - 49个字符
(1<<n=gets.to_i).times{|x|puts"%.#{n}b"%(x^x/2)}
这适用于n = 100000,没有问题     
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;
}
    
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
请注意,懒惰可以免费为您提供即时输出。     
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]
    
在Wikipedia上构造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
    
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] = '';
        puts(s);
    }
    return 0;
}
    
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));
    }
}
    
这是我的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 char) 或者扩展版本:
 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
    }
  }
    
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")
    
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#noob来说这是一个很好的学习经验 - 我没有费心缩短它,因为它反正太长了;-) 迭代解决方案:(使用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
    
Lua,156个字符 这是我在Lua的投掷,尽可能接近它。 LuaJIT(或lua与lua-bitop):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
    
在无剪切的Prolog中(如果在'&lt;&lt;&lt;'之后删除空格,则为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).
    
红宝石,50个字符
(2**n=gets.to_i).times{|i|puts"%0#{n}d"%i.to_s(2)}
    

要回复问题请先登录注册