Anagram

Growing up back in India, one of the Hollywood movies that I remember vividly is National Treasure. We rented the CD from the local shop, and I had to go to my uncle’s place to play the CD as we didn’t own a CD player yet. We only had a VCR player. In the movie there is a scene where Riley tries to guess the password based on the fingerprint marks on the touch pad. He enters all the characters and the computer gives him all the permutations of that word. Oh well, finally our Nicholas Cage saves the day as Abigail’s password wouldn’t be present in the dictionary, after all.

But that didn’t stop me from being fascinated with the little computer program that can chew out the various permutations of a word. I tried to write this program when I was doing my Bachelors, and having a lot of things on my mind then, I wasn’t able to go anywhere near solving it.

Today after 6 years, I came across a piece of text that that was one of my failed ideas in solving Anagram back from college days. I had a plan to go visit Hanging Lake near CO, which is a 3 hour ride from my place, and so I thought I would give the problem some more thought.

The ride was quite beautiful and the trek to Hanging lake was horrid. But it was worth it. I had 4 solid quiet hours to crack this little problem and as I didn’t have internet there, I didn’t have a dictionary.txt with me, so I had all my code skeleton ready to take an input from a txt file, and once I was back to my car and on the way back home, I downloaded a dictionary.txt file and fired up my little program.

Within 20 mins I fixed a couple of typos and had my program running. I think the only reason why I was able to come up with a solution now and not before may be because I’m now taking a stroll in the forest(?). I thought about the problem during my entire trek upwards, and here was my solution:

• Take a dictionary.txt and parse each word.
• When you parse each word, count all the characters and store it in an Array of size 26.
• Let’s call this dict.txt as it is a translation of dictionary.
• Here is where I had a problem, my program counted but with a complexity of n2. Then there was this cute 4 year old curious kid Alexandra who came around and asked me what I was doing. When I was explaining her what I was doing, I hit on a very simple method which I missed earlier ( code below, on Github )
• Now that you have a signature to word mapping file, write a normalization function that would build a hash map with signature as the key and words sharing the same signature as the values for the key.
• With this hash map, it’s very simple. When you are given a word, convert the word into it’s signature and look up the hash map for values. All the words linked to that hash map, are your anagrams.

The beauty of this solution is that, if you want to include new words or elements, you don’t have to modify anything in the solution. All you have to do is to run your index.js and normalize.js on the new data set. The dictionary data set that I had was pretty rudimentary so, my program doesn’t give you the anagrams which are plurals.

Usage : node anagram.js [word _ you _ want _ to _ find _ anagram_of ]

Github Link

Some pictures of the trip :