36
\$\begingroup\$

Introduction

A Gray Code is an alternative to binary representation in which a number is incremented by toggling only one bit, rather than a variable amount of bits. Here are some gray codes along with their decimal and binary equivalents:

 decimal | binary | gray
-------------------------
       0 |      0 |    0
-------------------------
       1 |      1 |    1
-------------------------
       2 |     10 |   11
-------------------------
       3 |     11 |   10
-------------------------
       4 |    100 |  110
-------------------------
       5 |    101 |  111
-------------------------
       6 |    110 |  101
-------------------------
       7 |    111 |  100
-------------------------
       8 |   1000 | 1100
-------------------------
       9 |   1001 | 1101
-------------------------
      10 |   1010 | 1111
-------------------------
      11 |   1011 | 1110
-------------------------
      12 |   1100 | 1010
-------------------------
      13 |   1101 | 1011
-------------------------
      14 |   1110 | 1001
-------------------------
      15 |   1111 | 1000

Cyclic Bit Pattern of a Gray Code

Sometimes called "reflected binary", the property of changing only one bit at a time is easily achieved with cyclic bit patterns for each column starting from the least significant bit:

bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111

...and so on.

Objective

Given a non-padded input string of a gray code, increment the gray code by alternating a single character in the sequence or prepending a 1 (when incrementing to the next power of 2), then output the result as a non-padded gray code.

Caveats

  • Do not worry about taking 0 or an empty string as input.
  • The lowest input will be 1, and there is no upper-bound to the string length other than memory limitations imposed by the environment.
  • By non-padded string, I mean there will be no leading or trailing whitespace (other than an optional trailing newline), and no leading 0s in the input or output.

I/O formats

The following formats are accepted form for input and output, but strings are encouraged over other formats:

  • most significant "bit" first
  • non-padded character array or string of ASCII '1's and '0's
  • non-padded integer array of 1s and 0s
  • non-padded boolean array

What's not allowed:

  • least significant "bit" first
  • decimal, binary or unary integer
  • fixed-length data-structure
  • character array or string of non-printable ASCII indices 1 and 0

Tests

input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000

More tests can be added by request.

Criteria

This is , so shortest program in bytes wins! All ties will be broken by favoring earlier submissions; standard loopholes apply. The best submitted answer will be accepted October 9th, 2016, and updated whenever better answers are given.

\$\endgroup\$
  • 1
    \$\begingroup\$ Related. Related. \$\endgroup\$ – Martin Ender Oct 2 '16 at 21:08
  • \$\begingroup\$ Can we take input as a number? \$\endgroup\$ – xnor Oct 2 '16 at 21:12
  • 1
    \$\begingroup\$ Less obviously, also related. \$\endgroup\$ – Martin Ender Oct 2 '16 at 21:12
  • 1
    \$\begingroup\$ Can I take both input and output reversed, e.g. 0011 for 8 \$\endgroup\$ – Ton Hospel Oct 3 '16 at 6:32
  • 1
    \$\begingroup\$ @TonHospel sorry I didn't see your question about reversed I/O. As I told 1000000000 my answer is no. \$\endgroup\$ – Patrick Roberts Oct 3 '16 at 18:45

14 Answers 14

13
\$\begingroup\$

Jelly, 10 8 bytes

Thanks to Dennis for saving 2 bytes.

^\Ḅ‘^H$B

Input and output are lists of 0s and 1s.

Try it online!

Explanation

The inverse of the Gray code is given by A006068. Using this we don't need to generate a large number of Gray codes to look up the input. One classification of this sequence given on OEIS is this:

a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ...

Where the [] are floor brackets. Consider the example of 44 whose binary representation is 101100. Dividing by 2 and flooring is just a right-shift, chopping off the least-significant bit. So we're trying to XOR the following numbers

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

Notice that the nth column contains the first n bits. Hence, this formula can be computed trivially on the binary input as the cumulative reduction of XOR over the list (which basically applies XOR to each prefix of the list and gives us a list of the results).

This gives us a simple way to invert the Gray code. Afterwards, we just increment the result and convert it back to the Gray code. For the latter step we use the following definition:

a(n) = n XOR floor(n/2)

Thankfully, Jelly seems to floor the inputs automatically when trying to XOR them. Anyway, here is the code:

^\          Cumulative reduce of XOR over the input.
  Ḅ         Convert binary list to integer.
   ‘        Increment.
    ^H$     XOR with half of itself.
       B    Convert integer to binary list.
\$\endgroup\$
  • \$\begingroup\$ You don't need the Ḟ$; bitwise operators cast to int. \$\endgroup\$ – Dennis Oct 3 '16 at 0:25
  • \$\begingroup\$ @Dennis Thanks, I discovered that while writing up. :) \$\endgroup\$ – Martin Ender Oct 3 '16 at 0:25
  • \$\begingroup\$ @MartinEnder Is the integer it converts to internally a big integer? \$\endgroup\$ – Patrick Roberts Oct 3 '16 at 1:54
  • \$\begingroup\$ @PatrickRoberts yes, if necessary - it's Python under the hood. \$\endgroup\$ – Jonathan Allan Oct 3 '16 at 2:20
  • \$\begingroup\$ Nice analysis and explanation. \$\endgroup\$ – Wayne Conrad Oct 4 '16 at 13:55
8
\$\begingroup\$

JavaScript (ES6), 58 bytes

s=>s.replace(s.split`1`.length%2?/.$/:/.?(?=10*$)/,c=>1-c)

Directly toggles the appropriate bit. Explanation: As shown in MartinEnder♦'s answer, each bit in a decoded Gray code is the cumulative XOR, or parity, of itself and the bits to its left. We then need to increment the number which causes a carry ripple that toggles all the rightmost 1 bits to 0 and then the next 0 bit to 1. Re-encoding results in a code with just that one 0 bit position toggled. If the parity of all the 1 bits is even, then the rightmost bit is 0 and we therefore just toggle the last bit. If the parity of all the 1 bits is odd, then the rightmost bits are 1, and we need to find the last 1 bit. This is now the last of the carried bits, so the bit we need to toggle is the next bit from the right.

\$\endgroup\$
  • \$\begingroup\$ Very nice method. Is the first ? in /.?(?=10*$)/ really required? Oh, nevermind. Yes it is. :-) \$\endgroup\$ – Arnauld Oct 3 '16 at 5:57
8
\$\begingroup\$

Perl, 27 25 bytes

Includes +1 for -p

Give input string on STDIN, e.g.

gray.pl <<< 1010

gray.pl:

#!/usr/bin/perl -p
s%(10*\K1(\K0)*)*%1-$&%e

Perl has no cheap infinite-precision integers. So directly toggle the right bit which is the one just before where the last odd-numbered 1 would be.

\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, \G really makes things easy for you! \$\endgroup\$ – Neil Oct 3 '16 at 7:41
  • 1
    \$\begingroup\$ On the other hand, \K makes things even easier for you. \$\endgroup\$ – Neil Oct 3 '16 at 9:06
  • \$\begingroup\$ Haaaaa... Now I want to see the \G implementation as well. \$\endgroup\$ – Magic Octopus Urn Oct 4 '16 at 1:02
  • 2
    \$\begingroup\$ @carusocomputing You can see older versions of a submission by clicking on the edited link \$\endgroup\$ – Ton Hospel Oct 4 '16 at 6:58
6
\$\begingroup\$

Haskell, 118 115 108 bytes

g 0=[""]
g n|a<-g$n-1=map('0':)a++map('1':)(reverse a)
d=dropWhile
f s=d(=='0')$(d(/='0':s)$g$1+length s)!!1

Try it on Ideone.
Naive approach: g generates the set of all gray codes with length n (with 0-padding), f calls g with length(input)+1, removes all elements until 0<inputstring> is found and returns the next element (truncating a possibly leading 0).

\$\endgroup\$
  • 1
    \$\begingroup\$ Good first answer! I hope we can get some more efficient ones soon. \$\endgroup\$ – Patrick Roberts Oct 2 '16 at 23:01
5
\$\begingroup\$

MATL, 18 bytes

ZBtE:t2/kZ~tb=fQ)B

Try it online! Or verify all test cases.

Explanation

Let a(n) denote the sequence of integers corresponding to Gray codes (OEIS A003188). The program uses the characterization a(n) = n XOR floor(n/2), where XOR is bit-wise.

Essentially, the code converts the input to an integer a0, finds that integer in the sequence, and then selects the next term. This requires generating a sufficiently large number of terms of the sequence a(n). It turns out that 2·a0 is sufficiently large. This stems from the fact that the Gray code a(n) never has more binary digits than n.

Let's take input '101' as an example.

ZB      % Input string implicitly. Convert from binary string to integer
        %   STACK: 5
t       % Duplicate
        %   STACK: 5, 5
E       % Multiply by 2. This is the number of terms we'll generate from the sequence
        %   STACK: 5, 10
:       % Range
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10]
t       % Duplicate
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [1 2 3 4 5 6 7 8 9 10]
2/k     % Divide by 2 and round down, element-wise
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [0 1 1 2 2 3 3 4 4 5]
Z~      % Bit-wise XOR, element-wise
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15]
t       % Duplicate
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15]
b       % Bubble up
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15], 5
=       % Equality test, element-wise
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [0 0 0 0 0 1 0 0 0 0]
f       % Find: yield (1-based) index of nonzero values (here there's only one)
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 6
Q       % Increase by 1
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 7
)       % Apply as index
        %   STACK: 4
B       % Convert to binary array
        %   STACK: [1 0 0]
        % Implicitly display
\$\endgroup\$
  • \$\begingroup\$ I notice the output is space-delimited characters... is it printing some sort of array? \$\endgroup\$ – Patrick Roberts Oct 2 '16 at 23:06
  • \$\begingroup\$ @PatrickRoberts Yes, exactly. I assumed it's acceptable, is it? \$\endgroup\$ – Luis Mendo Oct 2 '16 at 23:07
  • \$\begingroup\$ I'll accept it as-is. I've already loosened my requirements on I/O format, so there's no point in making it more strict again. Nice job. \$\endgroup\$ – Patrick Roberts Oct 2 '16 at 23:09
5
\$\begingroup\$

CJam (19 bytes)

{_2b__(^@1b1&*)^2b}

Online demo. This is an anonymous block (function) from bit array to bit array, which the demo executes in a loop.

It works on the simple principle that if the number of set bits is even we should toggle the least significant bit, and otherwise we should toggle the bit to the left of the least significant set bit. Actually identifying that bit turns out to be much easier using bit hacks on an integer than using the list of bits.

Dissection

{         e# Declare a block:
  _2b     e#   Convert the bit array to a binary number
  __(^    e#   x ^ (x-1) gives 1s from the least significant set bit down
  @1b1&   e#   Get the parity of the number of set bits from the original array
  *       e#   Multiply: if we have an even number of set bits, we get 0;
          e#   otherwise we have 2**(lssb + 1) - 1
  )^      e#   Increment and xor by 1 or 2**(lssb + 1)
  2b      e#   Base convert back to a bit array
}

Working solely with the bit array, I think it's necessary to reverse it: working with the left-most 1 is much easier than the right-most. The best I've found so far is (24 bytes):

{W%_1b)1&1$+1#0a*1+.^W%}

Alternative approach (19 bytes)

{[{1$^}*]2b)_2/^2b}

This converts from Gray code to index, increments, and converts back to Gray code.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 53 bytes (non-competing)

A recursive function which builds all gray codes until the input is found, then stops at the next iteration.

The highest possible input depends on the browser recursion limit (about 13 bits in Firefox and 15 bits in Chrome).

f=(s,n=1)=>(b=(n^n/2).toString(2),s)?f(b!=s&&s,n+1):b

console.log(f("1"));      // -> 11
console.log(f("11"));     // -> 10
console.log(f("111"));    // -> 101
console.log(f("1011"));   // -> 1001
console.log(f("1111"));   // -> 1110
console.log(f("10111"));  // -> 10110
console.log(f("101100")); // -> 100100
console.log(f("100000")); // -> 1100000

\$\endgroup\$
  • \$\begingroup\$ I'm afraid this submission doesn't qualify, since the method does not work for unbounded string lengths. Please change to non-competitive if you want to keep this answer on here. \$\endgroup\$ – Patrick Roberts Oct 3 '16 at 12:37
  • \$\begingroup\$ @PatrickRoberts - Sure. That makes sense. \$\endgroup\$ – Arnauld Oct 3 '16 at 12:53
  • \$\begingroup\$ @PatrickRoberts Really? How does a recursion limit not fall under "memory limitations imposed by the environment."? \$\endgroup\$ – Sanchises Oct 9 '16 at 14:53
  • \$\begingroup\$ @sanchises I was referring to heap memory, but more to the point, this program recurses for every possible gray code up to the one being tested, which is extremely inefficient. Technically this could be submitted as "Node.js 6.5" and have --harmony added for penalty bytes in order to have access to tail-call recursion optimization, which appears to be possible here. \$\endgroup\$ – Patrick Roberts Oct 9 '16 at 15:58
  • \$\begingroup\$ @sanchises Looking over my reply, that was a poor argument. The main issue is that the limitation isn't imposed by the environment, it's imposed by the algorithm. There are other answers which recurse for every bit rather than for every incremental value, and I find those to be more acceptable since it works for a much wider range of values. \$\endgroup\$ – Patrick Roberts Oct 9 '16 at 16:47
2
\$\begingroup\$

Retina, 25 bytes

^(10*10*)*
$1:
1:
0
.?:
1

I feel sure there should be a better way of doing this...

\$\endgroup\$
  • \$\begingroup\$ Do you actually need the ^ ? \$\endgroup\$ – Ton Hospel Oct 3 '16 at 9:07
  • \$\begingroup\$ @TonHospel The regex tried to match everywhere without it. (Replace mode defaults to a global replacement.) \$\endgroup\$ – Neil Oct 3 '16 at 9:13
2
\$\begingroup\$

05AB1E, 12 bytes

Uses CP-1252 encoding.

CÐ<^¹SOÉ*>^b

Try it online!

Explanation

Example for input 1011.

C              # convert to int (bigint if necessary)
               # STACK: 11
 Ð             # triplicate
               # STACK: 11, 11, 11
  <            # decrease by 1
               # STACK: 11, 11, 10
   ^           # XOR
               # STACK: 11, 1
    ¹          # push first input
               # STACK: 11, 1, 1011
     S         # split to list
               # STACK: 11, 1, [1,0,1,1]
      O        # sum
               # STACK: 11, 1, 3
       É       # mod 2
               # STACK: 11, 1, 1
        *      # multiply
               # STACK: 11, 1
         >     # increase by 1
               # STACK: 11, 2
          ^    # XOR
               # STACK: 9
           b   # convert to binary
               # STACK: 1001
               # implicitly print top of stack
\$\endgroup\$
2
\$\begingroup\$

Python 2.7, 68 characters

def f(s):i=long(s,2);print bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:]

Python 3, 68 characters

def f(s):i=int(s,2);print(bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:])

This function converts the given binary string to an integer then xor the last bit if the number of set bits in the original string is even, or its swaps the bit to the left of the rightmost set bit if the number of set bits in the original string is odd. Then it converts the result to a binary string and removes the 0b boolean prefix.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 1 byte by removing the space after def f(s): and (assuming Python 2) another by using print instead of return. \$\endgroup\$ – ElPedro Oct 4 '16 at 10:21
  • \$\begingroup\$ @ElPedro Thanks, I also applied a condition trick and factored out the left-hand size of a xor to save a few additional characters :) \$\endgroup\$ – Morwenn Oct 4 '16 at 10:25
  • \$\begingroup\$ Just saw that. Nice answer :-) \$\endgroup\$ – ElPedro Oct 4 '16 at 10:27
  • \$\begingroup\$ Um.. checking python documentation, it looks like int() generates a 32 bit integer, although my requirement is for you to increment any length string. I'm not sure that this qualifies as a valid submission \$\endgroup\$ – Patrick Roberts Oct 4 '16 at 14:45
  • 1
    \$\begingroup\$ @PatrickRoberts I'll check later. long instead of int might solve the problem. \$\endgroup\$ – Morwenn Oct 4 '16 at 14:46
2
\$\begingroup\$

C++, 205 bytes

#include <string>
std::string g(std::string s){int i,z;if(s=="1")return"11";for(i=z=0;i<s.length();i++)if(s[i]=='1')z++;i--;if(z%2){char c=s[i];s.erase(i);s=g(s);s+=c;}else{s[i]=s[i]==49?48:49;}return s;}

Description: Even numbers have even number of ones. Variable z counts ones; if z is even (z mod 2 = z%2 = 0 - else branch), alter the last bit; if z is odd, call this function again without the last character and calculate new value, then append the last character afterwards.

Click here to try it for the test cases.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your submission. If you could provide a short description of your approach and a link to an online compilation of this as a demo, I'd really appreciate that. \$\endgroup\$ – Patrick Roberts Oct 9 '16 at 3:40
  • 1
    \$\begingroup\$ @PatrickRoberts Added the link and the description as you requested. \$\endgroup\$ – AlexRacer Oct 10 '16 at 23:16
2
\$\begingroup\$

Batch, 199 197 bytes

@echo off
set/ps=
set r=
set t=%s:0=%
if 1%t:11=%==1 goto g
:l
set b=%s:~-1%
set s=%s:~,-1%
set r=%b%%r%
if %b%==0 goto l
if 0%s%==0 set s=0
:g
set/ab=1-%s:~-1%
echo %s:~,-1%%b%%r%

Reads input from STDIN into variable s. Removes the 0s and does a parity check on the 1s and if there are an odd number it strips the rightmost 0s in a loop, stopping when it strips a 1. s therefore contains the even parity prefix and r the rest of the string. s is set to zero if it was blank so that its last digit can be toggled, and then everything is concatenated.

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

Actually, 20 19 13 bytes

Based on Martin Ender's Jelly answer with my own version of "cumulative reduce of XOR over the input". Golfing suggestions welcome. Try it online!

σ1♀&2@¿u;½≈^├

Ungolfing

      Implicit input a as a list, such as [1,0,1,1,0,0].
σ     Get the cumulative sums of a.
1♀&   Map x&1 (equivalent to x%2) over every member of the cumulative sum.
2@¿   Convert from binary to decimal.
u     Increment x.
;½≈   Duplicate and integer divide by 2.
^     XOR x and x//2.
├     Convert to binary to obtain our incremented Gray code.
      Implicit return as a string, such as "100100".
\$\endgroup\$
1
\$\begingroup\$

J, 38 bytes

[:#:@(22 b.<.@-:)@>:@#.[:22 b./[:#:#.\

Try it online!

This is essentially Martin's algorithm in J.

Note that 22 b. is XOR.

                                    [: #: #.\   Creates the prefixes of the input
                                                converts to a number, then converts
                                                back to binary.  Needed to get the
                                                padding on the left.

                          [: 22 b./             Reduce the rows of the resulting 
                                                matrix with XOR, giving us the 
                                                normal binary
                      @#.                       Convert to int and...
                   @>:                          Increment and...
      (22 b. <.@-:)                             XOR that with its own floored half
[: #:@                                          And turn the result back to binary
\$\endgroup\$
  • \$\begingroup\$ Nice job, dude! \$\endgroup\$ – Patrick Roberts Jul 9 '18 at 4:28

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.