{"id":201,"date":"2004-06-10T19:42:22","date_gmt":"2004-06-10T17:42:22","guid":{"rendered":"http:\/\/blogs.bl0rg.net\/neingeist-neu\/2004\/06\/10\/add-a-gram\/"},"modified":"2006-10-10T03:43:11","modified_gmt":"2006-10-10T01:43:11","slug":"add-a-gram","status":"publish","type":"post","link":"https:\/\/blogs.bl0rg.net\/neingeist\/2004\/06\/10\/add-a-gram\/","title":{"rendered":"Add-A-Gram"},"content":{"rendered":"

Another toy problem from the ITA software page<\/a> is the Add-A-Gram:<\/p>\n


\nAn “add-a-gram”
\nis a sequence of words formed by starting with a 3-letter word, adding
\na letter and rearranging to form a 4-letter word, and so on. For example,
\nhere are add-a-grams of the words “CREDENTIALS” and “ANACHRONISM”:<\/em><\/p>\n

ail + s =
\nsail + n =
\nnails + e = <\/em><\/p>\n

aliens + t =
\nsalient + r =
\nentrails + c =
\nclarinets + e =
\ninterlaces + d =
\nCREDENTIALS (length 11)<\/em><\/p>\n

(…) given the dictionary found
\nhere (1.66MB)<\/a>, what is the longest add-a-gram?
\n<\/em><\/p>\n

Running my code to get the longst add-a-gram is left as an exercise to the reader \ud83d\ude09 I also did some basic performance testing and compared the results
\nof my Lisp version to those of the versions on the site in
\nPerl<\/a>
\nand Python<\/a>. Looks like Lisp isn’t so slow after all. Timings and Lisp code follow:
\n<\/p>\n

;; CMUCL:       $ time lisp -eval '(compile-file \"add-a-gram.lisp\")' -eval '(load \"add-a-gram.x86f\")' -eval '(run)' -eval '(quit)'\r\n;;              real    0m11.834s\r\n;; Python:      $ time .\/addagram.py WORD.LST\r\n;;              real    0m43.589s\r\n;; Perl:        $ time perl addagram.pl WORD.LST\r\n\r\n;;              real    0m17.541s\r\n\r\n(defvar<\/a> *wordlist* nil)\r\n\r\n(defun<\/a> run ()\r\n(let<\/a> ((best-word \"\"))\r\n(setq<\/a> *wordlist* (make-hash-table<\/a> :test 'equal))\r\n(read-file \"WORD.LST\")\r\n(maphash<\/a> #'(lambda<\/a> (sorted-word word)\r\n(if<\/a> (><\/a> (length<\/a> word) (length<\/a> best-word))\r\n(if<\/a> (add-a-gram-p sorted-word)\r\n(setf<\/a> best-word sorted-word)))) *wordlist*)\r\n(show-result best-word)))\r\n\r\n(defun<\/a> read-file (arg-file-name)\r\n(let<\/a> ((line nil))\r\n(with-open-file<\/a> (stream<\/a> arg-file-name :direction :input)\r\n(loop<\/a> while (setq<\/a> line (read-line<\/a> stream nil)) do\r\n(unless<\/a> ( (<\/a>length<\/a> line) 3)\r\n(setf<\/a> (gethash<\/a> (sort-word line) *wordlist*) line))))))\r\n\r\n(defun<\/a> add-a-gram-p (sorted-word)\r\n(let<\/a> ((foo nil))\r\n(cond<\/a> ((=<\/a> (length<\/a> sorted-word) 3) (gethash<\/a> sorted-word *wordlist*))\r\n((null<\/a> (gethash<\/a> sorted-word *wordlist*)) nil)\r\n(t<\/a> (setf<\/a> foo (remove-one-char sorted-word))\r\n(loop<\/a> until (or<\/a> (null<\/a> foo) (add-a-gram-p (car<\/a> foo)))\r\ndo (setf<\/a> foo (cdr<\/a> foo)))\r\n(car<\/a> foo)))))\r\n\r\n(defun<\/a> remove-one-char (word)\r\n(let<\/a> ((foo nil))\r\n(loop<\/a> for k from 1 to (length<\/a> word) do\r\n(push<\/a> (concatenate<\/a> 'string\r\n(subseq<\/a> word 0 (1-<\/a> k))\r\n(subseq<\/a> word k (length<\/a> word))) foo))\r\nfoo))\r\n\r\n(defun<\/a> sort-word (word)\r\n(concatenate<\/a> 'string (sort<\/a> (coerce<\/a> word 'list) #'char<)))\r\n\r\n(defun<\/a> show-result (sorted-word)\r\n(cond<\/a> ((=<\/a> (length<\/a> sorted-word) 3)\r\n(format<\/a> t \"~A~%\" (gethash<\/a> sorted-word *wordlist*)) )\r\n(t<\/a>             (format<\/a> t \"~A~%\" (gethash<\/a> sorted-word *wordlist*))\r\n(show-result (add-a-gram-p sorted-word)))))<\/pre>\n","protected":false},"excerpt":{"rendered":"
Another toy problem from the ITA software page is the Add-A-Gram: An “add-a-gram” is a sequence of words formed by starting with a 3-letter word, adding a letter and rearranging to form a 4-letter word, and so on. For example, here are add-a-grams of the words “CREDENTIALS” and “ANACHRONISM”: ail + s = sail + […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[14],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts\/201"}],"collection":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/comments?post=201"}],"version-history":[{"count":0,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts\/201\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/media?parent=201"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/categories?post=201"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/tags?post=201"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}