CS 14 - Anagrams

Due Sunday October 12th, 8pm

Your assignment is to write a program that reads in a dictionary of words from a text file, reads in a single word from the user, and then prints out all words in the dictionary that are anagrams of that word. Further, your program must execute completely within 1 second when executed on the server hill.cs.ucr.edu for all of our test cases, so an inefficient solution is unlikely to work.

Details

Your program needs to use file streams (more information here or here) to read in the file /usr/share/dict/words, the standard English dictionary under most Linux distributions. For up to 3% bonus credit you may add a command line flag to specify an alternate dictionary, but you must read in that dictionary as a default. If the preceding sentence doesn't make any sense to you, ask someone or Google for it.

You also must read in a single word from standard input (using cin). Upon reading in that word, print out all anagrams of the word that are found in the dictionary, in alphabetical order. No other output should be generated.

Downloads

A compiled binary sample of the program that you can test against can be found here

Sample input/output files (save to disk):
anagram1.in anagram1.out
anagram2.in anagram2.out
anagram3.in anagram3.out

These tests can be run against your program using standard Unix I/O redirection and the diff utility.

> ./anagram < anagram1.in | diff - anagram1.out
> ./anagram < anagram2.in | diff - anagram2.out
> ./anagram < anagram3.in | diff - anagram3.out

If any of these commands produce any output, your solution is incorrect.

Hints

Here we provide a relatively simple path toward implementing this program. Do note that we are not telling you how these pieces go together, and there is still a bit of thinking that you need to do to implement this on your own.

Write a function bool hasChar(string word, char c) that returns true if c appears in word.
Write a function void replaceChar(string& word, char c) that replaces the first instance (if any) of c in word with a non-alphabetic character like " ".
Write a function bool isAnagram(string word1, string word2) using hasChar and replaceChar

Bonus Credit

If your program runs in O(n lg n) time, you will receive 5% bonus credit. If your program runs in O(n) time, you will receive an additional 5% bonus credit (10% total.)