find-sum

find-sum.clj

(ns sample.sample-core
  (:require [clojure.repl :refer :all]
            [clojure.test :refer :all]))

; List comprehension
; Works for negative numbers
(defn find-sum-1
  "Find the first continuous sub-sequence of elements having the sum.
  Return the start-index and length of the sub-sequence.
  Return [-1 -1] if no such sub-sequence exists."
  [col sum]
  (let [matches-seq (for [start-index (range 0 (count col))
                          length (range 1 (-> (count col)
                                              (- start-index)
                                              (inc)))]
                      (when (= sum (apply + (->> col
                                                 (drop start-index)
                                                 (take length))))
                        [start-index length]))]
    (or (->> matches-seq
             (filter identity)
             (first))
        [-1 -1])))

; Loop & recur
; Does NOT work for negative numbers
(defn find-sum-2
  "...same as above..."
  [col sum]
  ;(println "====" sum)
  (let [v (vec col)
        total-length (count v)]
    (loop [start-index 0
           length 1]
      (let [sub-vec (subvec v start-index (+ start-index length))
            sub-sum (apply + sub-vec)
            can-expand (< (+ start-index length) total-length)
            can-shrink (> length 1)]
        ;(println "start-index" start-index "sub-sum" sub-sum "sub-vec" sub-vec)
        (cond
          (and (< sub-sum sum) can-expand) (recur start-index (inc length)) ; expand to right
          (and (> sub-sum sum) can-shrink) (recur (inc start-index) (dec length)) ; shrink from left
          (and (> sub-sum sum) can-expand) (recur (inc start-index) length) ; shift to right
          (= sub-sum sum) [start-index length]
          :else [-1 -1])))))

; Works also on infinite seq's
; Keeps the running sum to avoid re-computing it
; Does NOT work for negative numbers
(defn find-sum-3
  "...same as above..."
  [col sum]
  ;(println "====" sum)
  (loop [start-index 0
         sub-vec [(first col)]
         sub-sum (first col)
         col (rest col)]
    (let [next-item (first col)
          length (count sub-vec)
          can-shrink (> length 1)]
      ;(println "start-index" start-index "sub-sum" sub-sum "length" length "next-item" next-item "sub-vec" sub-vec)
      (cond
        (and (< sub-sum sum) next-item) (recur start-index  ; expand to right
                                               (conj sub-vec next-item)
                                               (+ sub-sum next-item)
                                               (rest col))
        (and (> sub-sum sum) can-shrink) (recur (inc start-index) ; shrink from left
                                                (vec (rest sub-vec))
                                                (- sub-sum (first sub-vec))
                                                col)
        (and (> sub-sum sum) next-item) (recur (inc start-index) ; shift to right
                                               (conj (vec (rest sub-vec)) next-item)
                                               (+ sub-sum (- (first sub-vec)) next-item)
                                               (rest col))
        (= sub-sum sum) [start-index length]                ; match
        :else [-1 -1]
        ))))

(deftest find-sum-test
  (let [standard-data [5, 4, 3, 9, 7, 2, 4, 61, 7, 8]
        tested-fn find-sum-3]
    (testing "Finite collection"
      (is (= [0 3] (tested-fn standard-data 12)) "Match at the start")
      (is (= [1 2] (tested-fn standard-data 7)) "Match right after start")
      (is (= [1 3] (tested-fn standard-data 16)) "Longer match right after start")
      (is (= [7 1] (tested-fn standard-data 61)) "Single match in the middle")
      (is (= [7 2] (tested-fn standard-data 68)) "Multiple match in the middle")
      (is (= [-1 -1] (tested-fn [5, 4] 68)) "Not found")
      (is (= [-1 -1] (tested-fn [5, 4, 9] 8)) "Not found, prevent start-index overflow")
      (is (= [-1 -1] (tested-fn [1 2 3] 0)) "Not found, zero sum does not mean empty sub-seq")
      (is (= [8 2] (tested-fn standard-data 15)) "Match at the end")
      (is (= [9 1] (tested-fn standard-data 8)) "Match last")
      (is (= [2 3] (tested-fn '(1 2 3 4 5 6) 12)) "Works for a list too")
      (is (= [99 1] (tested-fn (conj (vec (take 99 (repeat 1))) 100) 100)) "Edge case for version 2")
      )
    (testing "Negative numbers"
      (is (= [2 3] (tested-fn [1 2 3 -1 -2 4 5] 0)) "Zero")
      )
    (testing "Infinite sequence"
      (is (= [47 6] (tested-fn (iterate inc 1)
                               (->> (iterate inc 48)
                                    (take 6)
                                    (apply +)))))
      )))