415 PurelyFunctional.tv Newsletter

00 Pattern matching.md

Pattern matching

When describing rhyming patterns, poets use letters to define patterns, like this:

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

This poem has an ABCB rhyming structure because the B lines rhyme and A and C do not.

We'll use this same naming scheme but use equality instead of rhyming. Write a function that takes a sequence of values and a pattern string. It returns a a map of letters to values if the pattern matches, and nil if it does not.

Examples:

(pattern [1 2 1 2] "ABAB") ;=> {\A 1 \B 2}
(pattern [1 2 3 2] "ABCB") ;=> {\A 1 \B 2 \C 3}
(pattern [1 2 3 4] "ABAB") ;=> nil
(pattern [1 1 1 1] "A") ;=> nil (wrong number of elements)
(pattern [1 1 1 1] "ABCD") ;=> {\A 1 \B 1 \C 1 \D 1}
(pattern [1 4 2 1] "ADCA") ;=> {\A 1 \D 4 \C 2}

Thanks to this site for the challenge idea where it is considered Expert in JavaScript. The problem has been modified from the original.

Please submit your solutions as comments on this gist.

(defn pattern [xs pat]
  (when (= (count xs) (count pat))
    (let [kvs (set (map vector pat xs))
          result (into {} kvs)]
      (when (= (count kvs) (count result))
        result))))

(defn pattern [p s]
  (when (= (count p) (count s))
    (let [m (zipmap s p)]
      (when (<= (count (set p)) (count m))
          m))))

@werand You may want to take another look, as (pattern [1 2 1] "ABB") should return nil

@steffan-westcott you are right, i have been too lazy with my tests and thinking, here is a different version

(defn join-unique-value [m [p v]]
  (when (and ((complement nil?) m) (= (get m v p) p))
        (assoc m v p)))

(defn pattern [p v]
  (when (= (count p) (count v))
    (->> (map vector p v)
         (reduce join-unique-value {}))))

(def patterns
  [[[1 2 1 2] "ABAB"]
   [[1 2 3 2] "ABCB"]
   [[1 2 3 4] "ABAB"]
   [[1 1 1 1] "A"]
   [[1 1 1 1] "ABCD"]
   [[1 4 2 1] "ADCA"]
   [[1 2 1] "ABB"]])

(defn pattern [[xs ys]]
  (let [m (zipmap ys xs)]
    (when (= xs (map m ys))
      m)))

(comment
  (map pattern patterns)
  ;; => ({"A" 1, "B" 2}
  ;;     {"A" 1, "B" 2, "C" 3}
  ;;     nil
  ;;     nil
  ;;     {"A" 1, "B" 1, "C" 1, "D" 1}
  ;;     {"A" 1, "D" 4, "C" 2}
  ;;     nil)
  )

(defn pattern [vs ks]                                                                                                                                 
  (let [zm (zipmap ks vs)]                                                                                                                            
    (if (not= vs (map zm ks))                                                                                                                         
      nil                                                                                                                                             
      zm)))