Lisp 作为 Java 的替代品 (2000)

;; Peter Norvig - 来自 Erann Gat 的编程挑战：;; http://www.flownet.com/ron/papers/lisp-java/;;给定一个单词列表和一个电话号码列表，找出所有的方法；；每个电话号码都可以表示为一个单词列表。运行： (main "word-list-file-name" "phone-number-file-name")(defvar *dict* nil "一个将电话号码（整数）映射到输入字典中的单词列表的哈希表产生那个数字。")(defun main (&optional (dict "dict") (nums "nums") (dict-size 100)) "读取输入文件 DICT 并将其加载到 *dict*。然后对于 NUMS 中的每一行，根据翻译规则，将数字的所有翻译打印成单词序列。” (setf *dict* (load-dictionary dict dict-size)) (with-open-file (in nums) (loop for num = (read-line in nil) while num do (print-translations num (remove-if-not #'digit-char-p num)))))(defun print-translations (num numbers &optional (start 0)) words nil)) "将 NUM 的每个可能的翻译打印成一串单词。DIGITS 必须是删除非数字的 WORD。在递归调用中，START 是 DIGITS 中查找下一个单词的位置，而 WORDS 是为 (subseq DIGITS 0 START) 找到的单词列表。所以如果 START 到达 DI 的结尾GITS，然后我们在 WORDS 中有一个解决方案。否则，对于 DIGITS 的每个前缀，在字典中查找映射到前缀值的单词（增量计算为 N），并且对于每个这样的单词尝试通过递归调用扩展解决方案。有两个并发症：（1）规则说除了字典单词之外，您可以在输出中使用单个数字，但不能连续使用两个数字。另外（这看起来很傻）你不能在一个可以出现任何单词的地方有一个数字。我用变量 FOUND-WORD 处理这个问题；如果循环后为假，并且最近的单词不是数字，请尝试推送数字的递归调用。 (2) 另一个复杂之处是，将字符串映射到整数的显而易见的方法是将 R 映射到 2，将 ER 映射到 02，这当然与 2 是相同的整数。因此我们在每个数字前加一个 1，R 变为 12 并且ER 变成 102。" (if (>= start (length digits)) (format t "~a:~{ ~a~}~%" num (reverse words)) (let ((found-word nil) (n 1 )) ; 前导零问题（循环从下面开始的 i （长度数字） do (setf n (+ (* 10 n) (nth-digit digits i))) (loop for word in (gethash n *dict*) do (setf found-word t) (print-translations num numbers (+ 1 i) (cons word words)))) (when (and (not found-word) (not (numberp (first words)))) (print- translations num numbers (+ start 1) (cons (nth-digit numbers start) words)))))(defun load-dictionary (file size) "从单词文件中创建一个哈希表（每行一个）。需要一个初始哈希表大小的提示。每个键是一个单词的电话号码；每个值是具有该电话号码的单词列表。” ((table (make-hash-table :test #'eql :si ze size))) (with-open-file (in file) (loop for word = (read-line in nil) while word do (push word (gethash (word->number word) table)))) 表)) (defun word->number (word) "按照规则将一个单词（字符串）翻译成一个电话号码。" (let ((n 1)) ;前导零问题（循环从 0 下面（长度字）为 ch =（字符字 i）做（当（alpha-char-p ch）（setf n（+（* 10 n）（char->digit ch）） )))) n))(defun nth-digit (digits i) “数字字符串的第 i 个元素，为 0 到 9 的整数。” (- (char-code (char numbers i)) # .(char-code #\0)))(defun char->digit (ch) "根据电话号码规则将字符转换为数字。" (ecase (char-downcase ch) ((#\e) 0 ) ((#\j #\n #\q) 1) ((#\r #\w #\x) 2) ((#\d #\s #\y) 3) ((#\f #\ t) 4) ((#\a #\m) 5) ((#\c #\i #\v) 6) ((#\b #\k #\u) 7) ((#\l #\ o #\p) 8) ((#\g #\h #\z) 9)))