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

Advertisements