Hi all,
I've come across an interesting problem that I solved using Perl and
Ruby. However, as I'm trying to learn LISP, I'd love to know what
would be the most efficient way of solving it in LISP. The solutions
I've tried to write in LISP are very long and ugly and I'm sure there
is a nice, clean, and concise way of doing it.
The problem is the following: a user calls into an IVR to check his/
her account balance. In order to do so, s/he must enter his/her
account number. The account number may contain letters and numbers but
has no specific format nor specific length. It's all arbitrary. So,
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?
Thanks
Waldo wrote:
> The problem is the following: a user calls into an IVR to check his/
> her account balance. In order to do so, s/he must enter his/her
> account number. The account number may contain letters and numbers but
> has no specific format nor specific length. It's all arbitrary. So,
> 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))
On Jun 9, 9:33 am, Waldo <····@infoway.net> wrote:
> Hi all,
>
> I've come across an interesting problem that I solved using Perl and
> Ruby. However, as I'm trying to learn LISP, I'd love to know what
> would be the most efficient way of solving it in LISP. The solutions
> I've tried to write in LISP are very long and ugly and I'm sure there
> is a nice, clean, and concise way of doing it.
>
> The problem is the following: a user calls into an IVR to check his/
> her account balance. In order to do so, s/he must enter his/her
> account number. The account number may contain letters and numbers but
> has no specific format nor specific length. It's all arbitrary. So,
> 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?
>
> Thanks
This requires CL-ITERATE, and an appropriate use declaration in your
package.
(defun num->letters (num)
(ecase num
(#\2 '(#\a #\b #\c))
(#\3 '(#\d #\e #\f))
(#\4 '(#\g #\h #\i))
(#\5 '(#\j #\k #\l))
(#\6 '(#\m #\n #\o))
(#\7 '(#\p #\q #\r #\s))
(#\8 '(#\t #\u #\v))
(#\9 '(#\w #\x #\y #\z))))
(defun permute (pfx rest)
(if (string= rest "")
(list pfx)
(if (eql (char rest 0) #\*)
(iter (for char in (num->letters (char rest 1)))
(appending (permute (format nil "~A~A" pfx char) (subseq rest 2))))
(permute (format nil "~A~A" pfx (char rest 0)) (subseq rest 1)))))
(defun possibilities (input) (permute "" input))
Waldo <·····@infoway.net> writes:
> I've come across an interesting problem that I solved using Perl and
> Ruby. However, as I'm trying to learn LISP, I'd love to know what
> would be the most efficient way of solving it in LISP. The solutions
> I've tried to write in LISP are very long and ugly and I'm sure
> there is a nice, clean, and concise way of doing it.
Are you more interested in efficiency or nice- clean- and conciseness?
> 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?
To me it seems natural and relatively easy to write this as a nested
iteration that accumulates characters, but there are other approaches.
If you're interested in writing it yourself, here are a couple of
suggestions:
* There are a number of equally acceptable ways to traverse small
input strings character by character: you can apply a function to
each character with MAP, or explode them into lists using COERCE and
then traverse the characters with a MAPC/MAPCAR/MAPLIST or with a DO
or DOLIST, or iterate over the characters' indices with DOTIMES or
LOOP, or make a string-input-stream and use READ-CHAR/PEEK-CHAR.
One or more of those should be useful.
* For accumulating arbitrary-sized but small collections, lists are
pretty good. You can convert a list all of whose elements are
characters into a string conveniently with COERCE. Alternatively,
you could use vectors with fill pointers to accumulate intermediate
results, though I think that this would be somewhat cumbersome.
Hope that helps,
RmK
On 9 Jun, 14:33, Waldo <····@infoway.net> wrote:
> Hi all,
>
> I've come across an interesting problem that I solved using Perl and
> Ruby. However, as I'm trying to learn LISP, I'd love to know what
> would be the most efficient way of solving it in LISP. The solutions
> I've tried to write in LISP are very long and ugly and I'm sure there
> is a nice, clean, and concise way of doing it.
>
> The problem is the following: a user calls into an IVR to check his/
> her account balance. In order to do so, s/he must enter his/her
> account number. The account number may contain letters and numbers but
> has no specific format nor specific length. It's all arbitrary. So,
> 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?
>
> Thanks
The efficient way is to actually solve a different problem, and
convert all the accounts to their corresponding numbers and store them
in a list in a hash table*, which you key into using these numbers.
A more fun way is to use a set cross product:
CL-USER> (defun cross (list1 list2)
(mapcan (lambda(x)
(mapcan (lambda(y)
(cons x y)) list2)) list1))
CROSS
CL-USER> (cross '(a b) '((1)(2)))
((A 1) (A 2) (B 1) (B 2))
and push it recursively down your list of numbers.
(defun look-up (list) ;Untested
(if (char= (first list) #\*)
(cross (star (second list)) (look-up (cddr list))
(cross (list (first list)) (look-up (rest list))))
and then check for membership.
*or not if there won't be collisions.
Chris Russell <·····················@gmail.com> writes:
> The efficient way is to actually solve a different problem,
This can quite often be the case, but it can be difficult to actually
notice when you are up to your ears in the original problem. Thanks for
pointing this out.
--
Thomas A. Russ, USC/Information Sciences Institute
On Jun 9, 9:33 am, Waldo <····@infoway.net> wrote:
> Hi all,
>
> I've come across an interesting problem that I solved using Perl and
> Ruby. However, as I'm trying to learn LISP, I'd love to know what
> would be the most efficient way of solving it in LISP. The solutions
> I've tried to write in LISP are very long and ugly and I'm sure there
> is a nice, clean, and concise way of doing it.
>
> The problem is the following: a user calls into an IVR to check his/
> her account balance. In order to do so, s/he must enter his/her
> account number. The account number may contain letters and numbers but
> has no specific format nor specific length. It's all arbitrary. So,
> 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?
>
> Thanks
Posted this earlier, but it seems to have disappeared. Others have
presented some nice ideas. Here's a different approach. It parses
the key string into a list of sets of admissible characters, then
reduces the list with a Cartesian cross product operator.
(defun parse (key-string)
(do ((result nil) ; result list accumulator
(i 0 (1+ i)) ; string index
(len (length key-string))) ; iteration limit
((= i len) (nreverse result))
(case (char key-string i)
(#\* (incf i) ;; translate the escape
(push (ecase (char key-string i)
(#\2 '(#\A #\B #\C))
(#\3 '(#\D #\E #\F))
(#\4 '(#\G #\H #\I))
(#\5 '(#\J #\K #\L))
(#\6 '(#\M #\N #\O))
(#\7 '(#\P #\Q #\R #\S))
(#\8 '(#\T #\U #\V))
(#\9 '(#\W #\X #\Y #\Z)))
result))
(t (push (list (char key-string i))
result)))))
(defun cross-string-list-with-char (string-list char)
(mapcar #'(lambda (s) (concatenate 'string s (string char)))
string-list))
(defun cross-string-list-with-char-list (string-list char-list)
(mapcan #'(lambda (c) (cross-string-list-with-char string-list c))
char-list))
(defun string-possibilities (key-string)
(reduce #'cross-string-list-with-char-list (parse key-string)
:initial-value '("")))
On Jun 9, 10:09 pm, Gene <············@gmail.com> wrote:
> Posted this earlier, but it seems to have disappeared. Others have
> presented some nice ideas. Here's a different approach. It parses
> the key string into a list of sets of admissible characters, then
> reduces the list with a Cartesian cross product operator.
I wish the original post had worked, it would have saved me the time
and embarrassment of posting my solution. This solution is excellent.
Regards,
Tom H.
Hello again,
Well, I just want to extend my sincere thanks to everyone. This has
been more than educational for me and opened up more of my mind to the
power of LISP and how things can be done correctly in different ways.
Thank you again.
On Jun 9, 11:09 pm, Gene <············@gmail.com> wrote:
> On Jun 9, 9:33 am, Waldo <····@infoway.net> wrote:
>
> > Hi all,
>
> > I've come across an interesting problem that I solved using Perl and
> > Ruby. However, as I'm trying to learn LISP, I'd love to know what
> > would be the most efficient way of solving it in LISP. The solutions
> > I've tried to write in LISP are very long and ugly and I'm sure there
> > is a nice, clean, and concise way of doing it.
>
> > The problem is the following: a user calls into an IVR to check his/
> > her account balance. In order to do so, s/he must enter his/her
> > account number. The account number may contain letters and numbers but
> > has no specific format nor specific length. It's all arbitrary. So,
> > 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?
>
> > Thanks
>
> Posted this earlier, but it seems to have disappeared. Others have
> presented some nice ideas. Here's a different approach. It parses
> the key string into a list of sets of admissible characters, then
> reduces the list with a Cartesian cross product operator.
>
> (defun parse (key-string)
> (do ((result nil) ; result list accumulator
> (i 0 (1+ i)) ; string index
> (len (length key-string))) ; iteration limit
> ((= i len) (nreverse result))
> (case (char key-string i)
> (#\* (incf i) ;; translate the escape
> (push (ecase (char key-string i)
> (#\2 '(#\A #\B #\C))
> (#\3 '(#\D #\E #\F))
> (#\4 '(#\G #\H #\I))
> (#\5 '(#\J #\K #\L))
> (#\6 '(#\M #\N #\O))
> (#\7 '(#\P #\Q #\R #\S))
> (#\8 '(#\T #\U #\V))
> (#\9 '(#\W #\X #\Y #\Z)))
> result))
> (t (push (list (char key-string i))
> result)))))
>
> (defun cross-string-list-with-char (string-list char)
> (mapcar #'(lambda (s) (concatenate 'string s (string char)))
> string-list))
>
> (defun cross-string-list-with-char-list (string-list char-list)
> (mapcan #'(lambda (c) (cross-string-list-with-char string-list c))
> char-list))
>
> (defun string-possibilities (key-string)
> (reduce #'cross-string-list-with-char-list (parse key-string)
> :initial-value '("")))- Hide quoted text -
I learned CL a long time ago -- before my implementation even had the
extended (loop ... ) construct! Haven't touched it since then. I did
this little example for old times' sake.
The extended loop gives a much nicer version of (parse). a difference
is that the original version will die on a trailing *. This silently
ignores.
(defun parse (key-string)
(loop for prev-key = nil then key
for key across key-string
if (eql prev-key #\*) collect (key->letters key)
else unless (eql key #\*) collect (list key)
end))
(defun key->letters (key)
(ecase key
(#\2 '(#\A #\B #\C))
(#\3 '(#\D #\E #\F))
(#\4 '(#\G #\H #\I))
(#\5 '(#\J #\K #\L))
(#\6 '(#\M #\N #\O))
(#\7 '(#\P #\Q #\R #\S))
(#\8 '(#\T #\U #\V))
(#\9 '(#\W #\X #\Y #\Z))))
On Thu, 14 Jun 2007 05:01:23 +0200, Gene <············@gmail.com> wrote:
> The extended loop gives a much nicer version of (parse). a difference
> is that the original version will die on a trailing *. This silently
> ignores.
>
> (defun parse (key-string)
> (loop for prev-key = nil then key
> for key across key-string
> if (eql prev-key #\*) collect (key->letters key)
> else unless (eql key #\*) collect (list key)
> end))
>
> (defun key->letters (key)
> (ecase key
> (#\2 '(#\A #\B #\C))
> (#\3 '(#\D #\E #\F))
> (#\4 '(#\G #\H #\I))
> (#\5 '(#\J #\K #\L))
> (#\6 '(#\M #\N #\O))
> (#\7 '(#\P #\Q #\R #\S))
> (#\8 '(#\T #\U #\V))
> (#\9 '(#\W #\X #\Y #\Z))))
>
>
This version uses the iterate macro and generate.
Also note that all the processing is done on lists with a coerce
translating back and fourth.
(defpackage :my-user (:use :cl :iterate)
(in-package :my-user)
(defun parse (key-list)
(iter
(generate char in key-list)
(next char)
(if* (char= char #\*)
:then
(next char)
(collect (ecase char
(#\2 '(#\A #\B #\C))
(#\3 '(#\D #\E #\F))
(#\4 '(#\G #\H #\I))
(#\5 '(#\J #\K #\L))
(#\6 '(#\M #\N #\O))
(#\7 '(#\P #\Q #\R #\S))
(#\8 '(#\T #\U #\V))
(#\9 '(#\W #\X #\Y #\Z))))
:else
(collect char))))
;; Note that for efficency I use push in cross with makes every sublist
come out in reverse order
;; Four cases to consider (Form: accumulated element -> result)
;; A. element is a cons (do a set cross product)
;; 1. nil (A B C) --> ((A) (B) (C))
;; 2. ((A 1) (B 1)) (C D) -> ((C A 1) (C B 1) (D A 1) (D B 1))
;; B. element is a atom
;; 1. nil 1 -> ((1))
;; 2. ((A 1) (B 1)) 2 -> ((2 A 1) (2 B 1))
(defun cross (accumulated element)
(if (consp element)
(if (null accumulated)
(mapcar (lambda (e) (list e)) element)
(mapcan (lambda (e)
(mapcar (lambda (a)
(push e a))
accumulated))
element))
(if (null accumulated)
(list (list element))
(mapcar (lambda (sublis)
(push element sublis))
accumulated))))
(defun expand (list)
(mapcar (lambda (e) (reverse e))
(reduce #'cross list :initial-value nil)))
(defun string-possibilities (key-string)
(mapcar (lambda (a) (coerce a 'string))
(expand (parse (coerce key-string 'list)))))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
The solution below works. I haven't profiled it, but I convert the
string to a list, generate all possible combinations resulting in a
multi-dimensional list and finally compress that multi-dimensional
list back to a list of strings. Obviously, this is not the most
efficient approach. I thought about working from a hash table as
suggested by Chris Russell, but didn't think that that was in the
spirit of the question.
Converting the string to a list back to a list of strings aside, the
code below is indicative of what my first cuts at a program are like
and why programming in a lisp environment is productive and enjoyable.
I broke the problem down into manageable units and interactively
tested as I went. Now that I have something working, areas of
improvement will become obvious, both through using the code and
profiling. Maybe this kludge is sufficient for my problem and I don't
need to waste time on improving performance.
Lisp environments support this approach better than anything else to
which I have been exposed.
Cheers,
Tom H.
;;; Courtesy of D. Herring
(defun letters (entry)
"International Standard as per http://dialabc.com/motion/keypads.html"
(case entry
(#\2 '(#\a #\b #\c))
(#\3 '(#\d #\e #\f))
(#\4 '(#\g #\h #\i))
(#\5 '(#\j #\k #\l))
(#\6 '(#\m #\n #\o))
(#\7 '(#\p #\q #\r #\s))
(#\8 '(#\t #\u #\v))
(#\9 '(#\w #\x #\y #\z))
(#\1 (signal :no-letter-assigned))
(t (signal :not-a-number))))
(defun replace-asterisk (entry-list &optional result-list)
"Replace the asterisk and next numeric character with the list
of corresponding alpha characters."
(let ((entry (car entry-list)))
(if (null entry)
(reverse result-list)
(case entry
(#\* (replace-asterisk (cddr entry-list)
(push (letters (second entry-list))
result-list)))
(t (replace-asterisk (cdr entry-list)
(push entry result-list)))))))
(defun expand-list (entry-list &optional result-list)
"Generate all possible accounts."
(let ((entry (car entry-list)))
(if (null entry)
(reverse result-list)
(typecase entry
(list (mapcar
(lambda (sub-entry)
(expand-list (cdr entry-list)
(cons sub-entry result-list)))
entry))
(atom (expand-list (cdr entry-list)
(push entry result-list)))
(t (signal :got-nil))))))
(defun compress-accounts (account-list)
"Compress multi-dimensional list of accounts to a list of strings."
(let ((account (car account-list)))
(unless (null account)
(typecase account
(list (concatenate 'list
(compress-accounts account)
(compress-accounts (cdr account-list))))
(standard-char (cons (concatenate 'string account-list) nil))
(t (signal :no-account))))))
(defun get-accounts (keypad-entry)
"Top level function."
(compress-accounts ; Compress to list of strings.
(expand-list ; Permutation
(replace-asterisk ; *number -> characters
(concatenate 'list keypad-entry))))) ; String -> list