419 PurleyFunctional.tv Newsletter

00 String difference.md

String difference

You are given two strings, a and b. We consider each letter to be unique, meaning duplicates are significant. Write a function that returns the count of letters in b which do not occur in a.

Examples

(strdiff "abc" "") ;=> {} ;; no characters in b don't occur in a
(strdiff "abc" "abc") ;=> {} ;; ditto
(strdiff "" "abc") ;=> {\a 1 \b 1 \c 1}
(strdiff "axx" "abcc") ;=> {\b 1 \c 2}
(strdiff "xxxx" "xxxxxx") ;=> {\a 2} ;; two x's in b that don't occur in a

Thanks to this site for the challenge idea where it is considered Hard in Python. The problem has been modified from the original.

Please submit your solutions as comments on this gist.

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

(defn strdiff [s1 s2]
  (-> (fn [s c] (let [[b a] (split-with #(not= % c) s)]
                  (apply str (concat b (rest a)))))
      (reduce s2 s1)
      frequencies))

(defn my-contains? [m [k v]]
  (= (get m k) v))

(defn strdiff [s1 s2]
  (let [im1 (into {} (map-indexed (fn [idx itm] [idx itm]) s1))]
    (->> s2
      (map-indexed (fn [idx itm] [idx itm]))
      (into {})
      (filter #(not (my-contains? im1 %)))
      (map (fn [[k v]] v))
      (apply str)
      (frequencies))))

(defn strdiff [a b]
  (->> (merge-with - (frequencies b) (select-keys (frequencies a) (set b)))
       (filter (comp pos? second))
       (into {})))

(defn strdiff [a b]
  (->> (reduce-kv (fn [m ch freq] (update m ch (fnil - 0) freq)) (frequencies b) (frequencies a))
    (filter (comp pos? val))
    (into {})))

(require '[clojure.string :as s])

(defn strdiff
  [s1 s2]
  (frequencies (reduce #(s/replace-first %1 %2 "") s2 s1)))

(defn strdiff [xs ys]
  (let [fx (frequencies xs)
        fy (frequencies ys)
        kx (into #{} (keys fx))
        ky (into #{} (keys fy))
        k-common (into [] (clojure.set/intersection kx ky))]
    (->> (merge-with - fy (select-keys fx k-common))
         (filter (fn [[_ v]] (> v 0)))
         (into {}))))

(defn strdiff
  "Returns the count of letters in b which do not occur in a."
  [a b]
  (dissoc (frequencies (map-indexed (fn [i ch] (if (= (get a i) ch) nil ch))
                                    b))
          nil))

(defn strdiff [a b]
  (->> (select-keys (frequencies a) (set b))
       (merge-with - (frequencies b))
       (remove (comp zero? val))
       (into {})))

fixed version, thanks to @sztamas!

(defn strdiff [a b]
  (->> (select-keys (frequencies a) (set b))
       (merge-with - (frequencies b))
       (filter (comp pos? val))
       (into {})))

@jaihindhreddy might worth mentioning that you have to remove negatives as well (not just zeros) or characters that have more occurrences in a than b will end up in the final map. Ex.

  (strdiff "xxx" "x") ;; => {\x -2}

(defn strdiff [a b]
  (->> (distinct b)
       (select-keys (frequencies a))
       (merge-with - (frequencies b))
       (reduce-kv (fn [m k v] (if (pos? v) (assoc m k v) m)) {})))

(defn strdiff [a b]
  (reduce (fn [m c]
            (if-let [n (get m c)]
              (if (= n 1)
                (dissoc m c)
                (assoc m c (dec n)))
              m))
          (frequencies b)
          (seq a)))

;; slightly faster with transients
(defn tstrdiff [a b]
  (persistent!
   (reduce (fn [m c]
             (if-let [n (get m c)]
               (if (= n 1)
                 (dissoc! m c)
                 (assoc! m c (dec n)))
               m))
           (transient (frequencies b))
           (seq a))))

Definitely feel like I'm cheating 😛

(require '[clojure.data :as data])

(defn strdiff [s1 s2]
  (let [[_ only-in-s2 _] (data/diff (vec s1)
                                    (vec s2))]
    (->> only-in-s2
         (filter some?)
         frequencies)))

(defn strdiff [a b]
  (let [a-freq (frequencies a)
        b-freq (frequencies b)]
    (reduce-kv (fn [r b-key b-val]
                 (if (not (contains? a-freq b-key))
                   (assoc r b-key b-val)
                   (let [a-val (get a-freq b-key)
                         diff (- b-val a-val)]
                     (if (> diff 0)
                       (assoc r b-key diff)
                       r))))
               {}
               b-freq)))

(defn strdiff [a b]
  (let [fa (frequencies a) 
        fb (frequencies b)]
    (->> (reduce-kv #(update %1 %2 (fnil - 0) %3) fb fa)
         (filter #(> (second %) 0)) 
         (into {}))))

(use '[clojure.set :only (difference intersection)])

(defn strdiff [a b]                                                                                                                                   
  (let [fa (frequencies a)                                                                                                                            
        fb (frequencies b)                                                                                                                            
        ka (set (keys fa))                                                                                                                            
        kb (set (keys fb))]                                                                                                                           
    (apply array-map 
     (flatten                                                                                                                         
      (append(for [i (intersection ka kb)                                                                                                             
                   :let [n (- (fb i) (fa i))]                                                                                                         
                   :when (> n  0)]                                                                                                                    
               [i n])                                                                                                                                 
             (for [d (difference kb ka)] [d (fb d)]))))))

Basic question: How do I get highlighted code? First time posting . . .

@prairie-guy To get syntax highlighting, wrap your code between ```clojure and ``` on their own lines. See the Github docs on syntax highlighting for more examples.

Thanks.

(defn update-freq-map [m k v]
  (if (get m k)
    (update m k #(- % v))
    m))

(defn dissoc-less-one [m]
  (let [less-one-key (->> m
                          (filter (fn [[_ v]] (< v 1)))
                          (map first))]
    (reduce
     (fn [m k] (dissoc m k))
     m
     less-one-key)))

(defn strdiff [a b]
  (let [freq-a (frequencies a)
        freq-b (frequencies b)]
    (->> (reduce-kv
          update-freq-map
          freq-b
          freq-a)
         dissoc-less-one)))

(defn strdiff [a b]
  (loop [freq-b (frequencies b)
         acc {}]
    (cond
      (or (= a b) (empty? freq-b)) acc
      (empty? a) freq-b
      :else
      (let [[k vb] (first freq-b)
            va ((frequencies a) k 0)
            diff (- vb va)]
        (if (pos-int? diff)
          (recur (rest freq-b) (assoc acc k diff))
          (recur (rest freq-b) acc))))))