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 is set, not a big deal.

(defn pair-match [socks]
  (reduce (fn [{:keys [pairs unmatched]} sock]
             (if (unmatched sock)
                {:pairs (conj pairs [sock sock]), :unmatched (disj unmatched sock)}
                {:pairs pairs, :unmatched (conj unmatched sock)}))
          {:pairs [], :unmatched #{}}
          socks))

(defn pair-match [socks]
  (reduce-kv (fn [m k cnt] (-> m
                               (update :pairs into (repeat (quot cnt 2) [k k]))
                               (cond-> (odd? cnt) (update :unmatched conj k))))
               {:pairs [] :unmatched []}
           (frequencies socks)))

Hello! It looks like I abused the threading macro :D
Could you, please give an advice to resolve this? Or it's not as bad after all?

(ns pf424sockpairs.core
  (:require [clojure.set]))

(defn pair-match
  "Given a bulk of socks, match pairs."
  [xs]
  (as-> xs _
    (->> _
         (group-by identity) (map last)
         (mapcat (partial partition-all 2))
         (group-by count))
    (-> _
        (clojure.set/rename-keys {1 :unmatched 2 :pairs})
        (update :unmatched flatten)
        (update :pairs vec))))

@safehammad I ended up with something very similar!

(defn pair-match [xs]
  (->> (sort xs)
       (partition-by identity)
       (mapcat (partial partition-all 2))
       (group-by (fn [x] (if (= (count x) 2) :pairs :unmatched)))))

@ZaymonFC Looks like this doesn't pass the tests.

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