Skip to content

Instantly share code, notes, and snippets.

# ericnormand/00 Consecutive numbers.md

Created November 29, 2021 14:53
Show Gist options
• Save ericnormand/6cc9a64238b4929510bb3d3025d60151 to your computer and use it in GitHub Desktop.
452 PurelyFunctional.tv Newsletter

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/

### jonasseglare commented Nov 29, 2021 • edited Loading

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

### mchampine commented Nov 29, 2021 • edited Loading

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

### steffan-westcott commented Nov 29, 2021 • edited Loading

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

### jonasseglare commented Nov 29, 2021

@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 :-)

### steffan-westcott commented Nov 29, 2021 • edited Loading

@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!

### jonasseglare commented Nov 29, 2021

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

### francesco-bracchi commented Nov 29, 2021

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

### miner commented Nov 29, 2021

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

### apalmer27516 commented Nov 29, 2021 • edited Loading

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 ;

### harto commented Nov 29, 2021

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

### brunchboy commented Nov 29, 2021

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

### alex-gerdom commented Nov 30, 2021 • edited Loading

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

### dhoboy commented Dec 1, 2021

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

### KingCode commented Dec 4, 2021

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

to join this conversation on GitHub. Already have an account? Sign in to comment