Words On A Telephone Keypad
January 13, 2017
We begin with a function that computes the signature of a word, ignoring non-letters:
(define (sign str) ; telephone keyboard A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (define keys (vector 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 9 9 9 9)) (define (lookup c) (vector-ref keys (- (char->integer c) 65))) (undigits (map lookup (filter char-alphabetic? (string->list (string-upcase str))))))
> (sign "act") 228 > (sign "bat") 228 > (sign "cat") 228 > (sign "can't") 2268 > (sign "PRAXIS") 772947
We use a hash table to store the words; the insert
function adds a word to a list of words with the same signature, and the lookup
function returns a possibly-empty list of words with the requested signature:
(define table (make-hash (lambda (x) x) = (list) 997)) (define (insert word) (table 'update! (sign word) (lambda (key words) (cons word words)) (list word))) (define (lookup signature) (sort string<? (table 'lookup signature)))
Building a table from a list of words is easy, just say (for-each insert words)
. To build a table from a file containing one word per line, using our library for processing text files, say:
(for-each-port read-line insert file-name)
Once the table is built, you can query it like this:
> (lookup 228) ("act" "bat" "cat") > (lookup 2268) ("can't") > (lookup 772947) ("praxis") > (lookup 12345) ()
You can run the program at http://ideone.com/JiwqfI.
Here’s one that goes the other way, turning the provided number into a string regex, and then using grep to search /usr/share/dict/words (via a Kawa process quasi-literal).
$ kawa /tmp/words.scm 772947 228
772947: (praxis)
228: (Abu abu act Bat bat Cat cat)
@Jamie: Great idea! Here’s a node.js version:
A solution in bash.