99 Clojure Problems – 49: Gray Code

"An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example:

n = 1: C(1) = ("0", "1").
n = 2: C(2) = ("00", "01", "11", "10").
n = 3: C(3) = ("000", "001", "011", "010", "110", "111", "101", "100").

Find out the construction rules and write a function to generate Gray codes. See if you can use memoization to make the function more efficient."

Example/Test

deftest gray-2
  (is (= ["00" "01" "11" "10"] (gray 2))))

(deftest gray-3
  (is (= ["000" "001" "011" "010" "110" "111" "101" "100"] (gray 3))))

Discussion

I did not work out the construction rules myself but simply looked at Wikipedia. I recommend to read the relevant article yourself before continuing. Based on my reading I came up with two solutions.

The first solution follows the name giving generative principle of forming new lists of gray codes by reflecting existing sublists. Or more precisely from Wikipedia:

"The binary-reflected Gray code list for n bits can be generated recursively from the list for n−1 bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with a binary 0, and then prefixing the entries in the reflected list with a binary 1"

This lead to an immediate translation into code based on strings as can be seen on Github.

Adding memoization as requested by the exercise is very easy in Clojure as there is a dedicated memoize function that returns a memoized version for a referentially transparent function.

Leaving aside the inefficiencies of this solution there is a more immediate problem with this implementation because it is not "stack safe". That means for every recursive step a new stack frame will be created and the code will only unwind the stack when it has reached the exit condition leading to a stack overflow for deep recursive calls. Using the gray code example, depending on your VM configuration and whether or not you are using memoization, you start running into trouble around 20 bits or so.

The second solution is based on the gray code conversion algorithm whereby you convert binary to gray code by xor'ing the binary number with itself right shifted by one. The only complication is that you have to calculate the range of possible numbers first. This is 2^n where n is the number of bits you want to support in your gray code encoding.

You calculate an exponent in Clojure by literally multiplying the number as many times as the exponent states:

(reduce * (repeat n 2))

or use a library like numeric-tower that features an exponent function. To create the identical output as the string based version I used the common lisp formatting build into clojure.pprint:

(cl-format nil (str "~" n "'0b") %)

This allows me to print the binary/gray code elegantly left padded with zeros. Alternatively you could use Java interop with String.format and Long.toBinaryString.

There is probably more to be said about gray code and there are more efficient solutions. The two main takeaways here on the language level are how easy it is in Clojure to create a memoized function and the possibility to use Common Lisp formatting instead of Java's if it seems more appropriate.

Read more about this series.