• Post Reply Bookmark Topic Watch Topic
  • New Topic
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:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

August Newsletter Puzzle

 
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
<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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'll have a lash (knowing zip about binary)
 
Roy Tock
Ranch Hand
Posts: 83
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 150
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic