**Problem statement**

From Programming Praxis:

The Hamming distance between two numbers is the number of bits that must be changed to make the bit representations of the two numbers equal. Read a list of numbers and find the two with the minimum Hamming distance between them.

**Solution**

This problem took me *all day* because i’m very new to Lisp.

;XOR p q => (p V q) ^ !(p ^ q)
(defun xor (p q)
(and
(or p q)
(not (and p q))
)
)
;Represent a number as a boolean list
(defun getbinary (n)
(map
'list
;"111" becomes (T T T)
(lambda (x)
(if (eq #\1 x) t nil)
)
;7 becomes "111"
(format nil "~b" n)))
;Find hamming distance between two *binary* numbers using XOR
(defun hammingdistance (n1 n2)
(count t
(append
(map
'list
(lambda (x y)
(xor x y)
)
n1
n2)
;map will not work when lists are not of the same length,
;we need to count extra digits in case of length differential.
;taking everything after certain point is fine
(nthcdr (length n1) n2)
(nthcdr (length n2) n1)
)))
;find minimum element in a list
(defun findmin (l &optional m)
(if l
(findmin
(cdr l)
(min
(car l)
;optional parameter is initially nil so
;we replace it first element of list
(if m m (car l))))
;terminating condition
m))
;gets all unique pairings between elements in a list
(defun uniquepairs (l)
(if l
(append
;start from beginning element and pair with every element *head*
;in (1, 2, 3), 1 gets paired with 2 and 3 in first iteration
(loop for x in (cdr l)
collect (list (car l) x))
;generate pairs for remaining elements
(uniquepairs (cdr l)))
;terminating condition
nil))
;find minimum hamming distance between any two elements in input list
;(minhd '(79 83)) => 3
;(minhd '(13500 1935 9645 5790)) => 4
(defun minhd (i)
(findmin
(map
'list
;input is a pair, list of two elements
(lambda (x)
(hammingdistance (getbinary (first x)) (getbinary (second x))))
;generate a list of all possible pairings
(uniquepairs i))))

It can also be viewed here on Github Gist.

### Like this:

Like Loading...