August 19, 2024
P49 - 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 with the following specification:
(gray N) returns the N-bit Gray code
Can you apply the method of "result caching" in order to make the function more efficient, when it is to be used repeatedly?
lisp
;;; Gray code
;;; Make it with lists first, then make string from list
;;; Way of making it: for n = 0 it is the empty list
;;; For larger n, add 0 to code for n-1, and add 1 to reverse
(defun gray (n)
(mapcar #'list-to-string (gray-list n))
)
(defun list-to-string (lista)
(let ((a (make-string (length lista) :initial-element #\0)))
(dotimes (i (length lista) a)
(setf (aref a i) (elt lista i))
)
)
)
(defun gray-list (n)
(if (= n 0)
'(())
(let ((prev (gray-list (1- n))))
(append (add #\0 prev)
(add #\1 (reverse prev))
)
)
)
)
;;; Adding a digit to a previous code word
(defun add (digit word)
(mapcar #'(lambda (x) (cons digit x)) word)
)
Be first to comment