Gray Code

Yesterday it rained all day and night. Today when my wife and I woke up the outside temperature was 58F. Not that cold but it called for long sleeve t-shirts.

Last night rain did wonders for lawns. They are starting to look very green and lush. It seems that on Friday we might get some additional rain which is good for farmers and lawns.

Over the long weekend my wife and I prepared bruschettas. Coming from Italian parents, while growing up, I consumed my fair share of this antipasto.

In the past few years we have prepared them now and then. This past long weekend my wife and I decided to prepare different flavored bruschettas before lunch. They were simple to prepare and we had them with beer, red and white wine and Prosecco. Prosecco is the champagne of Italy as Cava is the champagne of Spain. The change in names was required after the French patented the name champagne only to be used for sparkling wine produced in some parts of France.

You can use any bread, slice it and toast it until it gets a light golden brown color. We prefer to use Ciabatta or Focaccia bread. Yes, my family comes from the Ligurian region in Italy.

We get packages of four Ciabatta rolls at Trader Joe’s. We keep them in the fridge. With a serrated knife we slice them diagonally with a thickness of ½ inch or so. We put them in a convection oven at 450F until they turn light golden brown. My mouth is starting to water thinking about how good these things are.

We also get at Trader Joe’s a variety of jars of tapenades. They are reasonably priced and the flavors are incredible.

Once the bread is done, we pull it out of the oven and moved the pieces to a serving platter. We get a couple jars of tapenade and two spoons that are used to get about a full spoon of tapenade on to a piece of bread. Open your mouth wide and place the bruschetta in it. If you try them, please leave me a comment. I think they taste extremely good!!!

Now let’s get into the main subject of this post. I have been looking at the daily problems in LeetCode. I was under the impression that you had to solve multiples each day. I was mistaken. You should only solve one per day. That is a lot more reasonable.

For this post I tackled LeetCode 89 Gray Code which brought me some memories. You can find more about Gray Code here. Let’s take a look at the problem description.

An n-bit gray code sequence is a sequence of 2^n integers where:

o Every integer is in the inclusive range [0, 2^n - 1],
o The first integer is 0,
o An integer appears no more than once in the sequence,
o The binary representation of every pair of adjacent integers differs by exactly one bit, and
o The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

Constraints:

o 1 <= n <= 16

The description is correct but it matches just the “reflected binary Gray code”. If you are not satisfied with the Wikipedia article, I suggest reading chapter 13, Gray Code in the book Hacker’s Delight Second Edition by Henry S. Warren Jr.

We will solve this problem using the Java programming language and the VSCode IDE on a Windows computer. When you deal with bits and bytes, in general, I prefer to use C or C++, but for now Java is the go to language.

    public List<Integer> grayCode(int n) {
        
    }

The signature for the function of interest is simple. We are given an integer in the specified range and we need to return in a list the complete set of reflected binary Gray codes. The LeetCode web site has two examples when n = 2 and n = 1.

1
main <<< n: 1
main <<< grayCode0: [0, 1]
main <<< grayCode1: [0, 1]
main <<< grayCode2: [0, 1]
main <<< grayCode3: [0, 1]
main <<<  grayCode: [0, 1]


2
main <<< n: 2
main <<< grayCode0: [0, 1, 3, 2]
main <<< grayCode1: [0, 1, 3, 2]
main <<< grayCode2: [0, 1, 3, 2]
main <<< grayCode3: [0, 1, 3, 2]
main <<<  grayCode: [0, 1, 3, 2]


3
main <<< n: 3
main <<< grayCode0: [0, 1, 3, 2, 6, 7, 5, 4]
main <<< grayCode1: [0, 1, 3, 2, 6, 7, 5, 4]
main <<< grayCode2: [0, 1, 3, 2, 6, 7, 5, 4]
main <<< grayCode3: [0, 1, 3, 2, 6, 7, 5, 4]
main <<<  grayCode: [0, 1, 3, 2, 6, 7, 5, 4]


4
main <<< n: 4
main <<< grayCode0: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
main <<< grayCode1: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
main <<< grayCode2: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
main <<< grayCode3: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
main <<<  grayCode: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]

The first is the input line. It contains the value for `n`. Our test code, which IS NOT PART OF THE SOLUTION, reads the input line and displays the value for `n`.  At that point it seems to call five implementations which seem to return the same values.

Please take a few moments verifying that the values match the requirements.

    /**
     * Test code.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read `n` ****
        int n = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();

        // **** enforce constraints ****
        if (n < 1) n = 1;
        if (n > 16) n = 16;

        // ???? ????
        System.out.println("main <<< n: " + n);

        // **** call function of interest and display results ****
        System.out.println("main <<< grayCode0: " + grayCode0(n));

        // **** call function of interest and display results ****
        System.out.println("main <<< grayCode1: " + grayCode1(n));

        // **** call function of interest and display results ****
        System.out.println("main <<< grayCode2: " + grayCode2(n));

        // **** call function of interest and display results ****
        System.out.println("main <<< grayCode3: " + grayCode3(n));

        // **** call function of interest and display results ****
        System.out.println("main <<<  grayCode: " + grayCode(n));
    }

Our test code reads the value for `n`, makes sure that it is within range, and displays it.

The code then calls five different implementations which we will look in detail shortly.

    /**
     * Steps:
     * 
     * o Let the list of (n-1)-bit Gray codes be L1. Create another list L2 which is reverse of L1.
     * o Modify the list L1 by prefixing a ‘0’ in all codes of L1.
     * o Modify the list L2 by prefixing a ‘1’ in all codes of L2.
     * o Concatenate L1 and L2. The concatenated list is required list of n-bit Gray codes.
     * 
     * Runtime: 271 ms, faster than 5.04% of Java online submissions.
     * Memory Usage: 47.9 MB, less than 23.57% of Java online submissions.
     */
    static List<Integer> grayCode0(int n) {

        // **** sanity check(s) ****
        if (n == 1) return Arrays.asList(new Integer[] {0, 1});

        // **** initialization ****
        List<String> gcl    = new ArrayList<String>();
        List<Integer> gcli  = new ArrayList<Integer>();

        List<String> l1     = new ArrayList<String>();
        List<String> l2     = new ArrayList<String>();

        // **** loop once per set ****
        for (int i = 1; i < n; i++) {

            // **** populate l1 ****
            if (l1.size() == 0) {
                l1.add("0"); l1.add("1");
            } else
                l1 = new ArrayList<String>(gcl);

            // **** populate l2 (reverse of l1) ****
            l2 = new ArrayList<String>(l1);
            Collections.reverse(l2);

            // **** modify l1 (prefixing `0`) ****
            for (int j = 0; j < l1.size(); j++) {

                // **** ****
                String str = l1.get(j);

                // **** replace this entry in l1 ****
                l1.remove(j);
                l1.add(j, "0" + str);
            }

            // **** modify l2 (prefixing `1`) ****
            for (int j = 0; j < l2.size(); j++) {

                // **** ****
                String str = l2.get(j);

                // **** replace this entry ****
                l2.remove(j);
                l2.add(j, "1" + str);
            }

            // **** concatenate l2 to l1 ****
            gcl = new ArrayList<String>(l1);
            gcl.addAll(l2);
        }
        
        // **** convert String to Integer ****
        for (int i = 0; i < gcl.size(); i++)
            gcli.add(i, Integer.parseInt(gcl.get(i), 2));

        // **** return Integer list ****
        return gcli;
    }

The steps to generate the reflected binary Gray code are listed. You can get a true flavor for the use of the “reflected” word in their description.

We start with a sanity check.

We then initialize a set of array lists. They will be used to generate a list in binary and then convert it to integer before returning the results.

We enter the main loop. We will loop once per set.

We populate `l1`. If empty, we populate it with the seed values “0’ and “1”. If `l1` is not empty we use the gray codes from the previous pass.

We now populate `l2` with the reversed contents of `l1`. This operation doubles the number of entries per set.

We then set in the first list a prefix of “0” for each entry and in the second list we use a prefix of “1”. Take a look at the example for `n` = 2 and you should be able to follow these two steps.

We now concatenate the lists and add it to the `gcl` list.

The main loop repeats based on the value of `n`.

When we exit the main loop, we need to convert the Strings to binary values. Once the `gcli` list has been populated, we return from the function.

Slow but illustrates the individual steps.

    /**
     * Same as previous pass but optimiing the steps inside the main loop.
     * 
     * Runtime: 32 ms, faster than 11.86% of Java online submissions.
     * Memory Usage: 47 MB, less than 27.58% of Java online submissions.
     * 
     * Time: O(2 * n) - Space: O(2 * n)
     */
    static List<Integer> grayCode1(int n) {

        // ***** sanity check(s) ****
        if (n == 1) return Arrays.asList(new Integer[] {0, 1});

        // **** initialization ****
        List<String> gcl    = new ArrayList<String>();
        List<Integer> gcli  = new ArrayList<Integer>();

        // **** prime gcl ****
        gcl.add("0"); gcl.add("1");

        // **** copy gcl and append "0" to first and "1" to second half ****
        int i, j;
        for (i = 1; i < n; i++) {

            // **** append first part of gcl in reverse order ****
            for (j = gcl.size() - 1; j >= 0; j--) 
                gcl.add(gcl.get(j));

            // **** append "0" to first half of gcl ****
            for (j = 0; j < gcl.size() / 2; j++)
                gcl.set(j, "0" + gcl.get(j));

            // **** append "1" to second half of gcl ****
            for ( ; j < gcl.size(); j++)
                gcl.set(j, "1" + gcl.get(j));
        }

        // **** convert String to Integer ****
        for (i = 0; i < gcl.size(); i++)
            gcli.add(i, Integer.parseInt(gcl.get(i), 2));

        // **** return Integer list ****
        return gcli;
    }

In this pass we will try to optimize the steps we performed in the previous implementation.

We start with performing a sanity check. If `n` == 1 we know that we need to return [0, 1].

We will only use two instead of four array lists. We will work with the binary strings on a single array list. We have to convert the Strings to Integers using as a target the second array list.

We start by priming the list with the values of “0” and “1”.

In the main loop we append to the list all the existing values in reverse order. To the first appended half we prefix each entry with a “0” and for the second half we prefix the entries with a “1”.

The loop repeats until we have all the entries we require.

At that time, we repeat the process we did in the previous implementation which is to generate a list with integer values. The list is then returned to the caller.

Note that we did the same operations as in the previous pass but we did them in a more efficient way. This is illustrated by the execution times listed in the comments sections in both implementations.

    /**
     * Entry point for recursive function.
     * 
     * Runtime: 33 ms, faster than 11.39% of Java online submissions.
     * Memory Usage: 46.8 MB, less than 28.25% of Java online submissions.
     * 
     * Time: O(2 * n) - Space: O(2 * n)
     */
    static List<Integer> grayCode2(int n) {

        // ***** sanity check(s) ****
        if (n == 1) return Arrays.asList(new Integer[] {0, 1});

        // **** initialization ****
        List<Integer> gcli = new ArrayList<Integer>();

        // **** start recursion ****
        ArrayList<String> gcl = grayCodeRec(n);

        // **** convert String to Integer ****
        for (int i = 0; i < gcl.size(); i++)
            gcli.add(i, Integer.parseInt(gcl.get(i), 2));

        // **** return Integer list ****
        return gcli;
    }

We are now attempting a recursive approach. We start by performing a sanity check as before.

We initialize a list in which the String values will be collected.

A recursive call is invoked passing as argument the `n`. The function returns the list of Strings which we will convert to a list of integers as we did in the previous implementations.

    /**
     * Recursive function.
     */
    static ArrayList<String> grayCodeRec(int n) {

        // **** base case(s) ****
        if (n == 0) return new ArrayList<>(){ { add("0"); } };
        if (n == 1) return new ArrayList<>(){ { add("0"); add("1"); } };

        // **** initialization ****
        int j;

        // **** recursive call ****
        ArrayList<String> gcl = grayCodeRec(n - 1);

        // **** append first part of gcl in reverse order ****
        for (j = gcl.size() - 1; j >= 0; j--) 
            gcl.add(gcl.get(j));

        // **** append "0" to first half of gcl ****
        for (j = 0; j < gcl.size() / 2; j++)
            gcl.set(j, "0" + gcl.get(j));

        // **** append "1" to second half of gcl ****
        for ( ; j < gcl.size(); j++)
            gcl.set(j, "1" + gcl.get(j));

        // **** return gcl ****
        return gcl;
    }

This is the recursive call. We start by stating our base cases. The first addresses the case where n == 0 and the second when n == 1.

We then declare the variable that we will use to index the following three loops.

We make a recursive call to fill in the list with n – 1. Note that when all the recursive calls are made we will start with a list containing [“0”, “1”] which is where we started in all the previous implementations.

From then on we need to append, and prefix the lists.

The first loop appends the values in reverse order.

The second loop prefixes a “0” to the first half of the reversed list.

The third loop prefixes a “1” to the second half of the reversed list.

The updated list which has doubled its size is returned.

The process repeats until we get the results for the specified ‘n’.

Back into the entry call, we convert the String values in the returned list by the recursive call to a list of integers. The list of integers is returned to the caller.

Not much has been gained by using recursion as illustrated in the comments section of the entry function.

    /**
     * Page 315 of Hacker's Delight Second Edition by Henry S.Warren, Jr.
     * 
     * Runtime: 7 ms, faster than 33.02% of Java online submissions.
     * Memory Usage: 46.3 MB, less than 60.16% of Java online submissions.
     */
    static ArrayList<Integer> grayCode3(int n) {

        // **** initialization ****
        ArrayList<Integer> gcli = new ArrayList<>(){ { add(0); add(1); } };

        // **** sanity checks ****
        if (n == 1) return gcli;

        // **** loop generating the Gray codes O(2 ^ n - 1) ****
        for (int i = 2; i < (1 << n); i++) {

            // **** get previous gray code ****
            int gc = gcli.get(i - 1);

            // **** ****
            int l = Integer.lowestOneBit(gc);
            
            // **** parity ****
            int p = Integer.bitCount(gc);

            // **** proceed based on the parity bit of the ****
            if (p % 2 == 0) {       // even parity
                gc ^= 1;            // invert rightmost bit
            } else {                // odd parity
                int mask = l;
                mask <<= 1;         // shift left once
                gc ^= mask;
            }

            // **** add gray code to list ****
            gcli.add(gc);
        }

        // **** return gray code list ****
        return gcli;
    }

The approach in this function comes from the Hacker’s Delight book shown in the comments section.

We are now dealing with Integers instead of binary string representations. We start by initializing the list.

We then perform a sanity check and return our initialized list if needed.

We then enter a loop generating Gray codes.

First we recall the previous Gray code. In that Gray code we get the location of the lowest `1` bit followed by the parity of the Gray code.

If the parity of the Gray code is even, we invert the value of the rightmost bit; otherwise if the parity is odd we invert the value next to the lowest ‘1’ bit in the Gray code.

We then add the newly created Gray code to the list.

When done, we return the list of binary Gray codes.

Using this algorithm, we can generate the Gray codes faster than in all the previous implementations.

    /**
     * Page 314 of Hacker's Delight Second Edition by Henry S.Warren, Jr.
     * 
     * Runtime: 3 ms, faster than 96.35% of Java online submissions.
     * Memory Usage: 46.3 MB, less than 60.16% of Java online submissions.
     */
    static ArrayList<Integer> grayCode(int n) {

        // **** initialization ****
        ArrayList<Integer> gcli = new ArrayList<Integer>();

        // **** loop generating gray code values using formula ****
        for (int i = 0; i < (1 << n); i++)
            gcli.add(i ^ (i >> 1));

        // **** return gray code list ****
        return gcli;
    }

On this last implementation, we will use a different approach that is also found in the Hacker’s Delight book shown in the comments section of the function.

We initialize an array list.

We then enter a loop that generates all the Gray codes associated with the specified value of `n`.

The values are inserted into the list. When done the list is returned.

Note that this is the fastest implementation that we will attempt in this post. If you check in LeetCode, there are a couple faster implementations. They both seem to be quite complex.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.