Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Hello dear Code Reviewers,

I'm playing around with Clojure and am having a lot of fun. It's quite hard to go from imperative languages to Clojure, and I need some guidance on how to make the following code more idiomatic:

(ns cheaterpress.algorithm
  (:use [clojure.string :only [split lower-case]])
  (:use [clojure.test]))

(def words (split (slurp "words") #"\s"))

(defn string-to-letter-hash [string]
  (loop [letters (seq string) letter-hash {}]
    (if (empty? letters)
      letter-hash
      (let [letter (first letters) letter-freq (get letter-hash letter 0)]
        (recur (rest letters) (assoc letter-hash letter (inc letter-freq)))))))

(defn can-play [word letters index]
  (loop [letters letters index index]
    (if (and (= (inc index) (count word)) (not (= 1 (count word))))
      true
      (let [letter (get word index) frequency (get letters letter 0)]
        (when (not (= 0 frequency))
          (recur (assoc letters letter (dec frequency)) (inc index)))))))

(println 
  (time
    (count (doall (filter #(can-play % (string-to-letter-hash "abcdefghijklmnopqrstuvxyz") 0) (map lower-case words))))))

string-to-letter-hash takes a string and returns a map with the letter frequencies, e.g.:

(string-to-letter-hash "hello")
;=> {\h 1 \e 1 \l 2 \o 1}

can-play takes a letter frequency hash and a word, and then it finds out if it can make the word from the letters in the hash map. If it can, it returns true, otherwise, nil.

(can-play "hello" {\h 1 \e 1 \l 2 \o 1} 0)
;=> true
(can-play "lol" {\h 1 \e 1 \l 2 \o 1} 0)
;=> true
(can-play "hello world" {\h 1 \e 1 \l 2 \o 1} 0)
;=> nil

Thus what the last bit of code in my script does is basically get all the words in a file and find which of them can be played according to the can-play function.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Well there is a standard library function: frequences :)

user> (doc frequencies)
-------------------------
clojure.core/frequencies
([coll])
  Returns a map from distinct items in coll to the number of times
  they appear.

Since in Clojure many many types can be converted to sequences, frequencies will work on many types, including strings. In Clojure you can get an amazing amount of work done simply by using the sequence library. So your string-to-letter-hash is actually just an example of frequences.

For your can-play: the same type of thinking applies. Try to resist your first impulse of writing a loop. The Clojure library functions will almost always do the job - the thing that requires training is knowing the library well enough to find a good way to compose the functions.

(defn can-play? [word freqs]
  (every? #(>= % 0) (vals (merge-with - freqs (frequencies word)))))

(updated to comment version: https://gist.github.com/4105644)

share|improve this answer
    
What about the case (every? (complement nil?) (map (frequencies "helloworld") "hellohellohello"))? This will return true, but the word cannot be formed. –  Sirupsen Nov 18 '12 at 14:30
    
Also the behavior of: (every? freqs word) is equivalent to what you described, yeah? clojuredocs.org/clojure_core/clojure.core/every_q –  Sirupsen Nov 18 '12 at 14:38
    
I figured it out with multiple letters and frequencies I believe! gist.github.com/4105644 –  Sirupsen Nov 18 '12 at 14:48
add comment

Here is an implementation with recursion over the remaining letters and letter set:

(defn can-play [word available]
  (loop [[s & stem] (clojure.string/replace word #"\W" "") available available]
    (or (nil? s) ;; no more letters to check
      (and (pos? (available s 0)) ;; first letter must be in letterbox...
           ;; ...and the rest of the word must be playable after removing one
           ;; first instance of the first letter from the box
           (recur stem (update-in available [s] dec))))))
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.