11
\$\begingroup\$

The Gray Code is a sequence of binary numbers of bitwidth n where successive numbers differ only in one bit (see example output).

Reference

Example input:

3

Example output:

000
001
011
010
110
111
101
100

Notes:

  • This question seems to have a dupe but it's not, for that question is not a code-golf, and it demands different output. It will help to check out it's answers, though.
  • You may assume a variable n which contains the input.
\$\endgroup\$
  • 6
    \$\begingroup\$ Considering that the other question is a fastest-code code-challenge without an objective winning criterion (fastest measured how?), I propose closing the other and reopening this one. \$\endgroup\$ – Dennis Jul 3 '14 at 12:59
  • 2
    \$\begingroup\$ I agree with @dennis and therefore I have upvoted the following unpopular answer on the original question. "If the answer you are looking for is strictly a fast result, then if you declare an array (of the gray codes)..." However the original question aready has a 7-character and a 4-character answer so I don´t see much room for improvement. Therefore I am not casting a reopen vote at present. \$\endgroup\$ – Level River St Jul 3 '14 at 13:10
  • 3
    \$\begingroup\$ It's awfully similar to Traverse all numbers with only one bit flip per step though... \$\endgroup\$ – Dennis Jul 3 '14 at 13:58
  • \$\begingroup\$ The earliest Gray code question isn't great, but it already has answers which are fundamentally the same as the answers which this question wants, and which are not likely to be improved. I think it would have made more sense to leave this one closed and change the other one to a code golf. \$\endgroup\$ – Peter Taylor Jul 3 '14 at 15:57

16 Answers 16

2
\$\begingroup\$

JavaScript (77)

for(i=0;i<1<<n;)alert((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))

More browser-friendly version (console.log and prompt()):

n=prompt();for(i=0;i<1<<n;)console.log((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))
\$\endgroup\$
  • \$\begingroup\$ Maybe this array...join is overkill for(i=0;i<(l=1<<n);i++)console.log((i^(i>>1)|l).toString(2).slice(1)); \$\endgroup\$ – edc65 Jul 3 '14 at 16:00
2
\$\begingroup\$

Python 2 (47)

for i in range(2**n):print bin(2**n+i/2^i)[3:]

The expression i/2^i for the i'th gray code number is from the this answer. To add leading zeroes that pad to length n, I add 2**n before converting to a binary string, creating a string of length n+1. Then, I truncate the leading 1 and number type prefix 0b with [3:].

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 10 bytes

+~0=':!n#2

Try it online!

\$\endgroup\$
  • \$\begingroup\$ the odometer overload of ! took me by surprise. very cool ! \$\endgroup\$ – scrawl Aug 21 at 15:11
2
\$\begingroup\$

APL (Dyalog Classic), 11 bytes

2≠/0,↑,⍳n⍴2

Try it online!

n⍴2 is 2 2...2 - a vector of n twos

is the indices of an n-dimensional array with shape 2 2...2 - that is, a 2×2×...×2 array of nested vectors. As we use 0-indexing (⎕IO←0), those are all binary vectors of length n.

, flatten the 2×2×...×2 shape, so we get a vector of 2n nested binary vectors

"mix" - convert the vector of vectors to a solid 2n×n matrix. It looks like this:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

0, prepends zeroes to the left of the matrix

2≠/ computes the pairwise (2) xor () along the last dimension (/ as opposed to ); in other words, every element gets xor-ed with its right neighbour, and the last column disappears

0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
\$\endgroup\$
  • \$\begingroup\$ would you mind adding a quick explanation? \$\endgroup\$ – Jonah Jul 9 '18 at 5:14
  • 1
    \$\begingroup\$ @Jonah sure, added \$\endgroup\$ – ngn Jul 9 '18 at 9:37
  • \$\begingroup\$ very clever, thx \$\endgroup\$ – Jonah Jul 9 '18 at 12:51
2
\$\begingroup\$

Japt, 14 12 bytes

2pU Ç^z)¤ùTU

Shaved off two bytes thanks to ETHproductions.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Perfect example of how ù is used. Since N.z(n) is integer division with default arg = 2, you can save two bytes with 2pU Ç^z)¤ùTU: Try it online! \$\endgroup\$ – ETHproductions Jul 9 '18 at 18:31
  • \$\begingroup\$ @ETHproductions Thanks, I still miss the default args every now and then. Very handy, thanks a lot. \$\endgroup\$ – Nit Jul 9 '18 at 18:43
1
\$\begingroup\$

Python - 54

Based off of an algorithm from the reference given in the challenge:

for i in range(2**n):print'{1:0{0}b}'.format(n,i>>1^i)

Ungolfed:

# For each of the possible 2**n numbers...
for num in range(2**n):
    gray = num>>1 ^ num

    # Print in binary and pad with n zeros.
    print '{1:0{0}b}'.format(grey)
\$\endgroup\$
1
\$\begingroup\$

PowerShell(168)

Amateur PowerShell'r back with another attempt at golF! Hope you don't mind! At the very least these questions are fun, and a learning experience to boot. Assuming n has been inputted, we have:

$x=@('0','1');for($a=1;$a-lt$n;$a++){$x+=$x[($x.length-1)..0];$i=[Math]::Floor(($x.length-1)/2);0..$i|%{$x[$_]='0'+$x[$_]};($i+1)..($x.length-1)|%{$x[$_]='1'+$x[$_]}}$x

Because the PowerShell I'm working with is only 2.0, I can't use any bit shifting cmdlets which might make for shorter code. So I took advantage of a different method described in the question source, flipping the array and adding it to itself, appending a 0 to the front of the top half, and a 1 to the bottom half.

\$\endgroup\$
1
\$\begingroup\$

F# (86) (84) (80)

for i in 0..(1<<<n)-1 do printfn"%s"(Convert.ToString(i^^^i/2,2).PadLeft(n,'0'))

This could probably be improved further.

Also note, if run in FSI, you'd need to open System;; first. If you'd like to avoid importing that, (and if you don't care about the order in which the values are printed) you can use this 82-character version:

for i in 0..(1<<<n)-1 do(for j in 0..n-1 do printf"%i"((i^^^i/2>>>j)%2));printfn""
\$\endgroup\$
1
\$\begingroup\$

Ruby — 42 39

Same algorithm, different language:

(2**n).times{|b|puts"%0#{n}b"%(b>>1^b)}

Switching from #map to #times as @voidpigeon suggests saves 3 characters.

\$\endgroup\$
  • 1
    \$\begingroup\$ Instead of [*0...2**n].map you can use (2**n).times. \$\endgroup\$ – afuous Jul 7 '14 at 18:08
1
\$\begingroup\$

J, 24 bytes

[:#:@(22 b.<.@-:)[:i.2^]

Try it online!

Straightforward implementation of the "XOR with it's own floored half" algorithm. Note that 22 b. is XOR.

\$\endgroup\$
1
\$\begingroup\$

MATL, 10 bytes

W:qt2/kZ~B

Try it online!

The good old "XOR n with n>>2" method.

W - compute 2^(input) (gets input implicitly)
:q - create range of numbers from 0 to 2^n - 1
t - duplicate that range
2/k - MATL doesn't have bitshift, so divide (each number) by 2 and floor
Z~ - elementwise XOR that result with the original 0 to 2^n - 1 array
B - convert each number in the result to binary
(Implicitly display output.)

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 25 bytes

{(x-1){,/0 1,''|:\x}/0 1}

Try it online!


  • |:\xis "reverse scan x". applies reverse to x until the output equals the input, and shows each iteration. returns (0 1; 1 0) on first pass.
  • 0 1,'' is "0 1 join each each". joins a 0 to each value of 1st elem, and 1 to each value of 2nd elem, giving ((0 0; 0 1);(1 1; 1 0)) on first pass
  • ,/ is "join over", and flattens to list.
  • (x-1){...}/0 1is "apply {func} over 0 1 x-1 times". takes the output of the last iteration as input
\$\endgroup\$
0
\$\begingroup\$

APL (22)

{(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1

This outputs a n-by-2^n matrix containing the bits as its rows:

      n←3
      {(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

Explanation:

  • {...}⍣(n-1)⍪0 1: run the function n-1 times with initial input the matrix (0 1)T (which is the 1-bit gray code)

    • (0,⍵): each row of with a 0 prefixed,
    • : on top of,
    • 1,⊖⍵: each row of with an 1 prefixed, in reversed order
\$\endgroup\$
0
\$\begingroup\$

Jq 1.5, 105 100 bytes

def g(n):if n<2then. else map([0]+.)+(reverse|map([1]+.))|g(n-1)end;[[0],[1]]|g(N)[]|map("\(.)")|add

Assumes N provides input. e.g.

def N: 3 ;

Expanded

def g(n):  # recursively compute gray code
  if n < 2
  then .
  else map([0]+.) + (reverse|map([1]+.)) | g(n-1)
  end;

  [[0],[1]]                 # initial state
| g(N)[]                    # for each element in array of gray codes
| map("\(.)")|add           # covert to a string

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 10 bytes

³Ç¤ÅÃf_Ê¥U

Try it online!

\$\endgroup\$
-1
\$\begingroup\$

T-SQL 134

This challenge is asking to return the Cartesian power of {(0),(1)}. This snippet builds the code which would execute the Cartesian product of {(0),(1)} n times.

DECLARE @ int=4,@s varchar(max)='SELECT*FROM's:set @s+='(VALUES(0),(1))t'+ltrim(@)+'(b)'if @>1set @s+=','set @-=1if @>0goto s exec(@s)
\$\endgroup\$
  • \$\begingroup\$ It's asking for the cartesian power in a specific order. Does your code account for that? \$\endgroup\$ – ToonAlfrink Feb 25 '17 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.