402 - PurelyFunctional.tv Newsletter

00 Most frequent element.md

Most frequent element

Write a function that takes a collection and returns the most frequent element. But here's the thing: you can't use the built-in function clojure.core/frequencies. And if there are ties, just pick one.

Examples

(most-frequent [2 2 3 4 4 2 1 1 3 2]) ;=> 2
(most-frequent []) ;=> nil
(most-frequent [1 1 4 4 5]) ;=> 4

Notes

• return nil for an empty collection
• in the case of a tie, return one of the winners

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

Please submit your solutions as comments on this gist.

A small tweak to my first effort to avoid the sort:

(defn most-frequent [xs]
  (some->> xs (group-by identity) vals (apply max-key count) first))

I'm sure our answers are anagrams of each other 😀

(defn most-frequent [coll]
  (let [freqs (reduce (fn [m x]
                        (assoc m x (inc (get m x 0))))
                      {}
                      coll)]
    (->> (sort-by second > freqs)
         ffirst)))

I struggled a bit with how to unit-test this so I skipped that in my first submission. Here's a take on that that I'd like feedback on:

(defn most-frequent 
  {:test (fn []
           (are [accepted coll]
                (some #(= % (most-frequent coll)) accepted)
             [2]    [2 2 3 4 4 2 1 1 3 2]
             [nil]  []
             [1 4]  [1 1 4 4 5]
             [true] [nil "hello" true nil true true]))}
  [coll]
  (some->> coll
           (group-by identity)
           vals
           (sort-by count #(> %1 %2))
           first
           first))

(defn most-frequent-stream
  "Lazy sequence of which element has occurred most often up through point in collection"
  ([xs] (most-freq-stream xs {}))
  ([xs counts] (most-freq-stream xs counts nil))
  ([xs counts mf]
   (lazy-seq
    (when (seq xs)
      (let [x (first xs)               ;; Will referencing head here be issue?
            xc (inc (or (counts x) 0)) ;; x count
            mc (or (counts mf) 0)      ;; max frequent val count
            nmf (if (< xc mc) mf x)]   ;; new most frequent val
        (cons nmf
              (most-freq-stream (rest xs) (assoc counts x xc) nmf)))))))

(defn most-frequent
  "Return most frequent element in coll. In event of a tie, return the first to hit that frequency"
  {:test #(do
            (assert (= (most-frequent [2 2 3 4 4 2 1 1 3 2]) 2)) ;=> 2
            (assert (nil? (most-frequent []))) ;=> nil
            (assert (= (most-frequent [1 1 4 4 5]) 4)))}
  [xs]
  (last (most-freq-stream xs)))

(test #'most-frequent)