2
\$\begingroup\$

I have a safe with a manual combination lock that I periodically change the combination to. I like to use a combination that's easy for me to remember, so I thought I'd write a quick Clojure program to make it easier to pick a new combination.

Note: When I say "combination" in this write-up it means the numbers used to open the lock, not a mathematical combination.

Rules for selecting a new combination:

The rules for choosing combinations are in the Operating/Changing Instructions for the lock (see "Selecting A New Combination") but I'll repeat them here:

Observing the following rules will help you select a new combination which is secure and which will optimize the design strengths of your Sargent & Greenleaf lock.

  1. Do not select numbers which all end in “0” and “5.” An example of a poor combination is: "50 – 15 – 30." An example of a good combination is: "52 – 15 – 37."

  2. Do not select numbers in an ascending or descending sequence. An example of a poor combination is: "22 – 41 – 68." An example of a good combination is: "22 – 68 – 41."

  3. Leave at least a ten number margin between adjacent numbers of the combination. An example of a poor combination is: "41 – 39 – 66." An example of a good combination is: "41 – 30 – 66."

  4. Do not use a number between 95 and 99 or between 0 and 20 for the third (or last) number of the combination. This can cause a condition which will inhibit the mechanism from locking correctly.

English words:

It's easier for me to remember an English word than a random sequence of numbers, so I thought I would get some help from a dictionary. I want all the six-character words in English that, when each character is mapped to a digit in the combination using the telephone keypad, fulfill the rules for selecting combinations. For example, "benign" is 23-64-46.

I found a text file listing over 355,000 words in the English language here, and used a little unix shell magic to pull out all the six-character words into a separate file:

$ cat words.txt | grep "^[a-z]\{6\}$" > six-character-words.txt

Approach:

I considered two approaches.

The first approach (which I rejected) was to check every six-digit permutation for the ones that make an English word when mapped to letters using the telephone keypad, and that conform to the rules for selecting a combination. There are 8 choices for each digit (2-9 since 0 and 1 don't map to a character on the telephone keypad) and six digits per combination, so that's 8^6=262144 permutations. It's worse than that, because each digit represents 3 or 4 characters so for each permutation you have to check at least 3^6=729 permutations of characters (actually more because 7 and 9 map to 4 characters). This is getting really expensive.

The second approach (which I used) was to check each six-character English word by converting it to a combination and validating the combination using the rules from the manual. There are only about 28,000 six-character English words.

Code:

Please critique my code! Obviously I'm interested in fixing any bugs, but I'm also always looking for ways to be clearer, more idiomatic, more efficient, etc.

(use 'clojure.java.io)

(defn abs [n] (max n (- n)))

(defn keypad-numbers [word]
  "Generates a vector of digits from the letters in a word using the standard telephone keypad mapping of numbers and letters"
  (let [keypad {:a 2 :b 2 :c 2
                :d 3 :e 3 :f 3
                :g 4 :h 4 :i 4
                :j 5 :k 5 :l 5
                :m 6 :n 6 :o 6
                :p 7 :q 7 :r 7 :s 7
                :t 8 :u 8 :v 8
                :w 9 :x 9 :y 9 :z 9 }]
    (vec (map keypad (map keyword (map str (seq word)))))))

(defn combo-numbers [combo-digits]
  "Generates a vector of combination numbers from a vector of combination digits"
  (let [a (+ (* 10 (combo-digits 0)) (combo-digits 1))
        b (+ (* 10 (combo-digits 2)) (combo-digits 3))
        c (+ (* 10 (combo-digits 4)) (combo-digits 5))]
    [a b c]))

(defn all-end-with? [numbers combo-digits]
  "Checks if the last digit of the combination's numbers all end with one of the provided numbers"
  (let [a (combo-digits 1)
        b (combo-digits 3)
        c (combo-digits 5)]
    (and
        (not (nil? (some #(= a % ) numbers)))
        (not (nil? (some #(= b % ) numbers)))
        (not (nil? (some #(= c % ) numbers))))))

(defn ascending? [combo-digits]
  "Checks if the numbers in the combination are ascending (e.g. 23 56 72)"
  (let [nums (combo-numbers combo-digits)]
    (and (> (nums 2) (nums 1)) (> (nums 1) (nums 0)))))

(defn descending? [combo-digits]
  "Checks if the numbers in the combination are descending (e.g. 72 56 23)"
  (let [nums (combo-numbers combo-digits)]
    (and (< (nums 2) (nums 1)) (< (nums 1) (nums 0)))))

(defn has-margin? [margin combo-digits]
  "Checks if the numbers in the combination are separated by a margin"
  (let [nums (combo-numbers combo-digits)]
    (and (> (abs (- (nums 0) (nums 1))) margin)
         (> (abs (- (nums 1) (nums 2))) margin))))

(defn taboo-last-number? [combo-digits]
  "Checks if the last number in the combination is between 95 and 99, or 0 and 20"
  (let [nums (combo-numbers combo-digits)]
    (or
      (and (>= (nums 2) 0) (<= (nums 2) 20))
      (and (>= (nums 2) 95) (<= (nums 2) 99)))))

(defn valid-combination? [combo-digits]
  (and (not (all-end-with? [0 5] combo-digits))
       (not (ascending? combo-digits))
       (not (descending? combo-digits))
       (has-margin? 10 combo-digits)
       (not (taboo-last-number? combo-digits))))

(defn with-lines [fname fun]
  "Executes a function for each line in a file"
  (with-open [rdr (reader fname)]
    (doseq [line (line-seq rdr)] (fun line))))

(with-lines
  "/home/erturne/nas/Development/sargent_combination/six-character-words.txt"
  (fn [line]
    (let [combo-digits (keypad-numbers line)]
      (if (valid-combination? combo-digits)
        (let [nums (combo-numbers combo-digits)]
            (println (str line " - " (format "%s-%s-%s"
                                             (nums 0)
                                             (nums 1)
                                             (nums 2)))))))))
\$\endgroup\$
3
\$\begingroup\$

I would

  1. Calculate the combination-numbers in valid-combination and send these numbers to the separate checking-functions instead of the combination-digits
  2. Remove the assertion that the combination consists of 3 numbers as much as possible.
  3. Exploit the fact that < and > may take more than 2 arguments.
  4. Exploit the fact that a combination number may never be < 0 or > 99

The modified code then becomes:

(use 'clojure.java.io)

(defn abs [n] (max n (- n)))

(defn keypad-numbers [word]
  "Generates a vector of digits from the letters in a word using the standard telephone keypad mapping of numbers and letters"
  (let [keypad {:a 2 :b 2 :c 2
                :d 3 :e 3 :f 3
                :g 4 :h 4 :i 4
                :j 5 :k 5 :l 5
                :m 6 :n 6 :o 6
                :p 7 :q 7 :r 7 :s 7
                :t 8 :u 8 :v 8
                :w 9 :x 9 :y 9 :z 9 }]
    (vec (map keypad (map keyword (map str (seq word)))))))

(defn combo-numbers [combo-digits]
  "Generates a vector of combination numbers from a vector of combination digits"
  (map (fn [[tens ones]] (+ (* 10 tens) ones))
       (partition 2 combo-digits)))

(defn ascending? [combo-numbers]
  "Checks if the numbers in the combination are ascending (e.g. 23 56 72)"
  (apply < combo-numbers))

(defn descending? [combo-numbers]
  "Checks if the numbers in the combination are descending (e.g. 72 56 23)"
  (apply > combo-numbers))

(defn all-end-with? [numbers combo-numbers]
  "Checks if the last digit of the combination's numbers all end with one of the provided numbers"
  (every? identity  ; this is a working alternative to (reduce and ...)
          (map (fn [number] (some #(= (mod number 10) %) numbers))
               combo-numbers)))

(defn has-margin? [margin combo-numbers]
  "Checks if the numbers in the combination are separated by a margin"
  (every? identity
          (map (fn [[n1 n2]] (> (abs (- n1 n2)) margin))
               (partition 2 1 combo-numbers))))

(defn taboo-last-number? [combo-numbers]
  "Checks if the last number in the combination is not between 20 and 95"
  (let [last-number (last combo-numbers)]
    (or (<= last-number 20)
        (>= last-number 95))))

(defn valid-combination? [combo-digits]
  "Check that combo-digits can form a good combination"
  (let [combo-numbers (combo-numbers combo-digits)]
    (and 
       (not (all-end-with? [0 5] combo-numbers))
       (not (ascending? combo-numbers))
       (not (descending? combo-numbers))
       (has-margin? 10 combo-numbers)
       (not (taboo-last-number? combo-numbers)))))

(defn with-lines [fname fun]
  "Executes a function for each line in a file"
  (with-open [rdr (reader fname)]
    (doseq [line (line-seq rdr)] (fun line))))

(with-lines
  "/home/erturne/nas/Development/sargent_combination/six-character-words.txt"
  (fn [line]
    (let [combo-digits (keypad-numbers line)]
      (if (valid-combination? combo-digits)
        (let [nums (combo-numbers combo-digits)]
            (println (str line " - " (format "%s-%s-%s"
                                             (nums 0)
                                             (nums 1)
                                             (nums 2)))))))))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Function keypad-numbers

First of all do not call seq on a collection before passing it to map, map already does it.

This is too verbose, and too nested:

(vec (map keypad (map keyword (map str word))))

Another way of writing this:

(vec (map (comp keypad keyword str) word))

Yet another:

(->> word
  (map str)
  (map keyword)
  (map keypad)
  vec)

Of course you can use characters as map keys, so this is much less verbose and also much easier to understand:

(defn keypad-numbers [word]
  "Generates a vector of digits from the letters in a word using the standard telephone keypad mapping of numbers and letters"
  (let [keypad {\a 2 \b 2 \c 2
                \d 3 \e 3 \f 3
                \g 4 \h 4 \i 4
                \j 5 \k 5 \l 5
                \m 6 \n 6 \o 6
                \p 7 \q 7 \r 7 \s 7
                \t 8 \u 8 \v 8
                \w 9 \x 9 \y 9 \z 9 }]
    (vec (map keypad word))))

Function combo-numbers

There is copy pasted code here:

(defn combo-numbers [combo-digits]
  "Generates a vector of combination numbers from a vector of combination digits"
  (let [a (+ (* 10 (combo-digits 0)) (combo-digits 1))
        b (+ (* 10 (combo-digits 2)) (combo-digits 3))
        c (+ (* 10 (combo-digits 4)) (combo-digits 5))]
    [a b c]))

It could be written like this instead:

(defn combo-numbers' [combo-digits]
  "Generates a vector of combination numbers from a vector of combination digits"
  (->> combo-digits
    (partition 2)
    (map #(+ (* (first %) 10) (second %)))
    vec))

Note combo-numbers' does not require combo-digits to be a vector anymore. It also can handle any even sized collection. For odd sized collections it just ignores the last element. Like in web-services, it is better to be lenient while accepting and strict when returning.

Function all-end-with?

Here, also, copy/pasted code is present:

(defn all-end-with? [numbers combo-digits]
  "Checks if the last digit of the combination's numbers all end with one of the provided numbers"
  (let [a (combo-digits 1)
        b (combo-digits 3)
        c (combo-digits 5)]
    (and
        (not (nil? (some #(= a % ) numbers)))
        (not (nil? (some #(= b % ) numbers)))
        (not (nil? (some #(= c % ) numbers))))))

This could be written like this instead:

(defn all-end-with?' [numbers combo-digits]
  "Checks if the last digit of the combination's numbers all end with one of the provided numbers"
  (let [a (combo-digits 1)
        b (combo-digits 3)
        c (combo-digits 5)
        p (set numbers)]
    (every? p [a b c])))

Note, in clojure :

  • nil is a falsy value.
  • Sets are predicates, that test if they contain the passed parameter.

Another problem with all-end-with? has a misleading name. it would be better it was run on combo-numbers instead of combo-digits:

(defn all-end-with?'' [numbers combo-numbers]
  "Checks if the last digit of the combination's numbers all end with one of the provided numbers"
  (->> combo-numbers
    (map #(mod % 10))
    (every? (set numbers))))

Note the concordance between the doc string provided, and how the code reads now.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

I'll leave the original code in place in the question. Here's the updated version taking all the feedback into consideration:

(ns com.sargentandgreenleaf.combination
  (:use [clojure.java.io :only [reader]]
        [clojure.string :only [join]]))

(defn abs [n] (max n (- n)))

(defn keypad-numbers [word]
  "Generates a sequence of digits from the letters in a word using the standard telephone keypad mapping of numbers and letters"
  (let [keypad {\a 2 \b 2 \c 2
                \d 3 \e 3 \f 3
                \g 4 \h 4 \i 4
                \j 5 \k 5 \l 5
                \m 6 \n 6 \o 6
                \p 7 \q 7 \r 7 \s 7
                \t 8 \u 8 \v 8
                \w 9 \x 9 \y 9 \z 9 }]
    (map keypad word)))

(defn all-end-with? [numbers combo]
  "Checks if the last digit of the combination's numbers all end with one of the provided numbers"
  (let [last-numbers (map #(mod % 10) combo)
        s (set numbers)]
    (every? s last-numbers)))

(defn ascending? [combo]
  "Checks if the numbers in the combination are ascending (e.g. 23 56 72)"
  (apply < combo))

(defn descending? [combo]
  "Checks if the numbers in the combination are descending (e.g. 72 56 23)"
  (apply > combo))

(defn has-margin? [margin combo]
  "Checks if the numbers in the combination are separated by a margin"
  (every? (fn [[n1 n2]] (> (abs (- n1 n2)) margin))
    (partition 2 1 combo)))

(defn taboo-last-number? [combo]
  "Checks if the last number in the combination is between 95 and 99, or 0 and 20"
  (let [last-number (last combo)]
    (or (<= last-number 20)
        (>= last-number 95))))

(defn valid-combination? [combo]
  "Checks that a combination is valid according to the rules in http://www.sargentandgreenleaf.com/pdf/book_mech_locks.pdf"
  (and (not (all-end-with? [0 5] combo))
       (not (ascending? combo))
       (not (descending? combo))
       (has-margin? 10 combo)
       (not (taboo-last-number? combo))))

(defn combo-numbers [combo-digits]
  "Generates a sequence of combination numbers from a collection of combination digits"
  (map (fn [[tens ones]] (+ (* 10 tens) ones))
    (partition 2 combo-digits)))

(defn run [fname]
  (with-open [rdr (reader fname)]
    (doseq [word (line-seq rdr)]
      (let [combo (combo-numbers (keypad-digits word))]
        (if (valid-combination? combo)
          (println (str word " - " (join "-" combo))))))))

(run  "./six-character-words.txt")
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Actually earlier version of with-lines is more readable. You can use let destructuring, instead to remove redundancy. And in the current version You can write just (str line " - " (clojure.string/join "-" combo)) instead. Also do not forget to check my answer;) \$\endgroup\$ – abuzittin gillifirca Nov 17 '14 at 13:50
  • \$\begingroup\$ Just updated my code to include your feedback. Thanks for the help! \$\endgroup\$ – erturne Nov 17 '14 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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