424 PurelyFunctional.tv Newsletter

00 Sock pairs.md

Sock pairs

After doing laundry, your socks are unmatched to their pairs. You need to match them!

Write a function that takes a collection of values and makes pairs if they are equal. If there is not a match for a particular value, return it as well.

(pair-match []) ;=> {:pairs [] :unmatched []}
(pair-match [1 2 1]) ;=> {:pairs [[1 1]] :unmatched [2]}
(pair-match [1 2 3 1 2 3 1 1 2]) ;=> {:pairs [[1 1] [2 2] [3 3] [1 1]] 
                                 ;=>  :unmatched [2]}

Note: It's like socks. If you have 3 blue socks, that's one pair and one unmatched. If you have 4 blue socks, that's two pairs.

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

Please submit your solutions as comments on this gist.

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

Unmatched as a set feels right 👍

(defn pair-match
  "Given a bulk of socks, match pairs. Iteratively."
  [xs]
  (let [makes-pair? (fn [acc x] (contains? (:unmatched acc) x))
        start-pair (fn [acc x] (update acc :unmatched conj x))
        promote-pair (fn [acc x] (-> acc
                                     (update :unmatched disj x)
                                     (update :pairs conj [x x])))]
    (as-> xs _
      (reduce (fn [acc x]
              (cond
                (makes-pair? acc x) (promote-pair acc x)
                :else (start-pair acc x)))
            {:pairs [] :unmatched #{}}
            _)
      (update _ :unmatched vec))))

As a monoid:

(defn ->pairs [v]
  {:pairs [] :unmatched #{v}})

(defn pairs-merge [a b]
  (let [matches (clojure.set/intersection (:unmatched a)
                                          (:unmatched b))]
    {:pairs (-> (:pairs a)
                (into (:pairs b))
                (into (map (juxt identity identity) matches)))
     :unmatched (-> (:unmatched a)
                    (clojure.set/union (:unmatched b))
                    (clojure.set/difference matches))}))

(defn pair-match [coll]
  (->> coll
       (map ->pairs)
       (reduce pairs-merge {:pairs [] :unmatched #{}})))

As reduction:

(defn pairs-conj [{:keys [pairs unmatched]} v]
  (if (contains? unmatched v)
    {:pairs (conj pairs [v v]) :unmatched (disj unmatched v)}
    {:pairs pairs              :unmatched (conj unmatched v)}))

(defn pair-match [coll]
  (reduce pairs-conj {:pairs [] :unmatched #{}} coll))