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/

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