456 PurelyFunctional.tv Newsletter

00 Rhyming scheme equivalence.md

Rhyming scheme equivalence

Roses are red    A
Violets are blue B
Sugar is sweet   C
And so are you   B

English teachers like to represent the rhyming pattern of poems with letters. Each line rhymes with lines with the same letter. In this case, B lines rhyme together, but the A and C lines don't rhyme. We will call that a "ABCB" rhyming scheme. However, the choice of letters is arbitrary. We could have called it "IBPB" or "XALA".

We want a way to know if two rhyming schemes are equivalent. Write a function that returns nil if they are not equivalent and returns a map of replacements if they are equivalent.

Examples

(equiv? "ABCB" "XALA") ;=> {\A \X \B \A \C \L}
(equiv? "A" "A") ;=> {}
(equiv? "A" "B") ;=> {\A \B}
(equiv? "AB" "A") ;=> nil
(equiv? "ABB" "XXY") ;=> nil

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 equiv? [a b]
  (let [index #(into {} (map vector (distinct %) (range)))]
    (when (= (map (index a) a) (map (index b) b))
      (->> (map vector a b)
           (remove #(apply = %))
           (into {})))))

(defn signature [s]
  (map (zipmap (distinct s) (range)) s))

(defn equiv? [s1 s2]
  (when (= (signature s1) (signature s2))
    (into {} (remove #(apply = %)) (zipmap s1 s2))))

Edit: Corrected algorithm, with thanks to @miner

What is the correct result for (equiv? "ABCA" "ABBA")? I think it should be nil (no match), not {\C \B}.

Correct, it must be nil in this case. So, my code is wrong.
Thank you for your comment.

I think now it's correct. A bit long but I think it's clear.

(ns rhyming-scheme-eqv)

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

(defn is-in-seq? [elt1 secuencia]
    (not (empty? (filter (fn [elt2] (= elt1 elt2)) secuencia))))

(defn equiv? [str1 str2]
    (cond
        ; si las 2 cadenas tienen diferente longitud, devuelve nil.
        (not (= (count str1) (count str2))) nil 
        :else 
            (loop [str1 str1
                   str2 str2
                   out {}]
                ; si llegamos al final de las cadenas, 
                (if (empty? str1)
                    ; eliminamos los pares cuya clave y valor son iguales y lo 
                    ; convertimos en un map.
                    (into {} (filter (fn [elt] (not (= (first elt) (second elt)))) out))
                    ; En otro caso, procesamos las cadenas
                    (let [nueva-clave (first str1)
                          nuevo-valor (first str2)
                          viejo-valor (get out nueva-clave) ; si la nueva-clave no se encuentra
                                                             ; en el hash-map, devuelve nil
                          valores (vals out)] 
                        (cond
                            ; si la clave no se encuentra en el hash-map y el nuevo valor no esta en el 
                            ; hash-map, se añade la nueva clave con su nuevo valor
                            (= viejo-valor nil) 
                                (if (is-in-seq? nuevo-valor valores) 
                                    nil
                                    (recur (rest str1) (rest str2) (assoc out nueva-clave nuevo-valor)))
                            ; si el nuevo valor y el viejo valor son iguales, no se repiten
                            (= nuevo-valor viejo-valor) (recur (rest str1) (rest str2) out)
                            ; y si el nuevo valor y el viejo valor son diferentes, devuelve nil.
                            :else nil))))))


; Pruebas unitarias
(test/testing "Pruebas eqv"
    (test/is (= (equiv? "ABCB" "XALA") {\A \X \B \A \C \L}))
    (test/is (= (equiv? "A" "A") {}))
    (test/is (= (equiv? "A" "B") {\A \B}))
    (test/is (= (equiv? "AB" "A") nil))
    (test/is (= (equiv? "ABB" "XXY") nil))
    (test/is (= (equiv? "ABCA" "ABBA") nil)))

I like the solution by @steffan-westcott. Here's a variation, going for performance. Most of the input strings are short so index-of works well for the signature.

(defn equiv? [s1 s2]
  (let [signature (fn [s] (mapv #(clojure.string/index-of s %) s))]
    (if (= s1 s2)
      {}
      (when (= (signature s1) (signature s2))
        (let [z (zipmap s1 s2)]
          (reduce-kv (fn [m k v] (if (= k v) (dissoc m k) m))
                     z
                     z))))))

(defn equiv? [sc1 sc2]
  (when (= (count sc1) (count sc2))
    (->> sc2 (map vector sc1)
         (reduce (fn [m [c1 c2 :as c1c2]]
                   (cond
                     (not (contains? m c1))
                     (conj m c1c2)
                     (not= c2 (get m c1))
                     (reduced nil)
                     :else
                     m))
                 {})
         ((fn [m] (and m (->> m (into {} (remove #(apply = %))))))))))