August 14, 2018

Exercism - Anagram

Given a word and a list of possible anagrams, select the correct sublist.

Given "listen" and a list of candidates like "enlists" "google" "inlets" "banana" the program should return a list containing "inlets".

Inspired by the Extreme Startup game.

(ns anagram
  (:require [cljs.test :refer-macros [deftest is run-tests]]
            [clojure.string :as str]))

;; I already have this from another project:
(defn scramble?
  "Returns true if letters of string b are contained in string a."
  [a b]
 (every? #(>= (if (contains? (frequencies a) %)
                  (get (frequencies a) %)
              (get (frequencies b) %)) (keys (frequencies b))))
;; However, it currently does too much for this case,
;; because it tests whether a partial anagram exists. 
;; Let's go with it for now and wire it up:  
(defn anagrams-for [word prospect-list] ;; <- arglist goes here
  (filter #(scramble? word %) prospect-list))

(deftest no-matches
  (is (= []
         (anagram/anagrams-for "diaper" ["hello" "world" "zombies" "pants"]))))

(deftest detect-simple-anagram
  (is (= ["tan"] (anagram/anagrams-for "ant" ["tan" "stand" "at"]))))

(deftest does-not-confuse-different-duplicates
  (is (= [] (anagram/anagrams-for "galea" ["eagle"]))))

(deftest eliminate-anagram-subsets
  (is (= [] (anagram/anagrams-for "good" ["dog" "goody"]))))

(deftest detect-anagram
  (is (= ["inlets"]
         (let [coll ["enlists" "google" "inlets" "banana"]]
           (anagram/anagrams-for "listen" coll)))))

(deftest multiple-anagrams
  (is (= ["gallery" "regally" "largely"]
         (let [coll ["gallery" "ballerina" "regally"
                     "clergy"  "largely"   "leading"]]
           (anagram/anagrams-for "allergy" coll)))))

(deftest case-insensitive-anagrams
  (is (= ["Carthorse"]
         (let [coll ["cashregister" "Carthorse" "radishes"]]
           (anagram/anagrams-for "Orchestra" coll)))))

(deftest word-is-not-own-anagram
  (is (= [] (anagram/anagrams-for "banana" ["banana"]))))

(deftest capital-word-is-not-own-anagram
  (is (= [] (anagram/anagrams-for "BANANA" ["banana"]))))

As we can see, we are partially there already. We just need to catch the case of a word not being its own anagram, and not allow for partial words. It also must be case-insensitive, and must be the same length.

Let's make a new predicate function:

(defn anagram? [word prospect]
  (and (not= (str/lower-case word) (str/lower-case prospect))
       (= (count word) (count prospect))
       (every? #(= (if (contains? (frequencies (str/lower-case word)) %)
                     (get (frequencies (str/lower-case word)) %)
                   (get (frequencies (str/lower-case prospect)) %))
               (keys (frequencies (str/lower-case prospect))))))

Now we'll redefine anagrams-for to use that, and run our tests again:

(defn anagrams-for [word prospect-list] ;; <- arglist goes here
  (filter #(anagram? word %) prospect-list))

The "cleanup phase":

It works! But... we can't submit a solution looking like that. They'll say something like,

It passes the tests, but I feel that it could be more readable/idiomatic...

So we'll anticipate that and clean it up. For one thing, we can eliminate repeating (str/lower-case) by moving it to the second function:

(defn anagram? [word prospect]
  (and (not= word prospect)
       (= (count word) (count prospect))
       (every? #(= (if (contains? (frequencies word) %)
                     (get (frequencies word) %)
                   (get (frequencies prospect) %))
               (keys (frequencies prospect)))))
(defn anagrams-for [word prospect-list] ;; <- arglist goes here
  (filter #(anagram? (str/lower-case word) (str/lower-case %)) prospect-list))


Finally, we can define some let bindings to remove the repetition.

(defn anagram? [word prospect]
  (let [word-letters (frequencies word)
        prospect-letters (frequencies prospect)]
    (and (not= word prospect)
         (= (count word) (count prospect))
         (every? #(= (if (contains? word-letters %)
                       (get word-letters %)
                     (get prospect-letters %))
                 (keys prospect-letters)))))

(defn anagrams-for [word prospect-list]
  (filter #(anagram? (str/lower-case word)
                     (str/lower-case %))


Looks good to me! View my solution on Exercism. A friendly mentor will be commenting on it shortly!


As it turns out, the solution can be made much simpler by forgetting about the whole frequencies business and just sorting the words alphabetically:

(defn anagram? [word prospect]
    (and (not= word prospect)
         (= (sort word) (sort prospect))))

(defn anagrams-for [word prospect-list]
  (filter #(anagram? (str/lower-case word)
                     (str/lower-case %))


And the solution was approved! See you in the next post.

Tags: coding exercises KLIPSE Exercism Clojure