CODEWITHSUNDEEP
algorithmcode-golfgray-code
Gabi Purcaru
Gabi Purcaru

Reputation: 31564

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

Upvotes: 22

Views: 8015

Answers (17)

c2h2
c2h2

Reputation: 12369

Ruby, 50 Chars

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

Upvotes: -1

Samsdram
Samsdram

Reputation: 1635

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]

Upvotes: 5

spillner
spillner

Reputation: 394

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

Upvotes: 0

jpjacobs
jpjacobs

Reputation: 9559

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

Upvotes: 0

comingstorm
comingstorm

Reputation: 26117

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.

Upvotes: 6

Paul R
Paul R

Reputation: 213060

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

Upvotes: 4

Jess
Jess

Reputation: 42948

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

Upvotes: 3

BrokenGlass
BrokenGlass

Reputation: 160952

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

Upvotes: 2

Eugene Smith
Eugene Smith

Reputation: 9398

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

Upvotes: 7

John La Rooy
John La Rooy

Reputation: 304375

Ruby - 49 chars

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

This works for n=100000 with no problem

Upvotes: 12

John La Rooy
John La Rooy

Reputation: 304375

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

Upvotes: 23

John La Rooy
John La Rooy

Reputation: 304375

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

Upvotes: 14

Jack
Jack

Reputation: 133609

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

Upvotes: 14

ljs
ljs

Reputation: 37817

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

Upvotes: 2

user500183
user500183

Reputation:

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)

Upvotes: 17

Daniel Fath
Daniel Fath

Reputation: 18109

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

Upvotes: 2

Richard Fearn
Richard Fearn

Reputation: 25501

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

Upvotes: 4

Related Questions