Jump to content

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*.
jumble solver

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

Edited by mrstarc
spell missing
Link to post
Share on other sites
  • Moderators

Moved to the appropriate forum, as the AutoIt Example Scripts forum very clearly states:

Quote

Share your cool AutoIt scripts, UDFs and applications with others.


Do not post general support questions here, instead use the AutoIt Help and Support forums.

Moderation Team

Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Link to post
Share on other sites

From a routine computational point of view (certainly not what your assignment aims to) it's more efficient to add a column to an existing list of words with the letter by letter content of each word.

For instance I have a list of 109562 english words in an SQLite table, including conjugated verbs and plurals of common names, living proper names out.
As an experiment I creates a second column in that table counting the occurence of each letter in the word. Example extract of words starting with 'flowe':

Quote

Word    Letters
flowed    0-0-0-1-1-1-0-0-0-0-0-1-0-0-1-0-0-0-0-0-0-0-1-0-0-0
flower    0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-0-0-0-0-1-0-0-0
flowered    0-0-0-1-2-1-0-0-0-0-0-1-0-0-1-0-0-1-0-0-0-0-1-0-0-0
flowerer    0-0-0-0-2-1-0-0-0-0-0-1-0-0-1-0-0-2-0-0-0-0-1-0-0-0
flowerers    0-0-0-0-2-1-0-0-0-0-0-1-0-0-1-0-0-2-1-0-0-0-1-0-0-0
floweret    0-0-0-0-2-1-0-0-0-0-0-1-0-0-1-0-0-1-0-1-0-0-1-0-0-0
flowerets    0-0-0-0-2-1-0-0-0-0-0-1-0-0-1-0-0-1-1-1-0-0-1-0-0-0
flowerier    0-0-0-0-2-1-0-0-1-0-0-1-0-0-1-0-0-2-0-0-0-0-1-0-0-0
floweriest    0-0-0-0-2-1-0-0-1-0-0-1-0-0-1-0-0-1-1-1-0-0-1-0-0-0
floweriness    0-0-0-0-2-1-0-0-1-0-0-1-0-1-1-0-0-1-2-0-0-0-1-0-0-0
flowering    0-0-0-0-1-1-1-0-1-0-0-1-0-1-1-0-0-1-0-0-0-0-1-0-0-0
flowerless    0-0-0-0-2-1-0-0-0-0-0-2-0-0-1-0-0-1-2-0-0-0-1-0-0-0
flowerpot    0-0-0-0-1-1-0-0-0-0-0-1-0-0-2-1-0-1-0-1-0-0-1-0-0-0
flowerpots    0-0-0-0-1-1-0-0-0-0-0-1-0-0-2-1-0-1-1-1-0-0-1-0-0-0
flowers    0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-1-0-0-0-1-0-0-0
flowery    0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-0-0-0-0-1-0-1-0

There are 26 numbers separated by '-' for counting letters occurences.

Apply the same process to an input anagram to obtain its content in each letter and search the table for words matching the same content. For instance the 4 anagrams of 'lwosfer' (whose "signature" is '0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-1-0-0-0-1-0-0-0') are found in 58ms:

Quote

Word    Letters
flowers    0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-1-0-0-0-1-0-0-0
fowlers    0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-1-0-0-0-1-0-0-0
reflows    0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-1-0-0-0-1-0-0-0
wolfers    0-0-0-0-1-1-0-0-0-0-0-1-0-0-1-0-0-1-1-0-0-0-1-0-0-0

Processing from the other hand, that is explicitely listing all possible anagrams of the input letters and looking up the dictionary for each one in turn to check if there is a match is much less efficient. The average length of words in my dictionary is 8.5 letters, say it's just 8. _ArrayPermute() will list all permutations of an array of 8 letters and even if you apply _ArrayUnique because there are probably duplicate letters in the input, you end up with something like 8! (that is circa 40k) permutations which is a massive loop in dictionary lookup.

You don't have to use a database engine like I did, you can do exactly the same with a conveniently sorted array.

There is a general rule of thumb to be learnt here: if you have the oportunity to invest once a significant work in setup (here: building the signature column in the dictionary) while speeding further routine processes, don't hesitate. It pays off most of the times.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to post
Share on other sites

I confess I'm well aware that I didn't answer the OP's question, in that this assignment focusses on C++ dynamic iterators and related constructs. If that's for a class in C++ programming class design, well, OK. Since this forum isn't a Java, C++, younameit forum we don't have to solve the question posed (if any). But if that's a broader IT question, then it's far off the mark.

If I were to teach students something, I would focus on having them think on problem solving. If a specific solution needs an OO iterator, that is only a technical detail. Leaving thoughts on problem solving an open thing is much more productive that focusing on low-level implementation techniques limited to some language. Learning to be a good problem solver is more valuable than today's low-level techniques.

Our complex world needs hard-problems solvers; those who don't feel comfortable doing that or show little creativity can always take a specialized cursus on the hyped language of the day, fasten his/her belt and find good jobs there.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to post
Share on other sites
  • Moderators

mrstarc,

Please stop posting the same question all over the forum in various new and existing threads. You have received some excellent advice in this one, so over to you to action it.

I have deleted all other instances (I hope!) - if you do post it again I will be forced to take more serious action. Please take note!

M23

Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Link to post
Share on other sites
21 hours ago, jchd said:

I would focus on having them think on problem solving

Can I PLEASE take your programming course instead of university courses!? This sounds amazing, though I'm afraid that your lectures might go a few miles over my head :D

All my code provided is Public Domain... but it may not work. ;) Use it, change it, break it, whatever you want.

Spoiler

My Humble Contributions:
Personal Function Documentation - A personal HelpFile for your functions
Acro.au3 UDF - Automating Acrobat Pro
ToDo Finder - Find #ToDo: lines in your scripts

Link to post
Share on other sites

Sorry I don't have that much free time. I need to make a living with my self-employed job: repairing electronic boards.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to post
Share on other sites

LOL

I would take your classes too if I could. Esp C++ because I have not had any time with it over the years. I learned Java and C# and Python and mastered C so I think I can handle C++, I can read the code and figure out what's going on so I can always learn.

 

I learned BASIC first on my TRS-80 Color computer, then learned to do structured programming with BASIC, then I learned the Assembler for my cpu in the Trash 80 (I loved that machine so much!) then I mastered C in my job at work. the rest is history

 

I always joked that I was the COM king because my programs in C were so tiny, powerful and efficient but super small as well, so I could produce COM files instead of bloated exe files, LOL.

Edited by Earthshine

My resources are limited. You must ask the right questions

 

Link to post
Share on other sites
10 hours ago, jchd said:

Sorry I don't have that much free time.

Does this mean you will no longer be offering the course:

Quote

The Ideographic Variation Sequences and Character Set Standardization for Early Cyrillic Writing 101

:)

Code hard, but don’t hard code...

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
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...