Path: ...!feeds.phibee-telecom.net!3.eu.feeder.erje.net!feeder.erje.net!news.in-chemnitz.de!news.swapon.de!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "B. Pym" <Nobody447095@here-nor-there.org>
Newsgroups: comp.lang.lisp
Subject: Re: String Manipulation Challenge
Date: Thu, 8 Aug 2024 18:57:11 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 116
Message-ID: <v934dj$67j8$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Thu, 08 Aug 2024 20:57:12 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="623536926260db1f505ba92f19951445";
	logging-data="204392"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/OlpIDJTdP7EbmwezkxDSo"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:NkMt/sbaq76xy2i7taI+B8su67g=
Bytes: 4873

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