401 - PurelyFunctional.tv Newsletter -

00 sums of pairs.md

Sums of pairs

Write a function that takes a collection of numbers and a target number. Return all pairs of numbers found in the collection that sum up to the target number.

Examples

(sums-of-pairs [2 4 5 6] 8) ;=> [[2 6]]
(sums-of-pairs [3 2 0 1 1 5] 5) ;=> [[2 3] [0 5]]
(sums-of-pairs [1 3 2 3 4 5] 7) ;=> [[3 4] [3 4] [2 5]]

Notes

• There can be duplicate numbers.
• Each pair should be sorted.

Thanks to this site for the challenge idea where it is considered Expert level in JavaScript.

Please submit your solutions as comments on this gist.

@KingCode, I'm sorry if I gave the impression I'm a core.logic expert :).
I actually never used core.logic before, just found the problem posed by @msladecek's solution interesting enough to look into it a bit.

I'm not sure if your proposed solution is the only way to go.
The O(n) solution we co-edited above also outputs [[3 4] [3 4] [2 5]] for example 3, doesn't it?

And for the solutions based on map-indexed you could keep the indexes where you found the pairs and sort based on those.
Something along the lines of (when adapting your original solution):

(defn sums-of-pairs [xs sum]
  (->> xs (map-indexed vector)
       ((fn [ixs]
          (for [[i x] ixs
                [j y] ixs
                :when (< i j)
                :when (= sum (+ x y))]
            [[(max i j) i] (sort [x y])])))
       (sort-by first)
       (mapv second)))

For the core.logic solution I assume you could do the sorting similarly as a last step, but it might be possible to set it all up in core.logic.
I'm not sure, would have to check.

(defn sums-of-pairs
  ([numbers target-number]) (sums-of-pairs numbers target-number [])

  ([numbers target-number acc]
   (if (empty? numbers)
     acc
     (let [[i & others] numbers
           res (for [j others :when (= target-number (+ i j))]
                 (vec (sort [i j])))
           acc' (into acc res)]
       (recur others target-number acc')))))

@sztamas, nice rewrite! I love your arithmetic on the indexes, I wish I had thought of that :)

Yes indeed the previous solution with your O(n) alg. did pass the order test, and I was agreeing with you in my post, sorry about the confusion..

(defn sums-of-pairs [xs trg]
  (let [match? (fn [[a b]] (= trg (+ a b)))
        combos (for [i (range (count xs))
                     j (range (inc i) (count xs))]
                 [(nth xs i) (nth xs j)])]
    (->> (filter match? combos)
         (map sort))))

Is it too late to answer? My solution to the problem-

(defn sums-of-pairs 
    [ns target] (first (reduce (fn [[l m] n]
                                   [(concat l (repeat (get m n 0) (sort [n (- target n)])))
                                    (update m (- target n) (fn [x] (if (= x nil) 1 (+ x 1))))]) [[] {}] ns)))
;; O(N) solution