The Assignment

You do not get a starter file. You must write it completely from scratch.

There is NO PARTIAL CREDIT ON OUTPUT.

Your program should take two command args: a dictionary file and a jumbles file. For each jumbled word you must find all the matching dictionary words and print them after the jumbled word in the line.

Here is the dictionary.txt and jumbles.txt I will test with.

Here is a tiny version of each input that you should test with until you are sure your code is correct: tinyDictionary.txt and tinyJumbles.txt and correct output for it: tinyCorrectOuput.txt.

Here is the correct execution command and output from a sample run of your program YOUR OUTPUT MUST MATCH EXACTLY. Notice the list of jumbles words is sorted vertically and the matching dictionary words that come after are sorted left to right.

java Project4 dictionary.txt jumbles.txt addej jaded ahicryrhe hierarchy alvan naval annaab banana baltoc cobalt braney nearby celer creel couph pouch cukklen knuckle dica acid cadi caid dobeny beyond dobol blood dufil fluid dupled puddle eslyep sleepy ettniner renitent ettorp potter genjal jangle gluhc gulch hartox thorax hoybis boyish hucnah haunch iddec diced irrpo prior kutbec bucket lappor poplar lasia alias laurib burial lubly bully meefal female milit limit mopsie impose mycall calmly nekel kneel nokte token noper prone nwae anew wane wean nyegtr gentry perrim primer preko poker pudmy dumpy pypin nippy rebisc scribe rodug gourd rpeoims imposer promise semipro shewo howes whose wardty tawdry warllc yaldde deadly 

Solving the jumbles problem requires comparing each jumbled word against all the words in the dictionary. The tricky part is finding an efficient way to test the jumbled word against a word from the dictionary. You can't just use the .equals() method to compare them since the jumbled word has it's letters scrambled from the real word it represents. A brute force algorithm would take the jumbled word and generate every possible permutation (reordering) of the letters. As each permutation is generated it would compare that permutation to a particular dictionary word.

Can you think of some issues created by this brute force approach? What if you were to use the all permutations approach with some of the following words?

The deal killer for using a brute-force all-permutations approach is that the number of permutations on a String having N letters is N factorial ( N! ). To understand why this is a problem we need to understand the explosiveness of the factorial function.

We cannot solve this problem in general using the brute force approach. We must look for a heuristic. A heuristic is an approach which eliminates a large portion of the search space and focuses only on a portion of the space that is likely to contain solutions. Our heuristic will be to transform of both the jumbled word and the dictionary word to canonical form for easy comparison. Even with this efficient means of comparing a jumble to real word, be sure that your overall approach is better than something like this:

 THIS IS A VERY INEFFICIENT OVERALL APPROACH (but it does produce the correct out) for each jWord from the sorted ArrayList of jumbles (read from the jumbles file) { print jWord + " " covert it to canonical: i.e. jCanonical open up the dictionary file, again ... sigh :( for each dWord in the dictionary { convert to canonical: i.e. dCanonical if jCanonical.equals(dCanonical) // YOU GOT A HIT :) print dWord + " " } print " "; close dictionary file } 

Study the above algorithm. Recognize that even though it does correctly generate the answer it does so in a very, very inefficient manner. Your solution should only open the dictionary file ONCE and convert the dictionary words to canonical form ONCE (and store them in a container).

There are many possible overall approaches to solving the Jumbles problem. You may solve it any way you can as long as you avoid processing the dictionary words more than once. Also you must generate the EXACT OUTPUT and you must not use TreeSet, TreeMap, HashSet, HashMap etc or any variant of these templated containers. Stick to plain arrays and ArrayLists. You may emulate a HashMap using ArrayList and or plain arrays if you happen to know what a HashMap is, but you may not use Java's Hash or Tree containers because those containers actually trivialize the problem. Later in the course you will solve jumbles with a Java HashMap for a simple lab exercise and find it is only a dozen or so lines of code to do it. For this exercise you must use only the tools we have given you thus far.

Thanks!!

N factorial 3 6 4 24 5 120 6 720 7 5,040 8 40,320 9 362,880 10 3,628,800 1139,916,800 12479,001,600 136,227,020,800 1487,178,291,200 151,307,674,368,000 1620,922,789,888,000 17355,687,428,096,000 186,402,373,705,728,000 19 121,645,100,408,832,000 202,432,902,008,176,640,000 2151,090,942,171,709,400,000 22 1,124,000,727,777,610,000,000 2325,852,016,738,885,000,000,000 24 620,448,401,733,239,000,000,000 25 15,511,210,043,331,000,000,000,000 26 403,291,461,126,606,000,000,000,000 2710,888,869,450,418,400,000,000,000,000 28 304,888,344,611,714,000,000,000,000,000 298,841,761,993,739,700,000,000,000,000,000 30 265,252,859,812,191,000,000,000,000,000,000 barely fits into a java int barely fits into a java long int LARGER THAN 2 to the 64 our Sun has burned out by now