Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Last active March 19, 2021 03:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ericnormand/c2c94f698bf3ace64c5f722da6dec2fc to your computer and use it in GitHub Desktop.
401 - PurelyFunctional.tv Newsletter -

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.

@sztamas
Copy link

sztamas commented Oct 28, 2020

@msladecek, how about something like this?

(defn sums-of-pairs [nums target]
  (let [idxs+nums (map-indexed vector nums)]
    (mapv (comp vec sort)
          (logic/run* [a b]
            (logic/fresh [a-idx b-idx]
              (logic/membero [a-idx a] idxs+nums)
              (logic/membero [b-idx b] idxs+nums)
              (fd/eq
                (< a-idx b-idx)
                (= target (+ a b))))))))

Based on @KingCode's map-indexed idea above.

@msladecek
Copy link

@sztamas nice!

@KingCode
Copy link

KingCode commented Oct 30, 2020

@sztamas, I am interested by your core.logic version, and will study it (and @msladecek's too, I need to learn core.logic) - neat stuff! Regarding your mention earlier regarding the original requirements of outputting the pairs in order of "discovery", thanks for explaining that too! (The original author's explanation on the JS site made little sense to many including myself). I agree it is a nice add-on to make this even more interesting and as you said, the natural combinatorial pair generation approach runs counter to that requirement. For this constraint, a natural traversal one element at a time with look-back (efficiently or not), is the way to go, e.g as in a run-of-the-mill reduction:

(defn sums-of-pairs [xs sum]
  (->> xs
       (reduce (fn [[pairs seen] x]
                 [(into pairs
                        (for [y seen
                              :when (= sum (+ x y))]
                          (sort [x y]))),
                  (conj seen x)])
               [[] []])
       first))

Which may explain why your core.logic version on example 3 outputs [[3 4] [2 5] [3 4]], unless maybe a small tweak would fix it? I am curious to see if it would be feasible or easier without map-indexed? I know nothing about core.logic, so please feel free to correct me.

@sztamas
Copy link

sztamas commented Oct 30, 2020

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

@vpetruchok
Copy link

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

@KingCode
Copy link

KingCode commented Nov 1, 2020

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

@proush42
Copy link

proush42 commented Nov 1, 2020

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

@Sinha-Ujjawal
Copy link

Sinha-Ujjawal commented Mar 19, 2021

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

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