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