Assignment 09

Anagrams

Two words are anagrams if they contain precisely the same letters (with repetition). That is, the words are anagrams if the letters of one can be rearranged to form the other. For example, the words silent and listen are anagrams.

Your Task

For this assignment, you will write a program, Anagrams.java, that reads the words from a given text file and prints all sets of anagrams among the words in the file. For example, if the file contains the text: Listen, the cat act was silent. Stop at the spot past the post., your program should print:

1
2
3
4

  Found anagrams:
  - cat act
  - listen silent
  - stop spot post

Your program must also report (1) the largest set of words that are all anagrams of each other, and (2) the amount of time taken to find the anagrams. For example, here is the sample output generated my my solution on the text file words-short.txt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

  Found anagrams: 
  -  meat team 
  -  mean name 
  -  expect except 
  -  cloud could 
  -  how who 
  -  seat east 
  -  no on 
  -  sign sing 
  -  earth heart 
  -  salt last 
  -  horse shore 
  -  night thing 
  -  read dear 
  -  deal lead 
  -  these sheet 
  -  there three 
  -  note tone 
  -  stream master 
  -  form from 
  -  act cat 
  -  add dad 
  -  broad board 
  -  are ear 
  -  left felt 
  -  range anger 
  -  silent listen 
  -  was saw 
  -  now own 
  -  quite quiet 
  -  stop post spot 
  -  town wont 
  -  south shout 
  -  garden danger 
  -  race care 
  There are 34 sets of anagrams.
  That took 3ms
  Words with the most anagrams are:
    stop
    post
    spot

The order in which your program prints the sets of anagrams does not matter, but it must print all anagrams (and only anagrams). In running your program, the user should be able to specify which file is to be read from the command line. For example, your program should be compiled and run as follows:

1
2

  javac Anagrams.java
  java Anagrams words-short.txt

Suggestions & Resources

You may use any data structures that you wish to find anagrams. For efficiency’s sake, you might consider using Java’s built-in data structures. Below are links to some that might be useful to you. Note that these are links to interfaces, but each page also has links to the documentation for various classes implementing the interface.

Additionally, you might find some functionality in the Arrays class useful. For example, the class offers (static) methods for hashing and sorting arrays:

Note that since the methods are static, you can invoke them by calling, for example, Arrays.hashCode(someArray). You may also find the String documentation helfpul:

Code

Here are some file to get you started, as well as several texts to test your program on:

Or download everything as hw09.zip

What to Submit

Submit your Anagrams.java as well as any other files needed to run your program.

Evaluation

Your submission will receive a score out of 10 points, broken down as follows:

  • 10 points for Anagrams.java:
    • 5 points program compiles, runs, and produces the expected output
    • 3 code is well-organized and commented
    • 2 program is efficient—it should not take more than 1 second to find all anagrams in words-all.txt linked above.