 This week's book giveaway is in the Other Languages forum.We're giving away four copies of Rust Web Development and have Bastian Gruber on-line!See this thread for details. Win a copy of Rust Web Development this week in the Other Languages forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Ron McLeod
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Junilu Lacar
• Rob Spoor
• Paul Clapham
Saloon Keepers:
• Tim Holloway
• Tim Moores
• Jesse Silverman
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Piet Souris
• Frits Walraven

Sheriff Posts: 6450
• • Number of slices to send:
Optional 'thank-you' note:
• • <h3>Binary Reflected Gray Code</h3>
<h4>Background</h4>

A Gray code is an ordered set of binary numbers such that only one bit changes
from one element to the next. Any n-bit Gray code will have 2n elements.
{000, 001, 011, 010, 110, 111, 101, 100} and {000, 010, 011, 001, 101, 100,
110, 111} are both examples of 3-bit Gray codes. Note that only one bit changes
between each element and each set has 8 (23) elements.

A binary reflected Gray code (BRGC) is a particular encoding for non-negative
integers. To find a BRGC of n bits, take the BRGC of ( n - 1 ) bits, writing
it forward and then backward. Prefix the first half of the binary numbers with
0, and prefix the second half of the binary numbers with 1. The binary reflected
Gray code of 1 bit (integer values 0 and 1) is:

<pre>
Integer BRGC
======= ====
0 0
1 1
</pre>

To find the BRCG up through 2-bit integers (0, 1, 2, 3), write the BRCG of 1 bit
going forward (0, 1), then backwards (1, 0), to get (0, 1, 1, 0). Prefix the first
half of those numbers with 0 and the second half with 1, giving us:

<pre>
Integer BRGC
======= ====
0 00
1 01
2 11
3 10
</pre>

Looking at the above chart we came up with, we can see that the BRCG encoding for the integer 2 is 11.

Let's try it one more time, finding the BRCG for integers up to 3-bits (0, 1, 2, 3, 4, 5, 6, 7). First we write the 2 bit BRGC forward then backwards (00, 01, 11, 10, 10, 11, 01, 00). Finally we prefix the first half of those numbers with 0, and the second half with 1:

<pre>
Integer BRGC
======= ====
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100
</pre>

Looking that the chart above tells us that the BRGC encoding for the integer
7 is 100.

<h4>The Challenge</h4>

Write a class BRGC containing three static methods. The first method displays
a table of long integers and their BRGC encoded values up to n-bits. It should
have the following signature:

public static void displayBRCG(long n)

Calling the method...

BRGC.displayBRGC(3);

...should produce something similar to the following output:

<pre>
Integer BRGC
======= ====
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100
</pre>

The second method returns the BRGC encoded representation of an input non-negative
long integer. It should have the following signature:

public static String encode(long n)

Calling the method...

System.out.println(BRGC.encode(5));

...should display 111 on the console.

The third method returns the long integer representation of an input BRGC encoding.
It should have the following signature...

public static long decode(String brgc)

Calling the method...

System.out.println(BRGC.decode("111"));

...should display 5 on the console.

Ranch Hand
Posts: 83
• • Number of slices to send:
Optional 'thank-you' note:
• • I believe that method encode() requires a second parameter; namely, the number of bits in the Gray code. Of course, encode(5) will always match the pattern "0*111", but we need to figure out the number of zeroes somehow.

Jason Menard
Sheriff Posts: 6450
• • Number of slices to send:
Optional 'thank-you' note:
• • Originally posted by Roy Tock:
I believe that method encode() requires a second parameter; namely, the number of bits in the Gray code. Of course, encode(5) will always match the pattern "0*111", but we need to figure out the number of zeroes somehow.

No, not really. You aren't required to display leading zeroes. The answer for encode(5) will always be "111" for example, as opposed to "0111", "00111" or the like. But if it helps to think about it like this, keep in mind that the standard binary representation of 5 requires three bits, so the BRGC encoded representatin of 5 also requires three bits.
[ August 03, 2003: Message edited by: Jason Menard ]

(instanceof Sidekick)
Posts: 8791
• • Number of slices to send:
Optional 'thank-you' note:
• • You can write the Gray codes for n bits into a grid so that when you move from one cell to another in NSEW directions only one bit changes - wrap around from one edge to the opposite edge. I wonder if that's at all tricky to automate.

Ranch Hand
Posts: 4632
• • Number of slices to send:
Optional 'thank-you' note:
• • I'll have a lash (knowing zip about binary)

Roy Tock
Ranch Hand
Posts: 83
• • Number of slices to send:
Optional 'thank-you' note:
• • Getting late...here's my early entry. There's no recursion.
encode() relies on a pattern, which I got by staring at the problem statement for a little while. decode() is the inverse of encode().

[ August 03, 2003: Message edited by: Roy Tock ]

Ranch Hand
Posts: 1365
• • Number of slices to send:
Optional 'thank-you' note:
• • Here's a quick solution. I didn't do a real implementation of decode() since it seems to be a bit trickier than encode() and my brain has retired for the night, but I stuck in a decode method that doesn't run in linear time (alas, quadratic).

Ranch Hand
Posts: 168
• • Number of slices to send:
Optional 'thank-you' note:
• • There is a very neat property of Gray Codes
You can translate from Gray Code to Binary by realizing that a '1' in Gray code means that the corresponding digit in binary code is different from the one immediately to the left. A '0' in Gray code means the corresponding binary digit is the same.

Ranch Hand
Posts: 145
• • Number of slices to send:
Optional 'thank-you' note:
• • Hi All,
This code works by using the number of bits to run a recursive method. In using the previous values to create the current values it stores the previous value in 2 places adding the "0" in front of one, and "1" in front of another. The resulting BRGC is stored in an array and printed; solving problem (a). (b) To find the BRGC of a particular number it calculates the number of bits by converting the number to a Binary String (Long.toBinaryString(y) ) and creates the array using the solution to (a). It then looks up the BRGC corresponding to the correct index. (c) To find the number corresponding to the BRGC, we already have the number of bits, create the array and search it (Arrays.binarySearch) to give the right index. Regards,
Fintan
[ August 11, 2003: Message edited by: Fintan Conway ]
[ August 11, 2003: Message edited by: Fintan Conway ]

Jason Menard
Sheriff Posts: 6450
• • Number of slices to send:
Optional 'thank-you' note:
• • Here's my solution... No arrays were explicitly used.
I used an algorithm for my encode that is simple enough I could have done the whole method in one line. Simply take the unencoded decimal value, use integer division to divide it by 2, and XOR that value with the unencoded decimal value. Then just convert the resulting decimal to binary to get your BRGC encoding.
For my display() method, I simply called encode() and padded the result with the appropriate number of zeroes prefixed.
Since there's a simple equation to encode a number into BRGC, I would think there might also be an equation to decode as well. Anyone have any idea on this? Not knowing an easy way to decode, I used the algorithm Michael Zalewski mentioned but implemented it quite differently than he did, prefering mathematical bit manipulation to character manipulation. Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?