A Solution for Problem 171 of 4Clojure

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.

Description of the problem

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.

A Solution

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)))))
INTERVALS

and 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)))))
T

Ok. Let me try to sleep again.