The goal of this assignment is to write a Java program that arranges a list of words into separate lists of anagrams. Your program should be named “CPSC319S21A2″ and will be called from the command line as follows
$ java CPSC319S21A2 file
where file is a file containing a list of words to be sorted into anagrams and is read by the program through standard input. The number of words in the input is arbitrary. The program should print to standard output the lists of anagrams in the following way:
- all the words that are anagrams of each other are printed on one line of output
- exactly one space between words on the same line, and
- no other spaces.
For example, this input text file: car
mega bed stop game pots arc tops
Should yield the output text:
arc car
game mega pots stop tops bed
Note that the input can be large. Some test files will be available on the course website.
The Algorithms
You are required to use 1-D arrays and singly linked lists in your program to deal with the arbitrary number of words in the input as follows:
Step #1. The data from the input text file should be Step #2. LIST A may then be sorted (example): (It structured in a 1-D array of words (example): is not a must)
|
car |
|
mega |
|
bed |
|
stop |
|
game |
|
pots |
|
arc |
|
tops |
LIST A
1-D array of words
|
arc |
|
bed |
|
car |
|
game |
|
mega |
|
pots |
|
stop |
|
tops |
0 10
3 Input text file 4 5 6 7
X
2
1 2 3 4 5 6 7
Step #4. Traverse LIST B to generate the required output text format (refer to previous page).
Step #3. A new LIST B should then be created directly from LIST A (i.e., the sorted 1-D array of words, step #2) as follows (example):
|
0 arc car NULL |
|
LIST B 1-D array of singly linked lists LIST B is a 1-D array storing, at each array entry, a singly linked list of all the anagrams found in the sorted LIST A (step #2) – i.e., (arc, car), (game, mega), (pots, stop, tops) – as well as any remaining word(s) with no anagrams found in the sorted LIST A (step #2) – i.e., (bed). Note: all the words in each of the singly linked lists are stored in alphabetical order and subsequently stored at each array entry also in alphabetical order – e.g., note the first word at LIST B [0](arc, car), LIST B [1](bed), LIST B [2](game, mega), and LIST B [3](pots, stop, tops). This is achieved by structuring LIST B (i.e., both 1-D array and singly linked lists) directly from LIST A which is sorted already (i.e., step #2). |
arc car
bed game mega
pots stop tops
Output text
LIST A
Sorted 1-D array of words
Sorting is not mandatory. But it would make your output elegant and increase understanding.
Finding Anagrams: To determine if two words are anagrams is to sort the letters in both words. If the two sorted words are the same, then the original two words are anagrams. For example, array entries #5, #6, and #7 (i.e., “pots”, “stop”, and “tops”) from the sorted LIST A of words (i.e., step #2) are anagrams:
‘p’ ‘o’ ‘t’ ‘s’ Aftersorting ‘o’ ‘p’ ‘s’ ‘t’ 0 1 2 3 ⎯⎯⎯⎯⎯⎯⎯⎯⎯> 0 1 2 3
‘s’ ‘t’ ‘o’ ‘p’ Aftersorting ‘o’ ‘p’ ‘s’ ‘t’ 0 1 2 3 ⎯⎯⎯⎯⎯⎯⎯⎯⎯> 0 1 2 3
‘t’ ‘o’ ‘p’ ‘s’ Aftersorting ‘o’ ‘p’ ‘s’ ‘t’ 0 1 2 3 ⎯⎯⎯⎯⎯⎯⎯⎯⎯> 0 1 2 3
IMPORTANT: You can use Arrays or ArrayLists, However you should use your own implementation of singly linked lists. You may use our textbook, lecture and tutorial materials or other sources of information as guidance but be sure to cite them. Check with your TA/instructor if you are unsure.
Instructions
1. Write the program described above.
Hand-In (digitally to D2L dropbox)
- Your source code file that generates the output in the form requested. The README file should include description of which class begins execution of your submitted code. For example, “CPSC319S21A2.java” is my main class and should be executed.
- Include all of the above items in a zipped folder (standard ZIP) titled CPSC319S21A2-LASTNAME-ID.zip
before submission to the D2L dropbox for assignment 2.
Grading
Assignment grades will be base equally on the submitted components as described on grading summary
- Source code that does not compile or produces run-time errors will receive a grade of 0%.
- Code that produces incorrect output (Ex. wrong format of output) will be penalized appropriately.
