Jumble Solver

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;
}
}

Hello @windfondquist welcome to the forums.

Whilst folks here will be happy to help if they can, no one is going to do your assignment for you. So it’s always helpful to show us what you have done to get started.

@ Gandalf thank you. :slightly_smiling_face:

So what part are you having trouble understanding?

Can’t really offer advice until we know where your level of understanding is.

@ m_hutley I don’t understand where I am facing issues or errors.

Well, you’ve given us the problem statement.

You can’t face issues or errors until you’ve written some code.

So either we need to see what you’ve attempted so far, or you’ve got no issues or errors yet.

1 Like