Code Golf: Gray Code

Question

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

Spectra

Given that CW is not available on questions without the intervention of the mods it is time for [code-golf] to leave Stack Overflow. The Stack Exchange proposal Code Golf & Programming Puzzles would be a good place, but it requires more commitments before it can go beta... – Insensitive

Converted it to community wiki. – Her

A lot of the recursive solutions (including mine I suspect) will probably be breaking when n=999 (and since part of the spec is currently that n can be up to 1000)... – Balbo

If another forum goes live, hopefully existing CG questions can get migrated. – Faught

@John, and hopefully the rep will be counted when they are migrated :) – Hoshi

n=100000 seems a bit excessive, no? For 4 bit gray code there are 16 entries each 4 chars long. This works out to 64 bytes. Extrapolating up for the original 1000 bit gray code would require 1.02e298 megabytes. I think this would break everyone's solution, just the recursive ones. – Gerald

@samsdram I don't expect any solution to print all the code. But I do expect it to start printing – Spectra

@Gabi: what is the point of having n greater than say 32 or 64 ? It seems like an arbitrary and unnecessary requirement ? – Mathildamathilde

Anyone see where the perl guys went? – Hoshi

«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.» Does that mean that a program that just prints the first permutation is fine? It doesn't print the whole Gray Code in a reasonable time, it needs an infinite time and enough bit-flips caused by cosmic rays to eventually print the whole code. – Kathleenkathlene

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

Submariner

You don't use standard input/output – Spectra

@Gabi, brand new iterative solution, uses stdin/stdout – Hoshi

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

Tarnopol

To use input from keyboard; replace '5' by ( 'Execute' 'QuoteQuad' ). This adds 3 chars :-/ – Tarnopol

Answer 3

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

Hoshi

Answer 4

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

Obbligato

As long as the language isn't specifically created to solve this problem it's allowed. – Tybi

Of course this language is not created to solve this problem :) It's a general purpose esoteric language or something like that.. – Obbligato

This actually looks like a nifty esoteric language (and far more useful than some!). Reminds of a terse form of HP RPN code :p But when the APL/J-golfers get in... – Spoonerism

I'm still working on it, but I doubt I can get near to APL or J.. Thanks for the compliment, anyway :) – Obbligato

@Obbligato please provide a link to download the compiler, so other people can test your solution – Spectra

I'm still developing it, in any case it is not a compiler but an interpreter :) I'll try to accelerate the work and release it in a couple of days then! – Obbligato

Answer 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

Submariner

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

Preset

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

Monopolist

Is it possible to use interact here? – Cryolite

You could also remove unlines and expect input as in cat "123" | myprog, which should be legal. – Cryolite

It already expects input that way. unlines is used to make the output into a string for interact. – Monopolist

... the additional stroke saved was that (unlines + "") is one shorter than (concat + "\n") – Monopolist

This is also possible: main=interact$unlines.(iterate f[""]!!).read. Saves 4 chars. – Cryolite

Answer 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]

Buddhi

I fear this looks exactly like line noise, but here's 85 characters: p=Prepend;f=FromCharacterCode/@(Nest[Join[#~p~0&/@#,#~p~1&/@Reverse[#]]&,{{}},#]+48)& – Barraza

Edited to post 91 chars solution, but @A. Rex posted a shorter one in the previous comment. Rolling back to leave only the better one. – Downthrow

@belisarius: Using some of your ideas, it's possible to get even shorter. j=Join;f=FromCharacterCode/@Nest[j[{48}~j~#&/@#,{49}~j~#&/@Reverse[#]]&,{{}},#]& – Barraza

A lot shorter: f=Nest[Join["0"<>#&/@#,"1"<>#&/@Reverse@#]&,{""},#]& – Barraza

@A. Rex Or for 50 char remove the "f=" and invoke with %[n] – Downthrow

@A. Rex It is very curious that using strings is more "golf-prone" than going with lists! – Downthrow

Answer 9

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

Mathildamathilde

The input/output are stdin and stdout – Spectra

Now fixed - uses stdin for input – Mathildamathilde

Answer 10

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

Vallonia

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

Docia

this won't work for n > 64, unfortunately there's no variable type in C# that can hold 1<<n with n > 64. – Risser

@Risser Did you try it? There's a reason I'm casting the 1 as long, it works fine with 100000 for me. – Cenobite

as far as I remember when I tried it (and that made sense) the value of the long rolls over and becomes negative at a certain value - it will work, just not the way it is supposed to. – Risser

@Risser Darn, you're right! I'll keep looking into this. – Cenobite

despite being broken, there are some typical golfing changes missed here. 1) dont need brackets on a single line for, 2) declare s as long and move initialization of i outside the loop, 3) apply the postfix increment operator on i to the last use in the loop and remove it from the for structure, 4) use Remove(start, length) instead of substring, with these changes you should be able to shave 5 characters – Fulcrum

your code shortened to 135 characters: static void Main(){long i=0,s=1<<int.Parse(Console.ReadLine());while(i<s)Console.WriteLine(Convert.ToString(s+i^i++/2,2).Remove(0,1));} – Farther

Answer 12

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

Risser

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

Farrier

I couldn't resist golfing this a bit further (143 chars): let m=List.map;;let rec g l=function|1->l|x->g(m((+)"0")l@m((+)"1")(List.rev l))(x-1);;stdin.ReadLine()|>int|>g["0";"1"]|>Seq.iter(printfn"%s") – Etch

Answer 14

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

Mckenzie

Answer 15

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

Titled

Answer 16

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

Revell

Answer 17

Ruby, 50 Chars

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

Suellensuelo