Homework Assignment 6 Solution

    • Assignment Policies

Under absolutely no circumstances code can be exchanged between students.

Excerpts of code presented in class can be used.

Assignments from previous offerings of the course must not be re-used. Viola-tions will be penalized appropriately.

Late Policy.    Check the course syllabus for the late submission policy.

    • Assignment

For this assignment, you will compute the list of words in a given dictionary that has the most number of anagrams. An anagram is word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, “rail safety” and “fairy tales” are anagrams. In this assignment, to simplify matters, we will focus on anagrams of words formed from letters only. For example, here is a list of 15 anagrams of the word “alerts”, including “alerts” itself, take from the dictionary:

alerts, alters, artels, estral, laster,

lastre, rastle, ratels, relast, resalt,

salter, slater, staler, stelar, talers

This assignment requires the class Anagrams. We next describe the class through the following UML diagram:













1


Anagrams

final Integer[] primes;

Map<Character,Integer> letterTable;

Map<Long,ArrayList<String>> anagramTable;

public Anagrams ()

private void buildLetterTable()

private void addWord(String s)

private Long myHashCode(String s)

public void processFile(String s) throws IOException

private ArrayList<Map.Entry<Long,ArrayList<String>>> getMaxEntries()

public static void main(String[] args)

The constant primes should be initialized to an array consisting of the first 26 prime numbers:

{2,  3,  5,  7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  53,  59,  61,

    • 67,  71,  73,  79,  83,  89,  97,  101};


It will be used to set up the letterTable, a hash table that will associate each letter in the alphabet with a prime number. More precisely, it will associate “a” with 2, “b” with 3, “c” with 5, and so on.

The instance variable anagramTable will hold the main working hash table. Each entry in this hash table has the following format:

Key (of type Long): the hash code of the word. It is important that this hash be the same for all anagrams of a word. The type Long is a 64-bit two’s complement integer. More details on how to produce this key will be given below.

Value (of type ArrayList<String>): a list of the words seen up until now that have Key as hash code. Note that all the strings in this list are anagrams.

We now describe each of the methods.

    • Method processFile

The main method is processFile which receives the name of a text file containing words, one per line, and builds the hash table anagramTable. For that it uses the addWord method. The implementation of this method is provided for you:

private    void    p r o c e s s F i l e ( String  s )  throws    I O E x c e p t i o n  {

    • F i l e I n p u t S t r e a m  fstream  =  new  F i l e I n p u t S t r e a m ( s );

B u f f e r e d R e a d e r    br  =  new    B u f f e r e d R e a d e r ( new    I n p u t S t r e a m R e a d e r ( fstream ));

    • String  strLine ;

while    (( strLine  =  br . readLine ())  !=  null )    {

    • this . addWord ( strLine );

}

    • br . close ();

}




2

    • Method buildLetterTable()

This method should be invoked by the constructor for the class Anagrams and should build the hash table letterTable which consists of the following entries:


{ a =2 ,
b =3 ,  c =5 ,  d =7 ,  e =11 ,  f =13 ,  g =17 ,  h =19 ,  i =23 ,  j =29 ,  k =31 ,  l =37 ,
2
m =41 ,
n =43 ,
o =47 ,  p =53 ,  q =59 ,  r =61 ,  s =67 ,  t =71 ,  u =73 ,  v =79 ,  w =83 ,

x =89 ,
y =97 ,
z =101}

This table is to be used in myHashCode, described next, for constructing the hash code of strings.

    • Method myHashCode

This method, given a string s, should compute its hash code. A requirement for myHashCode is that all the anagrams of a word should receive the same hash code. With that aim, you should resort to the fundamental theorem of arithmetic. The fundamental theorem of arithmetic), also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 0 either is prime itself or is the product of a unique combination of prime numbers.

Every integer n    0 can be expressed as a product of prime numbers:    n =
p 1 p 2 : : : p n .
1    2    n

As an example, the words “alerts” and “alters” should both receive the key 2.36204078E8, if we follow the encoding of letters given above.

    • Method addWord

This method should compute the hash code of the string s passed as argument, and should add this word to the hash table anagramTable.

    • Method getMaxEntries

This method should return the entries in the anagramTable that have the largest number of anagrams. It returns a list of them since there ay be more than one list of anagrams with a maximal size. It will be called by the main method, whose code is described and supplied below.

    • Method main

The main method will read all the strings in a file, place them in the hash table of anagrams and then iterate over the hash table to report which words have the largest number of anagrams. Note that it refers to a file called words_alpha.txt. This file contains a dictionary of words; instructions on how to obtain it are given below.

Here is the code for the main method:


3


public    static    void    main ( String []  args )  {

    • Anagrams  a  =  new  Anagrams ();


    • final  long  s ta r tT im e  =  System . nanoTime ();

try  {

    • a . p r o c e s s F i l e ( " w o r d s _ a l p h a . txt" );

}  catch  ( I O E x c e p t i o n  e1 )  {

    • e1 . p r i n t S t a c k T r a c e ();

}

    10 ArrayList < Map . Entry < Long , ArrayList < String > > >  m a x E n t r i e s  =  a . g e t M a x E n t r i e s ();

final    long    e s t i m a t e d T i m e  =  System . nanoTime ()  -  s t ar tT i me ;

    12 final  double  seconds  =  (( double )  e s t i m a t e d T i m e / 1 0 0 0 0 0 0 0 0 0 ) ;

System . out . println ( " Time :  "+  seconds );

    14 System . out . println ( " List  of  max  anagrams :  "+  m a x E n t r i e s );

}


Here is the expected output of your solution (the elapsed time may vary):

    • Elapsed  Time :  0 . 6 8 9 1 3 5 7 6 7

Key  of  max  anagrams :  23 62 0 40 7 8

    • List  of  max  anagrams :  [ alerts ,  alters ,  artels ,  estral ,  laster ,  lastre ,

rastle ,  ratels ,  relast ,  resalt ,  salter ,  slater ,  staler ,  stelar ,  talers ]

    • Length  of  list  of  max  anagrams :  15



    • Testing Your Solution

In order to test your solution you are provided with a dictionary (words_alpha.txt) that has

370099 words. You may download this file from this link:

https://github.com/dwyl/english-words/blob/master/words_alpha.txt

Place it in the folder where your project is located (the same folder where the bin and src folders are).

10    Submission instructions

Please submit a zip file containing the file Anagrams.java on Canvas. The main method of the class Anagrams.java should include your tests. No report is required. Some further guidelines:

Use JavaDoc to comment your code. Check the arguments of methods.













4