Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
419 PurleyFunctional.tv Newsletter

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/

@mchampine
Copy link

mchampine commented Mar 22, 2021

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

@filippocostalli
Copy link

filippocostalli commented Mar 22, 2021

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

@sztamas
Copy link

sztamas commented Mar 22, 2021

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

@steffan-westcott
Copy link

steffan-westcott commented Mar 22, 2021

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

@arthurulacerda
Copy link

arthurulacerda commented Mar 22, 2021

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

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

@diavoletto76
Copy link

diavoletto76 commented Mar 22, 2021

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

@nwjsmith
Copy link

nwjsmith commented Mar 22, 2021

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

@jaihindhreddy
Copy link

jaihindhreddy commented Mar 23, 2021

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

@sztamas
Copy link

sztamas commented Mar 23, 2021

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

@dkmarley
Copy link

dkmarley commented Mar 23, 2021

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

@miner
Copy link

miner commented Mar 23, 2021

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

@galuque
Copy link

galuque commented Mar 23, 2021

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

@vpetruchok
Copy link

vpetruchok commented Mar 23, 2021

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

@vmpj
Copy link

vmpj commented Mar 26, 2021

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

@prairie-guy
Copy link

prairie-guy commented Apr 2, 2021

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

@prairie-guy
Copy link

prairie-guy commented Apr 2, 2021

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

@steffan-westcott
Copy link

steffan-westcott commented Apr 2, 2021

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

@prairie-guy
Copy link

prairie-guy commented Apr 2, 2021

Thanks.

@simbiotiqu
Copy link

simbiotiqu commented Apr 5, 2021

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

@s3dse
Copy link

s3dse commented Apr 9, 2021

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

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