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")
> (sign "bat")
> (sign "cat")
> (sign "can't")
> (sign "PRAXIS")

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)
> (lookup 772947)
> (lookup 12345)

You can run the program at http://ideone.com/JiwqfI.

Pages: 1 2

3 Responses to “Words On A Telephone Keypad”

  1. Jamie Hope said

    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)
       &`{grep -i "^&[(num->regex n)]$" /usr/share/dict/words}))
     (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)

  2. matthew said

    @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
    $ cat /usr/share/dict/words | nodejs --harmony phone.js 666
  3. r. clayton said

    A solution in bash.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: