Telephone keyboard input recognition

from http://www.ieee.org/web/membership/students/scholarshipsawardscontests/xtremesamples.html

Can you do it /prog/? Here's the task:


 On a standard telephone, the numbers 1-9 can be used to correspond to a set of letters:

1: space            2: ABC     3: DEF       4: GHI               5: JKL       6: MNO

7: PQRS           8: TUV      9: WXYZ

Using the keypad, you can 'spell' words by entering the digits that correspond to each letter of the word. For example, 'words' is spelled 96737.

For this problem, we are given a dictionary file called with no more than 100,000 words, one per line, sorted in alphabetical order. Each word is comprised of no more than 18 characters, all lowercase letters from the phone keypad. Here is a (very short!) example of a dictionary file we will use in the examples:

Your program should read a string of digits (from 2 to 9, not using 1 as space) from the console and find the words in the dictionary whose spellings contain that series of consecutive digits anywhere within the word.

• If there are no matches, print the string 'No matches'
• If there is one match, print the matching word.
• If there are n>1 matches, print the string 'n matches:' followed by the matching

words, one per line.

NOTE: To make it easier to read the examples below, these are the 'spellings' of the words in words.txt, in digits:

cappuccino: 2277822466
chocolate: 246265283
cinnamon: 24662666
coffee: 263333
latte: 52883
vanilla: 8264554

examples

 contents of words.txt:

cappuccino
chocolate
cinnamon
coffee
latte
vanilla

program words.txt 22222
No matches

program words.txt 3333
coffee

program words.txt 626
2 matches:

chocolate
cinnamon

**NOTE**
obviously this is just for fun, OP (me) doesn't profit from your lisp solutions nor it's homework. It's from 2006 anyway.

I'm curious if you fags here can do it. some can, im sure.
I'll post my solution once I see a solution or two posted.

Any solution that makes a big string of enumerated digit sequences for each word and searches that string for the digit sequence is wrong. Clever, but wrong. Think about it.


(defvar *num-char-map* '("" " " "ABC" "DEF" "GHI" "JKL" "MNO" "PQRS" "TUV" "WXYZ"))

(defun num-string-match (num-str sample-str mapping)
  (let ((nl (length num-str))
        (sl (length sample-str)))
    (cond ((= 0 nl) t)
          ((> nl sl) nil)
          (t (let ((nc (subseq num-str 0 1))
                   (sc (string-upcase (subseq sample-str 0 1)))
                   (sr (subseq sample-str 1)))
               (let ((pos (position-if #'(lambda (str)
                                           (find (aref sc 0) str))
                                       mapping)))
                 (or (and pos
                          (= (parse-integer nc) pos)
                          (num-string-match (subseq num-str 1) sr mapping))
                     (num-string-match num-str sr mapping))))))))

(defun num-match-words (num-str words &optional (mapping *num-char-map*))
  (remove-if-not #'(lambda (w)
                     (num-string-match num-str w mapping))
                 words))

(defun read-words-file (word-file)
  (with-open-file (f word-file)
    (let ((words nil))
     (do ((l (read-line f nil :eof) (read-line f nil :eof)))
         ((eql l :eof) (nreverse words))
       (push l words)))))

(defun num-match-file (num-str word-file)
  (num-match-words num-str (read-words-file word-file)))

(defun telekey (file num)
  (let* ((words (num-match-file num file))
         (wordlen (length words)))
    (cond ((= 0 wordlen) (format t "No matches~%"))
          ((/= 1 wordlen) (format t "~d matches:~%~%" wordlen)))
    (dolist (w words)
      (format t "~a~%" w))))