You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
52 lines
1.7 KiB
Common Lisp
52 lines
1.7 KiB
Common Lisp
;; CMUCL: $ time lisp -eval '(compile-file "add-a-gram.lisp")' -eval '(load "add-a-gram.x86f")' -eval '(run)' -eval '(quit)'
|
|
;; real 0m11.834s
|
|
;; Python: $ time ./addagram.py WORD.LST
|
|
;; real 0m43.589s
|
|
;; Perl: $ time perl addagram.pl WORD.LST
|
|
;; real 0m17.541s
|
|
|
|
(defvar *wordlist* nil)
|
|
|
|
(defun run ()
|
|
(let ((best-word ""))
|
|
(setq *wordlist* (make-hash-table :test 'equal))
|
|
(read-file "WORD.LST")
|
|
(maphash #'(lambda (sorted-word word)
|
|
(if (> (length word) (length best-word))
|
|
(if (add-a-gram-p sorted-word)
|
|
(setf best-word sorted-word)))) *wordlist*)
|
|
(show-result best-word)))
|
|
|
|
(defun read-file (arg-file-name)
|
|
(let ((line nil))
|
|
(with-open-file (stream arg-file-name :direction :input)
|
|
(loop while (setq line (read-line stream nil)) do
|
|
(unless (< (length line) 3)
|
|
(setf (gethash (sort-word line) *wordlist*) line))))))
|
|
|
|
(defun add-a-gram-p (sorted-word)
|
|
(let ((foo nil))
|
|
(cond ((= (length sorted-word) 3) (gethash sorted-word *wordlist*))
|
|
((null (gethash sorted-word *wordlist*)) nil)
|
|
(t (setf foo (remove-one-char sorted-word))
|
|
(loop until (or (null foo) (add-a-gram-p (car foo)))
|
|
do (setf foo (cdr foo)))
|
|
(car foo)))))
|
|
|
|
(defun remove-one-char (word)
|
|
(let ((foo nil))
|
|
(loop for k from 1 to (length word) do
|
|
(push (concatenate 'string
|
|
(subseq word 0 (1- k))
|
|
(subseq word k (length word))) foo))
|
|
foo))
|
|
|
|
(defun sort-word (word)
|
|
(sort (copy-seq word) #'char<))
|
|
|
|
(defun show-result (sorted-word)
|
|
(format t "~A~%" (gethash sorted-word *wordlist*))
|
|
(unless (= (length sorted-word) 3)
|
|
(show-result (add-a-gram-p sorted-word))))
|
|
|