458 PurelyFunctional.tv Newsletter

00 String difference.md

String difference

Imagine two strings, A and B. B is generated by shuffling the letters in A and adding a new random letter to it at a random position. Write a function that takes A and B and returns the new letter.

Examples

(diff "" "j") ;=> \j
(diff "a" "ab") ;=> \b
(diff "abc" "xcab") ;=> \x
(diff "xxyyzz" "xzyfyxz") ;=> \f
(diff "cccvv" "cvvcvc") ;=> \v

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

Please submit your solutions as comments on this gist.

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

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

(defn diff [a b]
  ((s/map-invert (merge-with - (frequencies b) (frequencies a))) 1))

Revised version using sum of characters:

(defn char-sum [s]
  (apply + (map int s)))

(defn diff [before after]
  (char (- (char-sum after)
           (char-sum before))))

bit-xor is another possibility:

(defn diff [before after]
  (char (reduce (cat ((map int) bit-xor)) 0 [before after])))

(defn diff [a b]
 (ffirst (clojure.set/difference 
           (set (frequencies b))
           (set (frequencies a)))))

(defn diff [a b] (first (reduce #(clojure.string/replace-first %1 %2 "") b a)))

(defn diff
  "Returns the character in the second string that isn't in the first."
  [a b]
  (->> (merge-with - (frequencies (seq a)) (frequencies (seq b)))
       (filter #(not (zero? (val %))))
       first
       key))

(defn diff
  [s1 s2]
  (let [freq1 (frequencies s1)
        freq2 (frequencies s2)]
    (ffirst (filter (fn [[k v]] (not= (freq1 k) v)) freq2))))

As usual, frequencies is such a useful tool for such problems!

(defn mdiff [m1 m2]
  (into {}
        (map (fn [k]
               {k (- (m1 k 0) (m2 k 0))})
             (keys (merge m1 m2)))))

(defn diff [s1 s2]
  (->> (mdiff (frequencies s1) (frequencies s2))
       (keep (fn [[k v]] (when (< v 0) k)))
       first))

(defn diff [astr bstr]
  (loop [sa (sort astr) sb (sort bstr)]
    (if (= (first sa) (first sb))
      (recur (rest sa) (rest sb))
      (first sb))))

(defn diff [a b]
  (reduce-kv (fn [_ c cnt] (when (odd? cnt) (reduced c)))
             nil
             (frequencies (str a b))))

@miner I really like that concatenation/odd? trick

(defn diff
  [a b]
  (key (first (filter (comp odd? val) (frequencies (str a b))))))

a transducer version, based on the bit-xor solution by @jonasseglare

(defn diff [before after]
  (transduce (map int)
             (completing bit-xor char)
             0
             (str before after)))

(defn diff [s1 s2]
  (clojure.string/replace 
    (apply str (sort s2)) 
    (re-pattern (apply str (sort s1))) 
    "")) 

(defn diff [a b]
  (let [fa (frequencies a) fb (frequencies b)]
    (->> b (some #(when (or (not (contains? fa %))
                            (not= (fa %) (fb %)))
                    %)))))