August Newsletter Puzzle

<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 2<sup>n</sup> 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 (2<sup>3</sup>) 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.

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.

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 ]

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.

I'll have a lash (knowing zip about binary)

import java.util.*;
class BRGCpuzzle
{
  private static ArrayList brgcList = new ArrayList();
  public static void main(String args[])
  {
    try
    {
      long startNum = Long.parseLong(args[0]);
      long numToEncode = Long.parseLong(args[1]);
      String numToDecode = args[2];
      if(startNum > 0)
      {
        BRGCpuzzle BRGC = new BRGCpuzzle();
        displayBRGC(startNum);
        if(numToEncode >= 0 && numToEncode < brgcList.size())
        {
          System.out.println("encode = " + BRGC.encode(numToEncode));
        }
        else System.out.println("eror - encode data invalid");
        long decoded = BRGC.decode(numToDecode);
        if(decoded >= 0) System.out.println("decode index = " + decoded);
        else System.out.println("error - decode data invalid");
      }
    }
    catch(Exception e)
    {
      System.out.println("error - invalid data entered");
    }
    System.exit(0);
  }
  public static void displayBRGC(long n)
  {
    String list[] = new String[(int)Math.pow(2,(double)n)];
    list[0] = "0";
    list[1] = "1";
    int from = 0;
    int to = 1;
    String temp = "";
    for(int i = 1; i < n; i++)
    {
      from = to+1;
      to = (to+1)*2 -1;
      for(int ii = 0; ii < from; ii++)
      {
        temp = list[ii];
        list[ii] = "0"+temp;
        list[to - ii] = "1"+temp;
      }
    }
    for(int i = 0; i < list.length; i++)
    {
      brgcList.add(list[i]);
    }
    for(int i = 0; i < brgcList.size(); i++)
    {
      System.out.println((String)brgcList.get(i));
    }
  }
  public static String encode(long n)
  {
     return (String)brgcList.get((int) n);
  }
  public static long decode(String brgc)
  {
    return brgcList.indexOf(brgc);
  }
}

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().

/**
 * @author Roy Tock
 */
public class BRGC {
    public static void main(String[] args) {
        System.out.println("encode(0)=" + encode(0));
        System.out.println("encode(5)=" + encode(5));
        System.out.println("encode(233)=" + encode(233));
        System.out.println("decode(000)=" + decode("000"));
        System.out.println("decode(111)=" + decode("111"));
        System.out.println("decode(0111)=" + decode("0111"));
        System.out.println("decode(10011101)=" + decode("10011101"));
        System.out.println();
        System.out.println("displayBRCG(8) returns:");
        displayBRCG(8);
    }
    // There's a pattern to BRCG encoding.  Study it to yield this.
    public static String encode(long n) {
        if (n == 0)
            return "0";
        // Find out how many bits we need.
        int numBits = numBitsToDisplay(n);
        int displayPlace;
        int displayPlaceIterator;
        int binaryDigit;
        int displayDigit;
        int[] digits = new int[numBits];
        StringBuffer returnBuffer = new StringBuffer();
        for (displayPlace = numBits - 1; displayPlace >= 0; displayPlace--) {
            binaryDigit = (int) ((n / twoToPow(displayPlace)) % 2);
            displayDigit = binaryDigit;
            for (displayPlaceIterator = numBits - 1;
                displayPlaceIterator > displayPlace;
                displayPlaceIterator--) {
                displayDigit ^= digits[displayPlaceIterator];
            }
            digits[displayPlace] = displayDigit;
            returnBuffer.append(displayDigit);
        }
        return returnBuffer.toString();
    }
    public static void displayBRCG(int n) {
        long maxNum = twoToPow(n);
        for (long num = 0; num < maxNum; num++) {
            System.out.println("encode(" + num + ")=" + encode(num));
        }
    }
    // The inverse of the encode algorithm.  Again, studying the pattern will
    // yield this.
    public static long decode(String brgc) {
        int[] binaryBitArray = toBitArray(brgc);
        int currentBit;
        long value = 0;
        for (int i = binaryBitArray.length - 1; i >= 0; i--) {
            currentBit = binaryBitArray[i];
            for (int iter = binaryBitArray.length - 1; iter > i; iter--) {
                currentBit ^= binaryBitArray[iter];
            }
            if (currentBit == 1) {
                value += twoToPow(i);
            }
        }
        return value;
    }
    private static int numBitsToDisplay(long n) {
        int i = 0;
        while ((n >> i) > 0) {
            i++;
        }
        return i;
    }
    private static long twoToPow(int i) {
        return 1 << i;
    }
    private static int[] toBitArray(String s) {
        // trim leading zeroes
        int firstOne = s.indexOf('1');
        if (firstOne < 0) {
            return new int[0];
        }
        s = s.substring(firstOne);
        int[] bitArray = new int[s.length()];
        for (int i = 0; i < bitArray.length; i++) {
            if (s.charAt(s.length() - i - 1) == '0') {
                bitArray[i] = 0;
            } else {
                bitArray[i] = 1;
            }
        }
        return bitArray;
    }
}

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

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).

public class BRGC
{
    public static String encode(long n)
    {
        if (n < 0)
        {
            throw new IllegalArgumentException();
        }
        if (n == 0)
        {
            return "0";
        }
        long max = 1;
        while (max <= n)
        {
            max <<= 1;
        }
        return encode(n, max);
    }
    public static String encode(long n, long max)
    {
        if (max <= 1)
        {
            return "";
        }
        long mid = (max >> 1);
        long remainder = n % mid;
        if (n >= mid)
        {
            return "1" + encode(mid - remainder - 1, mid);
        }
        else
        {
            return "0" + encode(remainder, mid);
        }
    }
    public static void displayBRCG(long numBits)
    {
        for (int i = 0; i < (1 << numBits); i++)
        {
            String encoded = pad(numBits, encode(i));
            long decoded = decode(encoded);
            System.out.println(i + ": " + encoded + " - " + decoded);
        }
    }
    private static long decode(String encoded)
    {
        // remove 0's in front
        while (encoded.startsWith("0"))
        {
            encoded = encoded.substring(1);
        }
        if (encoded.length() == 0)
        {
            return 0;
        }
        long max = 1 << encoded.length();
        long min = 1 << (encoded.length() - 1);
        for (long i = min; i < max; i++)
        {
            if (encode(i).equals(encoded))
            {
                return i;
            }
        }
        return -1;
    }
    private static String pad(long desiredLength, String string)
    {
        StringBuffer pad = new StringBuffer();
        while ((pad.length() + string.length()) < desiredLength)
        {
            pad.append('0');
        }
        return pad + string;
    }
}

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.

public class BRGC {
  public static String encode( long nEncode) {
    String sEncodeBinary = Long.toString( nEncode, 2);
    StringBuffer sbEncodeGray = new StringBuffer( 33);
    char chBinaryDigitLast = '0';
    for( int iChar = 0; iChar < sEncodeBinary.length(); iChar++) {
      char chBinaryDigit = sEncodeBinary.charAt( iChar);
      sbEncodeGray.append(
        ( chBinaryDigit == chBinaryDigitLast) ? '0' : '1'
      );
      chBinaryDigitLast = chBinaryDigit;
    }
    return sbEncodeGray.toString();
  }
  public static long decode( String sDecode) {
    StringBuffer sbDecodeBinary = new StringBuffer( sDecode.length());
    char chGrayDigitLast = '0';
    for( int iChar = 0; iChar < sDecode.length(); iChar++) {
      char chGrayDigit = sDecode.charAt( iChar);
      sbDecodeBinary.append(
        (chGrayDigit == chGrayDigitLast) ? '0' : '1'
      );
      chGrayDigitLast = chGrayDigit;
    }
    return Long.parseLong( sbDecodeBinary.toString(), 2);
  }
  public static void displayBRGC( long nLimit) {
    System.out.println( "Integer\tBRGC");
    System.out.println( "=======\t====");
    for( long i = 0; i <= nLimit; i++) {
      System.out.println( Long.toString( i) + '\t' + BRGC.encode( i));
    }
  }
}

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.

import java.util.Arrays;
public class BRGC {
public static void displayBRGC(long n) {
if (n < 1) {
System.out.println("The value must be 1 or greater");
return;
}
long size = (long)Math.pow(n,2);
String[] arrBRGC = new String[(int)size];
arrBRGC = calcBRGC(n -1);
System.out.println("Integer\tBRGC");
System.out.println("=======\t====");
for (int i = 0; i < arrBRGC.length; i++) {
System.out.println(i + "\t" + arrBRGC[i]);
}
}//displayBRGC
public static String encode(long n) {
//Find max bits for number n
int bits = 0;
bits = getBits(n);

//Get array of BRGC for this number of bits
long size = (long)Math.pow(bits,2);
String[] encBRGC = new String[(int)size];
encBRGC = calcBRGC(bits -1);
// Find number n in this array
return encBRGC[(int)n];
}// encode
public static long decode(String brgc) {
//Find max bits for number n
int bits = 0;
bits = brgc.length();

//Get array of BRGC for this number of bits
long size = (long)Math.pow(bits,2);
String[] decBRGC = new String[(int)size];
decBRGC = calcBRGC(bits -1);
// Find number index of bgrc in this array
long found = 0;
found = Arrays.binarySearch(decBRGC, brgc);
return found;
}// decode
private static String[] calcBRGC(long x) {
if (x==0) {
String[] BRGC0 = {"0", "1"};
return BRGC0;
} else {
long prevSize = (long)Math.pow((x-1), 2);
String[] prevBRGC = new String[(int)prevSize];

prevBRGC = calcBRGC(x - 1);
String[] thisBRGC = new String[prevBRGC.length*2];
for(int i = 0; i < prevBRGC.length; i++) {
int swap = thisBRGC.length -1 - i;
thisBRGC[i] = "0" + prevBRGC[i];
thisBRGC[swap] = "1" + prevBRGC[i];
}
/*printArray(prevBRGC);
printArray(thisBRGC);
System.out.println("---------------");*/
return thisBRGC;
}
}// calcBRGC
private static int getBits(long y) {
String numString = Long.toBinaryString(y);
return numString.length();
}// getBits
private static void printArray(String[] prt) {
for (int i = 0; i < prt.length; i++) {
System.out.println(prt[i]);
}
System.out.println();
}// printArray

}// BRGC

Regards,
Fintan
[ August 11, 2003: Message edited by: Fintan Conway ]
[ August 11, 2003: Message edited by: Fintan Conway ]

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.

public class BRGC {
    public static void display(long n) {
        System.out.println("Integer\t\tBRGC");
        System.out.println("=======\t\t====");
        long max = 1 << n;
        if (max < 2)
            max = 0;
        for (long i = 0; i < max; i++) {
            System.out.println(i + "\t\t" + pad(encode(i), n));
        }
    }
    public static long decode(String brgc) {
        long len = brgc.length();
        long encVal = Long.parseLong(brgc, 2);
        long msb = getMSB(encVal);
        long res = 0;
        for (long i = msb; i >= 0; i--) {
            int thisEncBit = getMaskedBit(encVal, i);
            int leftResBit = getMaskedBit(res, i + 1);
            int thisResBit = leftResBit;
            if (thisEncBit == 1) {
                thisResBit = leftResBit ^ 1;
            }
            if (thisResBit == 1) {
                res += 1 << i;
            }
        }
        return res;
    }
    public static String encode(long n) {
        long rhs = n / 2;
        long val = n ^ rhs;
        return Long.toBinaryString(val);
    }
    private static String pad(String s, long n) {
        if (s == null)
            return null;
        int len = s.length();
        if (len == n)
            return s;
        if (len < n) {
            StringBuffer sb = new StringBuffer(s);
            long dif = n - len;
            for (long i = 0; i < dif; i++) {
                sb.insert(0, '0');
            }
            return sb.toString();
        }
        return null;
    }
    private static int getMaskedBit(long val, long maskBit) {
        long mask = 1 << maskBit;
        return ((val & mask) > 0 ? 1 : 0);
    }
    private static long getMSB(long val) {
        long msb = 0;
        while ((1 << msb) <= val)
            msb++;
        if (msb > 0)
            msb--;
        return msb;
    }
    public static void main(String[] args) {
        for (int i = 0; i < 8; i++) {
            System.out.println(i + ": " + encode(i));
        }
        System.out.println();
        display(3);
        System.out.println();
        System.out.println(decode("100"));
    }
}