Code Golf: Gray Code

问题:

The Challenge

The shortest program by character count that outputs the n-bit Gray Code. n will be an arbitrary number smaller than 1000100000 (due to user suggestions) that is taken from standard input. The gray code will be printed in standard output, like in the example.

Note: I don't expect the program to print the gray code in a reasonable time (n=100000 is overkill); I do expect it to start printing though.

Example

Input:

4

Expected Output:

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

回答1:

Python - 53 chars

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

This 54 char version overcomes the limitation of range in Python2 so n=100000 works!

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

69 chars

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

75 chars

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

回答2:

APL (29 chars)

With the function F as (⌽ is the 'rotate' char)

z←x F y
z←(0,¨y),1,¨⌽y

This produces the Gray Code with 5 digits (⍴ is now the 'rho' char)

F/5⍴⊂0,1

The number '5' can be changed or be a variable.

(Sorry about the non-printable APL chars. SO won't let me post images as a new user)

回答3:

Impossible! language (54 58 chars)

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

Test run:

./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

(actually I don't know if personal languages are allowed, since Impossible! is still under development, but I wanted to post it anyway..)

回答4:

Golfscript - 27 chars

Reads from stdin, writes to stdout

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

Sample run

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

回答5:

Ruby - 49 chars

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

This works for n=100000 with no problem

回答6:

C++, 168 characters, not including whitespaces:

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

回答7:

Haskell, 82 characters:

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

Point-free style for teh win! (or at least 4 fewer strokes). Kudos to FUZxxl.

previous: 86 characters:

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

Cut two strokes with interact, one with unlines.

older: 89 characters:

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

Note that the laziness gets you your immediate output for free.

回答8:

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]

回答9:

Straightforward Python implementation of what's described in Constructing an n-bit Gray code on Wikipedia:

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

Test:

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

回答10:

C, 203 Characters

Here's a sacrificial offering, in 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;
}

回答11:

C#, 149143 characters

C# isn't the best language for code golf, but I thought I'd go at it anyway.

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

Readable version:

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

回答12:

And here is my Fantom sacrificial offering

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)

Or the expanded version:

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

回答13:

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

回答14:

F# 180 175 too many characters

This morning I did another version, simplifying the recursive version, but alas due to recursion it wouldn't do the 100000.

Recursive solution:

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

After that was done I created a working version for the "100000" requirement - it's too long to compete with the other solutions shown here and I probably re-invented the wheel several times over, but unlike many of the solutions I have seen here it will work with a very,very large number of bits and hey it was a good learning experience for an F# noob - I didn't bother to shorten it, since it's way too long anyway ;-)

Iterative solution: (working with 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

回答15:

Lua, 156 chars

This is my throw at it in Lua, as close as I can get it.

LuaJIT (or lua with lua-bitop): 156 bytes

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 bytes

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

回答16:

In cut-free Prolog (138 bytes if you remove the space after '<<'; submission editor truncates the last line without it):

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

回答17:

Ruby, 50 Chars

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