Being an occasional insomniac, I sometimes find myself wide awake at night. Instead of counting sheep, I sometimes do simple coding problems. Tonight, I solved Problem 171 on 4Clojure using Common Lisp listening to Pink Floyd’s The Wall album.
Write a function that takes a sequence of integers and returns a sequence of “intervals”. Each interval is a a vector of two integers, start and end, such that all integers between start and end (inclusive) are contained in the input sequence.
Here is my solution in Common Lisp:
(defun intervals (xs &optional a b carry)
(cond ((null xs) (nreverse (and a (cons (list a b) carry))))
((null a) (intervals (sort xs #'<) t nil nil))
((null b) (intervals (cdr xs) (car xs) (car xs) nil))
((>= (1+ b) (car xs)) (intervals (cdr xs) a (car xs) carry))
(t (intervals (cdr xs) (car xs) (car xs) (cons (list a b) carry)))))
INTERVALSand here are the tests:
(every (lambda (test) (equal (intervals (car test)) (cdr test)))
'(((1 2 3) . ((1 3)))
((10 9 8 1 2 3) . ((1 3) (8 10)))
((1 1 1 1 1 1 1) . ((1 1)))
(nil . nil)
((19 4 17 1 3 10 2 13 13 2 16 4 2 15 13 9 6 14 2 11) . ((1 4) (6 6) (9 11) (13 17) (19 19)))))
TOk. Let me try to sleep again.