D. Herring wrote:

> > the instructions say that the caller should use the digits on the
> > phone keypad to enter numbers and letters. However, each letter must
> > be preceded with an asterisk.
> >
> > So, for example, if my account number is "1234", I would simply enter
> > "1" "2" "3" "4". If my account number was G3W70, I would enter "*" "4"
> > "3" "*" "9" "7" "0".
> >
> > Now, when searching for the account in the system, the system should
> > search for all possible matches and so the account entered into the
> > IVR, would need to be converted to an list of account numbers.
> >
> > So, if the caller entered 1234, the possible account numbers to search
> > is (1234). However, if the caller entered *43*970, the possible
> > account numbers to search is (G3W70, H3W70, I3W70, G3X70, H3X70,
> > I3X70, G3Y70, H3Y70, I3Y70, G3Z70, H3Z70, I3Z70).
> >
> > So, the question is: how to efficient transform the user's input into
> > a list of possible matches by expanding the digits into the
> > corresponding letters (1=1, 2=A|B|C, 3=D|E|F, 4=GHI, 5=JKL, 6=MNO,
> > 7=PQRS, 8=TUV, 9=WXYZ, 0=0) and doing all corresponding combinations
> > of those digits/letters to come up with all strings?
>
> Here's a first stab:
>
> (defun letters (number)
> "North American Classic as per http://dialabc.com/motion/keypads.html"
> (case number
> (#\1 (signal :no-letter-assigned))
> (#\2 '(#\a #\b #\c))
> (#\3 '(#\d #\e #\f))
> (#\4 '(#\g #\h #\i))
> (#\5 '(#\j #\k #\l))
> (#\6 '(#\m #\n))
> (#\7 '(#\p #\r #\s))
> (#\8 '(#\t #\u #\v))
> (#\9 '(#\w #\x #\y))
> (t (signal :not-a-number))))
>
> (defun translate (keys)
> "translate a string of keystrokes into all possible accounts"
> (let ((accounts (list ""))
> (escape nil))
> (dotimes (n (length keys))
> (let ((k (char keys n)))
> (if escape
> (progn
> (let ((tmp (list)))
> (dolist (a accounts)
> (dolist (l (letters k))
> (push (concatenate 'string
> a (string l))
> tmp)))
> (setf accounts tmp))
> (setf escape nil))
> (cond
> ((digit-char-p k)
> (setf accounts
> (mapcar
> (lambda (a)
> (concatenate 'string
> a
> (string k)))
> accounts)))
> ((eql k #\*)
> (setf escape t))
> (t (signal :unhandled-key k))))))
> accounts))

newLISP

(define (cartesian-multiply cartesian.lists cartesian.func (cartesian.built '()))
(if (null? cartesian.lists)
(cartesian.func (reverse cartesian.built))
(dolist (x (first cartesian.lists))
(cartesian-multiply (rest cartesian.lists) cartesian.func
(cons x cartesian.built)))))

(define (cartesian-product lists)
(if (null? lists)
'(())
(let (subproduct (cartesian-product (rest lists)))
(apply append
(map
(lambda (x) (map (lambda (xs) (cons x xs)) subproduct))
(first lists))))))

(define (num->letters num)
(explode
(case num
(2 "ABC")
(3 "DEF")
(4 "GHI")
(5 "JKL")
(6 "MNO")
(7 "PQRS")
(8 "TUV")
(9 "WXYZ"))))

(define (translate str)
(map join
(cartesian-product
(map
(fn (x) (if (= 2 (length x))
(num->letters (int (x 1)))
(list x)))
(find-all {\*?\d} str)))))

(translate "*43*970")

("G3W70" "G3X70" "G3Y70" "G3Z70" "H3W70" "H3X70" "H3Y70" "H3Z70"
"I3W70" "I3X70" "I3Y70" "I3Z70")