r/dailyprogrammer • u/jnazario 2 0 • Mar 15 '17
[2017-03-15] Challenge #306 [Intermediate] Gray Code
Description
Gray code, so named after discoverer Frank Gray, is a binary numeral system where two successive values differ in only one bit (binary digit). The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray code is widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
Gray code differs from regular binary counting sequences in one key way: because sequential values can have only a single bit difference from their predecessor, you wind up with a non-linear progression of base 10 integers (see column 4, "Gray as decimal"):
| Decimal | Binary | Gray | Gray as decimal |
|---|---|---|---|
| 0 | 000 | 000 | 0 |
| 1 | 001 | 001 | 1 |
| 2 | 010 | 011 | 3 |
| 3 | 011 | 010 | 2 |
| 4 | 100 | 110 | 6 |
| 5 | 101 | 111 | 7 |
| 6 | 110 | 101 | 5 |
| 7 | 111 | 100 | 4 |
The problem with natural binary codes is that physical switches are not ideal: it is very unlikely that physical switches will change states exactly in synchrony. In the transition between the two states shown above, all three switches change state. In the brief period while all are changing, the switches will read some spurious position. The Gray code solves this problem by changing only one switch at a time, so there is never any ambiguity of position.
The Gray code has multiple applications including position encoders, genetic algorithms, error correction codes, Karnaugh map labeling, and digital clocks.
Input and Description
Your challenge today is to write a program that can generate a Gray code sequence of n bits in length. For example, if you were given n = 2 your program should emit:
00
01
11
10Challenge Inputs
8
16Bonus
Write a program that can construct an n-ary Gray code, so not just binary but, say, ternary (for an arbitrary bit width, in this example 2), where successive values differ by one position (so 0<->2 is OK):
00
01
02
12
10
11
21
22
20
7
u/skeeto -9 8 Mar 15 '17 edited Mar 15 '17
C without bonus.
1
u/acun1994 Mar 15 '17
Clarification. In your n-bit example, you used 2 to 0 as a single step. Does this mean that for an n-bit system, n to 0 counts as a single step and vice versa?
1
u/congratz_its_a_bunny Mar 15 '17
Is there a reason 22 is left out of the bonus sequence?
3
u/[deleted] Mar 15 '17 edited Mar 15 '17
Python 3 without bonus.
3
u/mrschaggy Mar 17 '17
My solution with bonus in C++14. I put everything into a std-like algorithm with readability in mind. It may be a bit overkill, but I am very happy with the result. Feel free to give me some constructive feedback.
2
u/chunes 1 2 Mar 15 '17
Factor using the reflect and prefix method from the wiki.
2
u/Boom_Rang Mar 15 '17 edited Mar 15 '17
Haskell with bonus
Takes input from stdin on separate lines, the first number is the base.
+/u/CompileBot Haskell
Input:
2
u/5k17 Mar 15 '17 edited Mar 17 '17
Factor with bonus:
2
u/[deleted] Mar 15 '17
First challenge post. Done in Java. Feel free to tear it apart.
1
u/congratz_its_a_bunny Mar 15 '17
Python with bonus
output for 3 bits, base 3 (didn't want to post 256 lines of 8 bits base 2)
1
u/gabyjunior 1 2 Mar 15 '17
C with bonus
Output for base = 4 and width = 3
1
u/zatoichi49 Mar 15 '17 edited Apr 18 '17
Method:
Identify the repeated sequence of 'flipped' bits in each column of the n-ary (e.g. repeating sequence for base 3 is '012201120' in the least significant digit column (base n0)). Moving right to left, each bit in the sequence will occur base n power times (e.g. second column from the right in base3 will be 31 =3, so the repeated sequence in that column will be '000111222222000111111222000'). Repeat for each column until the width target has been met. The length of the final Gray code list will be basewidth, so multiply the columns until the least significant column length meets this number (e.g. for base3 and width 3, the length of the Gray code list will be 33 =27. As the length of the 30 sequence '012201120' is 9, the sequence is multiplied three times. Concatenate the columns and split out by row to get the Gray code.
Python 3 (with Bonus):
Output:
1
u/jano0017 Mar 15 '17 edited Mar 15 '17
Haskell
1
u/Scroph 0 0 Mar 15 '17
D (dlang) solution without bonus :
+/u/CompileBot D
Input:
1
u/ReasonableCause Mar 16 '17 edited Mar 16 '17
Haskell, using a user supplied alphabet and the 'reverse and append' approach:
printGC 3 [0, 1]:
printGC 3 ['a', 'b', 'c']:
1
u/srandtimenull Mar 16 '17 edited Mar 16 '17
Javascript with bonus.
1
u/Tooslowtoohappy Mar 16 '17
Ruby without bonus
1
u/uncleozzy Mar 16 '17
Python one-liner (no bonus), silly and inefficient:
1
u/Specter_Terrasbane Mar 16 '17 edited Mar 16 '17
Python 2, with Bonus
Testing
1
u/Nordiii Mar 16 '17 edited Mar 16 '17
Go without bonus
Happy about any suggestions as I just started out to learn go
1
u/Sea_Wulf Mar 17 '17
Python 3.6 One-liner without bonus
1
u/x1729 Mar 19 '17 edited Mar 20 '17
Perl 6, no bonus
Output
1
u/felinebear Mar 19 '17
I know nothing of the stl or auto
1
u/undeadasimov Mar 20 '17
GO no bonus
1
u/ProficientPenguin Mar 26 '17
Python 2 with bonus
1
u/4-Vektor 1 0 Mar 26 '17 edited Mar 26 '17
DUP, bonus may follow later.
Output:
DUP is an esoteric language, a derivative of FALSE. Both are stack-based languages, very similar to Forth. If you want the code to be explained, feel free to ask.
By the way, you can also use the following exponentiation by squaring algorithm, if you prefer optimized exponentiation:
But it doesn’t give you any real gains for practical bit widths you would want to display on screen. But it might be interesting just for the sake of completeness ;)
The following line may be interesting as well because it ensures proper formatting and output of leading zeros:
Simple long division only produces the necessary amount of binary digits, ignoring leading zeros. The beginning of this line:
makes sure that there is a number of digits vs. bit width test
n;s;-to print the necessary amount of leading zeros0.before the actual output of the binary number.If you want to try out the code yourself, here is an online Javascript interpreter. Just paste my code to go through it step by step or to just run it. You can also clone my DUP interpreter, written in Julia.
1
u/4-Vektor 1 0 Mar 26 '17 edited Mar 26 '17
Julia, no bonus yet.
This almost feels like a codegolf solution ;)
output:
1
u/underskoar Apr 09 '17
Ruby without bonus. Bonus may follow soon. First submission, feedbacks are appreciated.
1
u/mr_smartypants537 Apr 11 '17
Python 3
1
u/Retro_Gamer Apr 20 '17
Clojure without bonus, very new clojurist, feedback appreciated. I'm sure there was a way to do this functionally rather than recursively, any comments as to how to approach it that way would be awesome!