Re: String Manipulation Challenge

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