Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Created January 10, 2022 14:03
Show Gist options
  • Save ericnormand/87c7c0804b2cde1a1a1e65caaf4c5296 to your computer and use it in GitHub Desktop.
Save ericnormand/87c7c0804b2cde1a1a1e65caaf4c5296 to your computer and use it in GitHub Desktop.
458 PurelyFunctional.tv Newsletter

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/

@steffan-westcott
Copy link

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

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

@jonasseglare
Copy link

jonasseglare commented Jan 10, 2022

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

@ndonolli
Copy link

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

@mchampine
Copy link

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

@nwjsmith
Copy link

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

@brunchboy
Copy link

brunchboy commented Jan 11, 2022

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

@PEZ
Copy link

PEZ commented Jan 11, 2022

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

@miner
Copy link

miner commented Jan 11, 2022

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

@miner
Copy link

miner commented Jan 11, 2022

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

@nwjsmith
Copy link

@miner I really like that concatenation/odd? trick

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

@miner
Copy link

miner commented Jan 11, 2022

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

@filippocostalli
Copy link

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

@KingCode
Copy link

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

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