452 PurelyFunctional.tv Newsletter

00 Consecutive numbers.md

Consecutive numbers

Write a function that determines whether a sequence of integers can be rearranged into a sequence of consecutive numbers without duplicates. The function should return the sequence of consecutive numbers or nil if it is not possible.

Examples

(consec []) ;=> () ;; trivially true
(consec [1]) ;=> (1) ;; ditto
(consec [3 1 2]) ;=> (1 2 3)
(consec [5 3 2 1]) ;=> nil ;; non-consecutive (4 is missing)
(consec [7 8 9 7]) ;=> nil ;; 7 repeats

Thanks to this site for the problem idea, where it is rated Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn consec [numbers]
  (let [sorted (sort numbers)]
    (if (or (empty? sorted)
            (= sorted (range (first sorted)
                             (inc (last sorted)))))
      sorted)))

I tried to implement a solution that (i) doesn't need sorting and (ii) doesn't need an intermediate data structure for bookkeeping. I came up with this solution that checks the sum of squares to see if the numbers are consecutive. It works for inputs such as [1 3 3 3 5] but I don't know how to mathematically prove that it works for all inputs:

(defn consec [numbers]
  (if (empty? numbers)
    numbers
    (let [lower (apply min numbers)
          upper (apply max numbers)
          sum-squares (transduce (map (comp #(* % %) #(- % lower -1))) + 0 numbers)
          n (inc (- upper lower))
          expected-sum-squares (quot (* n (inc n) (inc (* 2 n))) 6)]
      (if (and (= n (count numbers))
               (= sum-squares expected-sum-squares))
        (range lower (inc upper))))))

(defn consec [si]
  (let [ssi (sort si)]
    (if (every? true? (map-indexed #(= (+ % (first ssi)) %2) ssi))
      ssi
      nil)))

(defn consec [xs]
  (if (seq xs)
    (when (apply distinct? xs)
      (let [a (apply min xs)
            b (inc (apply max xs))]
        (when (= (count xs) (- b a))
          (range a b))))
    xs))

@steffan-westcott Are you sure an implementation that just looks at the min, max and count will do the right thing, for instance for the input [1 3 3 3 5]? I tried something like that myself, before changing to a solution based on sort. But if it can be done, it would be cool :-)

@jonasseglare Good catch😉 I did not account for repeated input numbers as you point out. I've updated my answer to address that. It seems that trying to avoid a sort is tricky!

@steffan-westcott You're welcome, I was also intrigued by this :-) I came up with a solution (see my updated answer) that uses the sum of squared numbers as an extra check but I cannot prove it will always work.

(defn consec
  [xs]
  (let [[y' & ys' :as ys] (sort xs)]
    (when (or (empty? ys)
              (every? true? (map = ys' (map inc ys))))
      ys)))

(defn consec [coll]
  (let [sss (sort coll)]
    (when (reduce (fn ([r x] (if (= (inc r) x) x (reduced false))) ([] true)) sss)
        sss)))

I did sort with comparison to a virtual range, but used the concatenative language Factor. I had to add the empty check so my attempt to build a nil range didn't error out which makes me think I need to understand more the overall nil pruning strategy for this language.

: consec ( seq -- ? )
dup empty? 
[ drop t ]
[ natural-sort
  [ [ first ] [ length ] bi [a..b] >array ]
  [ = ] bi ] 
if ;

(defn consec [coll]
  (let [sorted (sort coll)
        pairs (partition 2 1 sorted)]
    (if (every? (fn [[a b]] (= b (inc a))) pairs)
      sorted)))

(defn consec
  "If its argument can be sorted into a sequence of consecutive integers
  without duplicates, return the sorted list, or nil if it cannot."
  [s]
  (let [sorted (sort s)]
    (when (every? #{-1} (map (partial apply -) (partition 2 1 sorted)))
      sorted)))

(defn consec [xs]
  (let [sorted-xs (sort xs)
        needed-xs (take (count xs)
                        (iterate inc (first sorted-xs)))]
    (when (= sorted-xs needed-xs)
      sorted-xs)))

(defn consec
  "function that determines whether a sequence of integers
  can be rearranged into a sequence of consecutive numbers
  without duplicates."
  [vect]
  (if (< (count vect) 2)
    vect    
    (let [unique-vect (into #{} vect)
          sorted-vect (sort vect)
          step-check (loop [[val1 val2 & rest] sorted-vect]
                       (let [diff (- val2 val1)]
                         (cond 
                           (and (nil? rest) (= diff 1)) true
                           (= diff 1) (recur (cons val2 rest))
                           :else nil)))]
    (if (and
          (= (count vect) (count unique-vect))
          step-check)
      sorted-vect
      nil))))

(defn consec [xs]
  (let [sxs (sort xs)]
    (when-not 
        (->> sxs (partition 2 1)
             (reduce (fn [misfit? [x y]]
                       (if misfit? 
                         (reduced true)
                         (not= 1 (- y x))))
                     false))
      sxs)))