# James Michael Hare

...hare-brained ideas from the realm of software development...

### News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

## Solution to Little Puzzlers–“List All Anagrams in a Word”

This is the way I went about the "List all anagrams in a word” problems. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

### The Solution

There are many ways to tackle this problem.  Ultimately, the main goal of this problem was to be able to return all the anagram words of an input word as quickly as possible with little CPU overhead.  This pretty much eliminates attempting to perform all permutations of an input word, which can be a very expensive operation.

A major hint is in the fact we are given a dictionary.  Because we are given this dictionary we can prep it in any way we like when the program starts, and then the processing of any word input becomes simple.  Most dictionaries will easily fit within memory of modern computing hardware, so this should not be a major concern.

So, having the dictionary, we have all possible valid word anagrams already.  The only trick is how to get from the input to these words.

So let’s think, “what do all anagrams have in common?”  For example, the word “post” has “pots”, “stop”, “tops”, etc.  It may seem obvious, but all anagrams have the same letters.  Thus, if we can hash or organize these letters in a consistent way, we can store all anagrams under the same key.  In this way, we can apply the same hash/organization to the input word, immediately get the list of anagrams, and simply exclude the input word from the anagram list.

The simplest way to do this would simply be to sort the letters, this is a fairly simple operation in C#:

`   1: var key = string.Concat(word.ToLower().OrderBy(c => c));`

That would turn “post”, “pots”, etc. all into: “opst” which we can use as our key for our lookup.  Now, how to store them, you could download your own multidictionary, or create a Dictionary<string, List<string>>, but really C# already has one for you called a Lookup.  The Lookup stores a key to multiple values.

So first, let’s write a simple DAO for reading in our words from a file:

`   1: public class WordFileDao : IWordDao `
`   2: { `
`   3:     public string FileName { get; private set; }`
`   4:  `
`   5:     public WordFileDao(string fileName) `
`   6:     { `
`   7:         FileName = fileName; `
`   8:     }`
`   9:  `
`  10:     public IEnumerable<string> RetrieveWords() `
`  11:     {`
`  12:         // make sure to remove any accidental space and normalize to lower case`
`  13:         return File.ReadLines(FileName).Select(l => l.Trim().ToLower()); `
`  14:     } `
`  15: } `

Then, we can create an anagram finder to create the lookup on construction, and then find words on demand:

`   1: public class AnagramFinder `
`   2: { `
`   3:     private readonly ILookup<string, string> _anagramLookup; `
`   4:  `
`   5:     public AnagramFinder(IWordDao dao) `
`   6:     { `
`   7:         // construct the lookup at initialization using the`
`   8:         // dictionary words with the sorted letters as the key`
`   9:         _anagramLookup = dao.RetrieveWords().ToLookup( `
`  10:             k => string.Concat(k.OrderBy(c => c))); `
`  11:     }`
`  12:  `
`  13:     public IList<string> FindAnagrams(string word) `
`  14:     { `
`  15:         // at lookup time, sort the input word as the key,`
`  16:         // and return all words (minus the input word) in the sequence`
`  17:         string input = word.ToLower(); `
`  18:         string key = string.Concat(input.OrderBy(c => c));`
`  19:  `
`  20:         return _anagramLookup[key].Where(w => w != input).ToList(); `
`  21:     } `
`  22: }`

Notice the ToLookup() extension method (in System.Linq), this method creates an instance of Lookup from any IEnumerable<T> if you provide it a key generator and a value generator.  For the key generator, I’m returning the word in sorted, lowercase (for consistency).  For the value, I’m just lower-casing the word (again, for consistency).  This effectively creates the “dictionary of key to list of values” that, when you query using the “[…]” operator, will return an IEnumerable<T> of the values, or empty sequence if the key was not found.

And that’s it!  We have our anagram word finder which can lookup words quickly with only the cost of sorting the letters in a word, which is much less expensive (processing-wise) than attempting all permutations of the letters in a word.

### Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.

Print | posted on Tuesday, August 4, 2015 4:22 PM | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology CSharp ]