Minimum Hamming Distance in Common Lisp

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.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s