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 + n =
nails + e =
aliens + t =
salient + r =
entrails + c =
clarinets + e =
interlaces + d =
CREDENTIALS (length 11)		 mar + c =
cram + h =
march + s =
charms + o =
chromas + n =
monarchs + i =
harmonics + a =
maraschino + n =
ANACHRONISM (length 11)

Test your own credentials: given the dictionary found here (1.66MB), what is the longest add-a-gram?

Notes

  • We love the ITA Software careers page! They have all sort of monstrously difficult problems that applicants need to solve to apply for a job. This is one of them.
  • Acknowledgements: TAFFY DB - it's sort of handy. It was released just about the same time as we were starting this problem. We were hoping the sort and order by features would help, but they took too long, and we eventually gave up on using that part of Taffy. So ultimately, we regret using it as it complicates the solution quite a bit, without adding any value. A lesson learned.
  • Interactivity achieved through timers, and regular status updates. This part is actually realy nifty... Using timers to allow repaints in the browser, AND this avoids script time out errors in the browser. It's a bitch to do asynchronous recursion though; we had to implement our own call stack to store the state machine values between the timer events.
  • getElementsByName() is borked in IE7 - doesn't read the "name" attribute, it uses the "id" attribute, which is what we thought getElementByID() is meant to do... Took us a while to find that little bugger.