Jump to content
Sal's RuneScape Forum
Sign in to follow this  
hoshanaeckhart

Jumble Solver

Recommended Posts

Hi.

I need help starting this assignment. The teacher/class is way over my head and I HAVE to do well on this assignment to pass...

So if anyone could assist me in doing and understanding this assignment, it would be greatly appreciated.

Thank you!


____________________________________________________________________________



We will write a program to solve word jumbles. You have probably seen them in the newspaper every day. Quick - what word is formed from the letters 'mezia'? 'cidde'? 'hucnah'? 'bouste'? Your program will solve these by brute force. It will have a list of English words (from Program 8, Spell Checker), and it will generate all permutations of the letters in the jumble. When it finds a permutation that is in the word list, its done.

Requirements

First, use your WordListIndexed to store the English language dictionary from the Spell Checker program. Our jumbles won't contain any punctuation marks or abbreviations. Don't store them in your WordListIndexed.

The primary class in this assignment, StringPermutationIterator, generates all the permutations of the letters in a given string. This class must have an iterator interface: next( ) and hasNext( ) (no remove( ) member function). There are two major challenges for this class. First, generate the permutations recursively. For example, to generate the permutations of a four letter string, put one of the four letters as the first letter and combine it will all permutations of the remaining 3 letters. Repeat until each letter has been used at the front (see example). For simplicity, you may assume that all the letters in the input string are unique (no duplications). If this assumption does not hold then we simply generate some duplicates that cause your program to run a little slower. We still get the correct result. Second, you must generate the permutations incrementally. It is not allowed to generate all permutations, store them in a list, and have the iterator walk down the list. Nor is it allowed to utilize the fact that there will be exactly n! permutations. You must create a true dynamic iterator that generates one at a time the elements of the set of permutations. See the general plan for dynamic iterators*.

Primary classes: StringPermutationIterator.
Application: Write a short main method that unscrambles the 4 jumbles from the first paragraph of this assignment plus 'ueassrkpc'.

____________________________________________________________________________

See example:

SPI("cats")
'c' + an of SPI("ats"). When SPI("ats") rolls over (false == hasNext()), create
an new nested SPI object
'a' + an object SPI("cts"). When SPI("cts") rolls over, create a new SPI object
't' + an object SPI("cas") create SPI("cat")
's' + an object SPI("cat") When SPI("cat") rolls over, we are done.
SPI("cats").hasNext() == false




*
General plan for dynamic iterators:

public class DynamicIterator<String>
implements Iterator<String> {

String buffer;

boolean hasNext() { return buffer != null; }

String next() {
String result = buffer;
buffer = createNextElement();
return result;
}
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site, you agree to our Guidelines and Privacy Policy.