Re: String Manipulation Challenge
- From: "Thomas M. Hermann" <tmh.public@xxxxxxxxx>
- Date: Sun, 10 Jun 2007 03:14:06 -0000
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
.
- References:
- String Manipulation Challenge
- From: Waldo
- String Manipulation Challenge
- Prev by Date: Re: String Manipulation Challenge
- Next by Date: Re: String Manipulation Challenge
- Previous by thread: string manipulation challange
- Next by thread: Need help in naming a variable
- Index(es):
Relevant Pages
|
