Please refer to the addagram problem on this page. AnalysisGiven a 3 letter word, let us assume, we can find out the 4 letter words that are its addagrams. We can then expand this to a n letter word pointing to its (n + 1)th addagram. We can obviously model this as a directed graph where each word points to its addagrams. Further since there is no possibility of an addagram pointing to its possible source, this will be an acylic graph. Thus we have a directed acyclic graph representing the addagrams. AlgorithmThe problem then is of finding the ’longest path’ in the directed acyclic graph. In our case each edge will have a weight of 1.
First we build a hash table where key is the length of the word and values are the words of those length. Then we build the directed acylic graph such that each vertex is the word ’w’ and its neighbors are its addagrams obtained by searching through the hash table those words which are 1 more character in length than the given word ’w’.
0 Comments
Your comment will be posted after it is approved.
Leave a Reply. 
MeI am a polyglot software engineer specializing in shipping iOS and 3d scientific visualization applications. Archives
December 2011
Categories
All
