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.

Posted by programmingpraxis

Filed in Exercises

3 Comments »

3 Responses to “Words On A Telephone Keypad”

Jamie Hope said

January 13, 2017 at 4:46 PM

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).

(import (srfi 13))                      ; for string-join
(require 'regex)                        ; for regex-split

(define letters
  ["[+]" "1" "[abc]" "[def]" "[ghi]" "[jkl]" "[mno]" "[pqrs]" "[tuv]" "[wxyz]"])

(define (digits n::integer)
  (let loop ((ds '()) (n n))
    (if (< n 10)
        (cons n ds)
        (loop (cons (remainder n 10) ds) (div n 10)))))

(define (num->regex n::integer)
  (string-join (map letters (digits n)) ""))

(define (paragraph->lines s::String)
  (regex-split #/\n/ (*:trim s)))

(define (lookup n::integer)
  (paragraph->lines
   &`{grep -i "^&[(num->regex n)]$" /usr/share/dict/words}))

(for-each
 (lambda (arg)
   (format #t "~a: ~a~%" arg (lookup (string->number arg))))
 (cdr (command-line)))

$ kawa /tmp/words.scm 772947 228
772947: (praxis)
228: (Abu abu act Bat bat Cat cat)

matthew said

January 14, 2017 at 11:42 PM

@Jamie: Great idea! Here’s a node.js version:

const readline = require('readline');
const s = process.argv[2] || "43556";
const map = ['[+]','1','[abc]','[def]','[ghi]','[jkl]','[mno]','[pqrs]','[tuv]','[wxyz]'];
let restr = "";
for (const c of s.split('')) {
    restr += map[Number(c)] || "";
}
restr = "^" + restr + "$"; // Match whole line

const re = new RegExp(restr,"i"); // Case insensitive

const rl = readline.createInterface({
  input: process.stdin;
});

rl.on('line', function(line){
    if (re.test(line)) console.log(line);
})

$ cat /usr/share/dict/words | nodejs --harmony phone.js
hello
$ cat /usr/share/dict/words | nodejs --harmony phone.js 666
Mon
Ono
mom
moo
non

r. clayton said
January 17, 2017 at 9:31 AM
A solution in bash.

Programming Praxis