/**

Dictionary.java

This is a dictionary implementation using a Map that holds the word and the definition. The dictionary that is used

is Collins 15th Edition Dictionary (Official Scrabble Dictionary) containing upwards of 270,000 words, published

in 2015.

--------------------------------------------------------------------------------------------------------------------

--File Summary--

@@@@@@@@@@ CONSTRUCTORS @@@@@@@@@@@@@

Dictionary() -- create a Dictionary with words and definitions

Dictionary( boolean useDefs ) -- create a Dictionary with just words, or one with words and definitions

Dictionary( String fileName, LanguageSpecs specs, boolean useDefs ) -- create a Dictionary using another language, with just words, or their defs too

@@@@@@@@@@ PUBLIC FUNCTIONS @@@@@@@@@

isWord( String word ) -- checks if the word is in the Dictionary

isDef( String def ) -- checks if the definition is in the Dictionary

getDef( String word ) -- get the definition of a word

addDefs( String fileName ) -- add definitions to a list of words that have no definitions

descramble( String[] str, String fileName ) -- finds all words of a list of letters allowing rearrangement and removal. Then removes

-- duplicates, orders the words in increasing word length, and alphabetizes each set of length words

descramble( String str, String fileName ) -- same as above

descramble( char[] str, String fileName ) -- same as above

descramble( String[] str ) -- find all words of a list of letters allowing rearrangement and removal

descramble( String str ) -- same as above

descramble( char[] str ) -- same as above

scramble( String[] str ) -- find all permutations of all subsets of a list of letters

scramble( String str ) -- same as above

scramble( char[] str ) -- same as above

descrambleAnagram( String str ) -- finds all anagrams of a String (same as descramble method, but only gets words of same length as input token)

descrambleReps( String str ) -- finds all the anagrams of a String, allowing for repeated letters up to a set limit

descrambleReps( String str, int limit ) -- finds all of the anagrams of a String, allowing for a limited number of repeated letters

descrambleSpecs( String[] specs, String newFileName ) -- find all the words in the dictionary that match the given specs

descrambleSpecs( String specs, String newFileName ) -- same as above

descrambleSpecs( char[] specs, String newFileName ) -- same as above

descrambleSpecs( String[] specs, String oldFileName, String newFileName ) -- find all the words in the text file that match the given specs,

-- preserving the old text file

descrambleSpecs( String specs, String oldFileName, String newFileName ) -- same as above

descrambleSpecs( String[] specs, String str, String descrambleFileName, String newFileName ) -- find all the words made from the descrambled

-- letters that match the given specs

descrambleSpecs( String specs, String str, String descrambleFileName, String newFileName ) -- same as above

makeLanguage( LanguageSpecs specs, String fileName ) -- make a new language and store it in a text file;

-- based on randomization and approximation to another language (default English)

processNewWord( LanguageSpecs specs, String word ) -- create a new word based on the specs of a new language based on the original word

orderIncreasing( String fileName ) -- reorder a text file in increasing word length order

orderIncreasing( String oldFileName, String newFileName ) -- reorder a text file in increasing word length order, preserving the old file

alphabetize( String fileName ) -- alphabetize a text file (lexicographically)

alphabetize( String oldFileName, String newFileName ) -- alphabetize a text file (lexicographically), preserving the old file

alphabetizeSets( String fileName ) -- alphabetize a text file per each set of words of a given length

alphabetizeSets( String oldFileName, String newFileName ) -- alphabetize a text file per each set of words of a given length, preserving the old file

removeDuplicates( String fileName ) -- remove the duplicate entries from a text file

removeDuplicates( String oldFileName, String newFileName ) -- remove the duplicate entries from a text file, preserving the old file

removeDuplicates( ArrayList<?> list ) -- remove all duplicates in the list and returns the new list

getXLetterWords( int length ) -- get words of specified length

getWordsContainingX( String token ) -- get words containing a specified token

getWordsContainingX( String[] tokens ) -- get words containing multiple tokens

getAppends( String word ) -- get words containing a specified word

getWordsContainingXButNotY( String token, String exclusionToken ) -- get words containing a specified token, but not containing a different one

getWordsContainingXButNotY( String token, String[] exclusionTokens ) -- same as above, but can have multiple exclusion tokens

getDefsContainingX( String token ) -- get definitions containing a specified token

getDefsContainingX( String[] tokens ) -- get definitions containing any of a set of specified tokens

write( String[] list, String fileName ) -- write a list to a text file

write( ArrayList<String> list, String fileName ) -- write a list to a text file

write( LinkedHashMap<String, String> list, String fileName ) -- write a list to a text file

writeLimit( String[] list, String fileName, int upperLimit ) -- write a list to a text file, excluding words that are longer than a specified limit

writeLimit( String[] list, String fileName, int lowerLimit, int upperLimit ) -- write a list to a text file, excluding words based on length limits

removeWords( String fileName, String token ) -- remove all instances of the given word (do not remove if found in contained in another word)

removeWords( String oldFileName, String newFileName, String token ) -- same as above, but preserve old file, and create a new one

removeWordsContainingX( String fileName, String token ) -- edit a text file and replace it, removing words containing the given token

removeWordsContainingX( String oldFileName, String newFileName, String token ) -- same as above, but preserve old file, and create a new one

removeWordsContainingX( String fileName, String[] tokens ) -- edit a text file and replace it, removing words containing any of the given tokens

removeWordsContainingX( String oldFileName, String newFileName, String[] tokens ) -- same as above, but preserve old file, and create a new one

removeWordsLongerThanX( String fileName, int upperLimit ) -- edit a text file and replace it, removing all words longer than the given limit

removeWordsLongerThanX( String oldFileName, String newFileName, int upperLimit ) -- same as above, but preserve old file, and create a new one

clearFile( String fileName ) -- clear all contents of a text file so that it has nothing in it

renameFile( String oldFileName, String newFileName ) -- renames file to new name

fileContains( String fileName, String token ) -- True if the text file contains the token, false otherwise

printFileList() -- prints the names of all the files in the current directory

printList( String[] list ) -- print the list of words to the console

printFile( String fileName ) -- print the text file to the console

@@@@@@@@@@ PRIVATE FUNCTIONS @@@@@@@@

containsAny( String word, String[] tokens ) -- finds whether the word contains any of the tokens (true) or not (false)

containsAll( String word, String[] tokens ) -- finds whether the word contains all of the tokens (true) or not (false)

addWords( Scanner scanner ) -- add the list of words to the Dictionary (no definitions)

addWordsAndDefs( Scanner scanner ) -- add the list of words and their definitions to the Dictionary

addArray( ArrayList<String> arrayList, String[] list ) -- add the contents of an array to the end of an ArrayList

descrambleMain( String[] list ) -- adds the tokens that are words to the list and shrinks the list

descrambleReg( String[] str, String fileName ) -- descramble a set of letters with no variables

descrambleVar( String[] str, String fileName, int varIndex1, int varIndex2 ) -- descramble a set of letters with up to two variables

descrambleSubsets( String[] str ) -- finds all subsets of a list of letters

descramblePermutations( String prefix, String str, ArrayList<String> result ) -- finds all permutations of a list of letters

descrambleSpecs( String[] specs, Scanner scanner ) -- find all matches that fit the specs and return them in a list

removeReps( String str ) -- removes repeated letters from a String and returns the result

alphabetizeSets( Scanner scanner ) -- alphabetize a text file per each set of words of a given length

getScanner( String fileName ) -- gets a Scanner to read the text file

getFileSize( Scanner scanner ) -- gets the number of lines in the file

renameFileHandler( String oldFileName, String newFileName ) throws IOException -- renames file to new name

shrinkArray( String[] list, int actualSize ) -- If an array as open, unfilled spots, use this to return and replace the array without those spots

getWorkingDirectory() -- get the working directory direct path

printExecutionTime( long beginTime ) -- print the total time used during a process

SOPln( String message ) -- never type out System.out.println(..) again with this wonderful, short method; also reduces carpal tunnel

@@@@@@@@@@ PRIVATE CLASSES @@@@@@@@@@

BaseChain

BaseChain( int base, int length ) -- create a BaseChain object with the given base-X system and chain length

BaseChain( int base, int length, int limit ) -- create a BaseChain object with the given base-x system and chain length, with the limit

of repeated letter possibilities

Fields

- int base --> the base of the number system for counting with the chain

- int length --> the length of the chain

- int[] chain --> the elements stored in an array

- int limit --> the limit imposed on the total allowed repeated letters for permuting

- boolean updated --> for chains of no repeated letters, this is used for showing when a chain has been amended

Public Methods

- add() -- increments the chain by 1

- get() -- gets the chain array

- length() -- gets the length of the chain

- numNonZero() -- gets the numbers of nonzero elements within the chain

Private Methods

- addNoLimit() -- for chains with no limit

- addLimit() -- for chains with a limit

@@@@@@@@@@ GLOBALS @@@@@@@@@@@@@@@@@@

DICTIONARY_NO_DEFS_FILE_NAME -- the text file containing just words from Collin's 15th Edition Dictionary (2015)

DICTIONARY_WITH_DEFS_FILE_NAME -- the text file containing words and their definitions from Collin's 15th Edition Dictionary

NUM_WORDS -- holds the number of the words in the dictionary

ENGLISH_ALPHABET_LIST -- the list of the letters in the English alphabet (default)

ALPHABET_LIST -- the list of the letters in the alphabet

VOWELS -- determines what is considered a vowel. Check this variable if you want to include 'Y' as a vowel or not

DIRECTORY_PATH -- the direct path of the directory -- used to print all text files. Allows you to have this file in one place,

and access text files in another place. Thus, choose a direct path that has the text files that you are using

--------------------------------------------------------------------------------------------------------------------

@author Peter Olson

@version 10/15/21

@see dictionary_no_defs.txt

@see dictionary_defs.txt

@see dictionary_rikitikita.txt

@see DictionaryRunner.java

@see LanguageSpecs.java

@see WordFinderGame.java

*/

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.Scanner;

import java.util.Random;

import java.util.Collections;

import java.util.ArrayList;

import java.util.Arrays;

import java.io.FileReader;

import java.io.FileNotFoundException;

import java.io.PrintStream;

import java.io.PrintWriter;

import java.io.File;

import java.io.FilenameFilter;

import java.io.IOException;

import java.nio.file.FileSystems;

import java.nio.file.Files;

import java.nio.file.Path;

import java.nio.file.Paths;

import java.nio.file.StandardCopyOption;

import java.util.Iterator;

public class Dictionary extends LinkedHashMap {

public final String DICTIONARY_NO_DEFS_FILE_NAME = "dictionary_no_defs.txt"; //276,643 words -- Collins 15th Edition Dictionary 2015

public final String DICTIONARY_WITH_DEFS_FILE_NAME = "dictionary_defs.txt";

public final int NUM_WORDS;

public final String[] ENGLISH_ALPHABET_LIST = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};

public String[] ALPHABET_LIST; //by default, this is English ^^; also can be set to another language

public final String VOWELS = "AEIOU"; //@@@NOTE: If you want 'Y' to be a vowel, this String needs to be changed. (add 'Y')

public final String DIRECTORY_PATH = "C://Users/Peter/Desktop/UnclePedro/Work/teaching/cs/Java Files/Java Worksheets and Assignments/teacher";

/**

Create a dictionary and add all the words and definitions to it (note, Dictionary is a HashMap).

NOTE: Default constructor adds words and definitions using the DICTIONARY_WITH_DEFS_FILE_NAME

text file.

@see DICTIONARY_WITH_DEFS_FILE_NAME --> see text file

*/

public Dictionary () {

Scanner scanner = getScanner( DICTIONARY_WITH_DEFS_FILE_NAME );

ALPHABET_LIST = ENGLISH_ALPHABET_LIST;

addWordsAndDefs( scanner );

NUM_WORDS = this.size();

}

/**

Create a dictionary and add all the words and definitions to it, or just the words

(note, Dictionary is a HashMap).

NOTE: Default constructor adds words and definitions using the DICTIONARY_WITH_DEFS_FILE_NAME

text file.

@param useDefs True --> add words and defs; False --> only add the words, no defs

@see DICTIONARY_WITH_DEFS_FILE_NAME --> see text file

@see DICTIONARY_NO_DEFS_FILE_NAME --> see text file

*/

public Dictionary( boolean useDefs ) {

ALPHABET_LIST = ENGLISH_ALPHABET_LIST;

if( useDefs ) {

Scanner scanner = getScanner( DICTIONARY_WITH_DEFS_FILE_NAME );

addWordsAndDefs( scanner );

} else {

Scanner scanner = getScanner( DICTIONARY_NO_DEFS_FILE_NAME );

addWords( scanner );

}

NUM_WORDS = this.size();

}

/**

Create a dictionary with a new language (note: dictionary is a HashMap).

@param fileName The name of the text file containing the words to add

@param specs The details for creating the new language

@param fileName The file to check

@see makeLanguage( LanguageSpecs specs, String fileName )

*/

public Dictionary( String fileName, LanguageSpecs specs, boolean useDefs ) {

Scanner scanner = getScanner( fileName );

ALPHABET_LIST = specs.ALPHABET;

if( useDefs )

addWordsAndDefs( scanner );

else

addWords( scanner );

NUM_WORDS = this.size();

}

/**

Tells whether the given String is a word or not.

@param word The word to check and see if it is in the Dictionary or not

@return boolean True if it is a word, false otherwise

@see containsKey( Key key )

*/

public boolean isWord( String word ) {

return containsKey( word.toUpperCase() );

}

/**

Tells whether the given String is a definition of a word in the dictionary or not

@param def The definition to check and see if it is associated with a word. Note: The given definition must be

exactly equal to the definition in the dictionary in order for this to return true

@return boolean True if it is a definition, false otherwise

@see containsValue( Value value )

*/

public boolean isDef( String def ) {

return containsValue( def );

}

/**

Returns the definition associated with the word given. If the word is not in the dictionary,

"That's not a word!" is returned.

@param word The word to get the definition of

@return String The definition of the word if it is in the dictionary, or the String "That's not a word!"

@see HashMap.get( Key key )

*/

public String getDef( String word ) {

word = word.toUpperCase();

if( isWord( word ) )

return (String)this.get( word );

else

return "That's not a word!";

}

/**

Given a text file with words that have no definitions, add their definitions to the same file (separated by tabs)

@param fileName The text file to be editted to have words and their definitions

@see write( String[] list, String fileName )

*/

public void addDefs( String fileName ) {

if( !fileName.contains(".txt") )

fileName += ".txt";

Scanner fileScanner = getScanner( fileName );

int size = getFileSize( fileScanner );

//Must declare new Scanner object so that the Scanner is pointing at the top of the file again

fileScanner = getScanner( fileName );

String[] list = new String[ size ];

int i = 0;

while( fileScanner.hasNextLine() ) {

String word = fileScanner.nextLine();

list[i] = word + "\t";

list[i++] += getDef( word );

}

write( list, fileName );

fileScanner.close();

}

/**

Gets the total number of words in this dictionary

@return int The total number of words in this dictionary

*/

public int getNumWords() {

return NUM_WORDS;

}

/**

Gets the total number of words in this text file (Note that this returns the total number of lines, and is not a word count

@param fileName The text file to scan / observe

@return int The total number of words in the text file

@see getFileSize( Scanner scanner )

@see getScanner ( String fileName )

*/

public int getNumWords( String fileName ) {

if( !fileName.contains(".txt") )

fileName += ".txt";

Scanner scanner = getScanner( fileName );

return getFileSize( scanner );

}

/**

Create a dictionary filled with words of a new language. These new words are randomized using the processNewWord(..) method that is dependent

upon the LanguageSpecs for that language. Each word added is unique

@param specs The specs of the new language, including details on randomization, randomization length, randomization buffer, and the details on the letters of the alphabet

@param fileName The file to be written to

@return Dictionary A HashMap Dictionary object containing all of the words in the new language, which have been translated from the original language

*/

public void makeLanguage( LanguageSpecs specs, String fileName ) {

LinkedHashMap<String, String> dict = this;

LinkedHashMap<String, String> newDict = new LinkedHashMap<String, String>(); //I don't understand why I have to do this instead of just calling this.keySet() below

for( String word : dict.keySet() ) {

String newWord = processNewWord( specs, word );

//no repeated words

while( newDict.get(newWord) != null ) {

newWord = processNewWord( specs, word );

}

newDict.put( newWord, null );

}

write( newDict, fileName );

}

/**

* Process a new word in the new language dependent upon the specs of the LanguageSpecs. These new words can be randomized, can be made to be close to the length of the word,

* or random length, or the exact length of the original word.

*

* @param specs The specs of the Language, providing details on randomization, randomization length, randomization buffers, and the language itself

* @param word The word to be translated into a new word

* @return String The word in the new language

* @see makeLanguage( Language specs )

*/

public String processNewWord( LanguageSpecs specs, String word ) {

int engWordLength = word.length();

int newWordNumLetterSets = 0;

Random random = new Random();

if( specs.MATCH_LENGTH ) {

/* Since letters in another language might be multiple characters, divide by average letter length to approximate the correct number of

characters for the new word in the new language

*/

newWordNumLetterSets = engWordLength / specs.AVG_LETTER_LENGTH;

if( specs.RANDOMIZE_LENGTH ) {

/* The line below randomly adds a number within the range of the approximate length buffer. The number can be negative

or positive, depending on the randomization. A line below assures that it will not be a set less than the

MIN_RANDOMIZATION_LENGTH or longer than the MAX_RANDOMIZATION_LENGTH

*/

newWordNumLetterSets += ( Math.pow(-1, random.nextInt(2) + 1 ) ) * random.nextInt( specs.APPROX_LENGTH_BUFFER );

if( newWordNumLetterSets > specs.MAX_RANDOMIZATION_LENGTH )

newWordNumLetterSets = specs.MAX_RANDOMIZATION_LENGTH;

else if( newWordNumLetterSets < specs.MIN_RANDOMIZATION_LENGTH )

newWordNumLetterSets = specs.MIN_RANDOMIZATION_LENGTH;

}

} else {

// Set the number of letters to be equal to some number inbetween the max and min randomization range

newWordNumLetterSets += random.nextInt( specs.MAX_RANDOMIZATION_LENGTH - specs.MIN_RANDOMIZATION_LENGTH + 1 ) + specs.MIN_RANDOMIZATION_LENGTH;

}

String newWord = "";

int newAlphabetLength = specs.ALPHABET.length;

//Put together random letters from the new alphabet to make the new word

for( int i = 0; i < newWordNumLetterSets; i++ ) {

newWord += specs.ALPHABET[ random.nextInt( newAlphabetLength ) ];

}

return newWord;

}

/**

Given a set of letters, finds all the possible words that this set can make, and returns them in a list of Strings

@param str The array of characters to be parsed and processed

@return String[] The list of words that can be found by rearrangement and removal

@see descramble( String[] str )

*/

public String[] descramble( char[] str ) {

return descramble( new String( str ) );

}

/**

Given a set of letters, finds all the possible words that this set can make, removes the duplicates,

orders the file in sets of same length words, and alphabetizes each set of length words.

@param str The array of characters to be parsed and processed

@return boolean True if there are 2 or less '?'s and the method is successful, false otherwise

@see descramble( String[] str, String fileName )

*/

public boolean descramble( char[] str, String fileName ) {

return descramble( new String( str ), fileName );

}

/**

Given a set of letters, finds all the possible words that this set can make, and returns them in a list of Strings

@param str The String of letters to be parsed and processed

@return String[] The list of words that can be found by rearrangement and removal

@see descramble( String[] str )

*/

public String[] descramble( String str ) {

String[] listOfLetters = new String[ str.length() ];

for( int i = 0; i < listOfLetters.length; i++ )

listOfLetters[i] = String.valueOf( str.charAt(i) );

return descramble( listOfLetters );

}

/**

Given a set of letters, finds all the possible words that this set can make, removes the duplicates,

orders the file in sets of same length words, and alphabetizes each set of length words.

@param str The String of letters to be parsed and processed

@param fileName The text file to be processed

@return boolean True if there are 2 or less '?'s and the method is successful, false otherwise

@see descramble( String[] str, String fileName )

*/

public boolean descramble( String str, String fileName ) {

String[] listOfLetters = new String[ str.length() ];

for( int i = 0; i < listOfLetters.length; i++ )

listOfLetters[i] = String.valueOf( str.charAt(i) );

return descramble( listOfLetters, fileName );

}

/**

Given a set of letters, finds all the possible words that this set can make, and returns them in a list of Strings

@param str The list of letters to process-- Each element should be one letter long

@return String[] The list of words that can be found by rearrangement and removal

@see scramble( String[] str )

@see shrinkArray( String[] list, int actualSize )

*/

public String[] descramble( String[] str ) {

for( int i = 0; i < str.length; i++ )

str[i] = str[i].toUpperCase();

String[] list = scramble( str );

return descrambleMain( list );

}

/**

Determines which tokens are words from the list and returns a list with just those words

@param list The list of tokens to process

@return String[] The list of words

@see isWord( String word )

@see descramble( String[] str )

@see descrambleReg( String[] str, String fileName )

@see descrambleVar( String[] str, String fileName )

*/

private String[] descrambleMain( String[] list ) {

String[] words = new String[ list.length ];

int count = 0;

for( int i = 0; i < list.length; i++ ) {

if( isWord( list[i] ) ) {

words[ count ] = list[i];

count++;

}

}

words = shrinkArray( words, count );

return words;

}

/**

Given a set of letters, finds all the possible words that this set can make, removes the duplicates,

orders the file in sets of same length words, and alphabetizes each set of length words.

@param str The list of letters to process-- Each element should be one letter long

@return boolean True if there are 2 or less '?'s and the method is successful, false otherwise

@see scramble( String[] str )

@see shrinkArray( String[] list, int actualSize )

@see write( String[] list, String fileName )

@see removeDuplicates( String fileName )

@see orderIncreasing( String fileName )

@see alphabetizeSets( String fileName )

*/

public boolean descramble( String[] str, String fileName ) {

if( !fileName.contains(".txt") )

fileName += ".txt";

boolean containsVariable = false;

int count = 0;

int index = -1;

int index2 = -1;

for( int i = 0; i < str.length; i++ ) {

str[i] = str[i].toUpperCase();

if( str[i].equals("?") && count == 0 ) {

containsVariable = true;

index = i;

count++;

} else if ( str[i].equals("?") && count == 1 ) {

index2 = i;

count++;

} else if ( str[i].equals("?") && count > 1 ) {

return false;

}

}

if( !containsVariable )

descrambleReg( str, fileName );

else

descrambleVar( str, fileName, index, index2 );

return true;

}

/**

Given a set of letters, finds all the possible words that this set can make, removes the duplicates,

orders the file in sets of same length words, and alphabetizes each set of length words.

@param str The list of letters to process-- Each element should be one letter long

@return String[] The list of words that can be found by rearrangement and removal

@see scramble( String[] str )

@see shrinkArray( String[] list, int actualSize )

@see write( String[] list, String fileName )

@see removeDuplicates( String fileName )

@see orderIncreasing( String fileName )

@see alphabetizeSets( String fileName )

*/

private void descrambleReg( String[] str, String fileName ) {

String[] list = scramble( str );

String[] words = descrambleMain( list );

write( words, fileName );

this.removeDuplicates( fileName );

this.orderIncreasing( fileName );

this.alphabetizeSets( fileName );

}

/**

Given a set of letters, finds all the possible words that this set can make, removes the duplicates,

orders the file in sets of same length words, and alphabetizes each set of length words. If a '?' is included with

this set of letters, this is a variable that can be any letter. Thus, all 26 possibilities will be assessed and added

Note that two variables is O(n!*(n^3)*(26^2)) (yikes!) -- Thus, for one variable, the total number of allowed letters

to descramble (including the variable) is 10 letters still (approx. 3.6b * 26 = 94b ~approx 260 sec = 4 minutes and change)

The max number of allowed letters for two variables is 7 letters ( 5 seconds ), since 8 letters is more than 20 minutes of computation time

@param str The list of letters to process-- Each element should be one letter long

@return String[] The list of words that can be found by rearrangement and removal

@see addArray( ArrayList<String> arrayList, String[] list )

@see scramble( String[] str )

@see shrinkArray( String[] list, int actualSize )

@see write( String[] list, String fileName )

@see removeDuplicates( String fileName )

@see orderIncreasing( String fileName )

@see alphabetizeSets( String fileName )

*/

private void descrambleVar( String[] str, String fileName, int varIndex1, int varIndex2 ) {

ArrayList<String> varLists = new ArrayList<String>();

String[] list = new String[ fact( str.length ) ];

// Max allowed letters with 1 variable: 10 letters (4 mins)

// 2 varaibles: 8 letters (8 mins)

if( varIndex2 == -1 )

if( str.length > 10 )

return;

else

if( str.length > 9 )

return;

// If varIndex == -1, then there is just 1 variable. Otherwise, there are two variables

if( varIndex2 == -1 ) {

for( int i = 0; i < ALPHABET_LIST.length; i++ ) {

str[ varIndex1 ] = ALPHABET_LIST[i];

list = scramble( str );

varLists = addArray( varLists, list );

}

} else {

for( int i = 0; i < ALPHABET_LIST.length; i++ ) {

str[ varIndex1 ] = ALPHABET_LIST[i];

for( int j = 0; j < ALPHABET_LIST.length; j++ ) {

str[ varIndex2 ] = ALPHABET_LIST[j];

list = scramble( str );

varLists = addArray( varLists, list );

}

}

}

Object[] objArray = varLists.toArray();

String[] varListArray = Arrays.copyOf( objArray, objArray.length, String[].class);

String[] words = descrambleMain( varListArray );

write( words, fileName );

this.removeDuplicates( fileName );

this.orderIncreasing( fileName );

this.alphabetizeSets( fileName );

}

/**

Given a set of letters, finds all the possible forms that this set can make, and returns them in a list of Strings

@param str The array of characters to be parsed and processed

@return String[] The list of Strings that can be found by rearrangement and removal

@see scramble( String[] str )

*/

public String[] scramble( char[] str ) {

return scramble( new String( str ) );

}

/**

Given a set of letters, finds all the possible forms that this set can make, and returns them in a list of Strings

@param str The String of letters to be parsed and processed

@return String[] The list of Strings that can be found by rearrangement and removal

@see scramble( String[] str )

*/

public String[] scramble( String str ) {

String[] listOfLetters = new String[ str.length() ];

for( int i = 0; i < listOfLetters.length; i++ )

listOfLetters[i] = String.valueOf( str.charAt(i) );

return scramble( listOfLetters );

}

/**

Given a set of letters, finds all possible subsets of these letters and their permutations ie. returns a list of

all possible combinations of the letters, regardless of whether these are words or not

@param str The list of letters to process-- Each element should be one letter long

@return String[] The list of all permutations of all subsets

@see descrambleSubsets( String[] str )

*/

public String[] scramble( String[] str ) {

//This computer (Lenovo y510P) runs on 2.4GHz --> approx 2.4 billion computations/sec

//Based on an approximate O(n!*n^3) --> 13 --> 13 trillion (approx 13000 sec = 3.6 hours) cycles

// --> 10 --> 3.6 billion (approx 2 sec) cycles

// 1 variable --> 10 --> 94 billion (approx 260 sec ~approx 4 minutes) cycles

// 2 variables --> 8 --> ?? (more than 20 minutes) cycles

// 7 --> ?? -- 5 seconds

/*

Variable limits are handled in descrambleVar(..) method

Note that two variables is O(n!*(n^3)*(26^2)) (yikes!) -- Thus, for one variable, the total number of allowed letters

to descramble (including the variable) is 10 letters still (approx. 3.6b * 26 = 94b ~approx 260 sec = 4 minutes and change)

The max number of allowed letters for two variables is 8 letters (13b) ~approx 40 sec, or 9 letters (178b) ~approx 8 minutes

*/

final int MAX_COMPUTATIONAL_LIMIT = 10;

int size = str.length;

if( size > MAX_COMPUTATIONAL_LIMIT || size < 2 )

return str;

ArrayList<String> result = descrambleSubsets( str );

Object[] objArray = result.toArray();

String[] strArray = Arrays.copyOf( objArray, objArray.length, String[].class);

return strArray;

}

/**

Given a String which presumably contains a list of jumbled letters, finds all of the

descrambled words that can be found using all letters of that word.

eg. descrambleAnagram( "dpiswbree" ) yields "spiderweb"

eg. descrambleAnagram( "rstlnea" ) yields "rentals", "sternal", "slanter", "saltern", and "antlers"

eg. descrambleAnagram( "zxcvbnm" ) yields <nothing>

@param str The String to find the anagrams of

@return String[] The list of descrambled anagram words

@see descramblePermutations( String prefix, String token, ArrayList<String> list )

@see removeDuplicates( ArrayList<?> list )

*/

public String[] descrambleAnagram( String str ) {

ArrayList<String> result = descramblePermutations( "", str, new ArrayList<String>() );

int sizeList = result.size();

ArrayList<String> words = new ArrayList<String>();

//just add Strings that are words in the dct

for( int i = 0; i < sizeList; i++ ) {

if( this.isWord( result.get(i) ) )

words.add( result.get(i) );

}

words = (ArrayList<String>)removeDuplicates( words );

Object[] objArray = words.toArray();

String[] strArray = Arrays.copyOf( objArray, objArray.length, String[].class);

return strArray;

}

/**

Given a String which presumably contains a list of jumbled letters, finds all of the

descrambled words that can be found using all letters of that word, allowing for

repetition of letters that are found in the word

A limit must be made on the number of repetitions within the word due to the issue of

permutations creating an intractable problem. The descramble functions operate on an

order close to O(n^2) at worst, whereas this function results in a complexity of

O(n^2)*O(a^b), where a is the average number of repetitions per letter, and b is the

number of letters in the word.

The descramble functions operate within a fraction of a second. At a cap of 7 letters

descrambled with repetitions, we get the following operating times based on the max

limits for repetitions per letter:

2: 7^2 * 2^7 = ~627.2 to 6272 seconds [10 minutes to 100 minutes]

3: 7^2 * 3^7 = ~10,716.3 to 107,163 seconds [2.9 hrs to 29 hours]

...

In order to decrease these computational times, further reductions within the synthesis

are necessary, such as setting restrictions on the repetitions of vowels and/or common

consonants, and intraprocess checking

Thus, a limit is set in order to reduce the load on the heap space. A limit of total

additional reps is set per word, so the total repeated letters reduces the total

permutations that are checked for finding words. Here is a chart of the adjusted

times, considering factors such as word length, total repeats allowed per letter, and

total allowed repeats in general:

Word Length | Letter Repeats Max | Total Repeats Max | Average Computational Time

---------------------------------------------------------------------------------

3 | 1 | 1 | 0ms

4 | 1 | 1 | 1ms

5 | 1 | 1 | 2ms

6 | 1 | 1 | 7ms

7 | 1 | 1 | 12ms

8 | 1 | 1 | 31ms

9 | 1 | 1 | 241ms

10 | 1 | 1 | 2s

11 | 1 | 1 | 21s

---------------------------------------------------------------------------------

3 | 1 | 2 | 27ms

4 | 1 | 2 | 33ms

5 | 1 | 2 | 519ms

6 | 1 | 2 | 49s

---------------------------------------------------------------------------------

3 | 1 | 3 | 27ms

4 | 1 | 3 | 33ms

5 | 1 | 3 | 519ms

6 | 1 | 3 | 49s

---------------------------------------------------------------------------------

@param str The String to find the anagrams of. Does not need to contain repeat letters. The

function will add the additional repeated letters on a permutative basis

@param totalRepLimit The max allowed count of repeated letters to permutate

@return String[] The list of descrambled anagram words

@see descrambleAnagram( String str )

@see REP_LIMIT The limit to the total number of allowed repeated letters

@see removeReps( String str )

@see BaseChain.numNonZero()

@see BaseChain.add()

@see Arrays.copyOf(...)

*/

public String[] descrambleReps( String str, int totalRepLimit ) {

final int BASE = 2;

final int CHAR_REP_LIMIT = totalRepLimit;

final int FULL = -1; //@see BaseChain.numNonZero()

//@@DEBUG

long beginTime = System.currentTimeMillis();

String strNoReps = removeReps( str );

char[] charList = strNoReps.toCharArray();

ArrayList<String> masterList = new ArrayList<String>();

int length = strNoReps.length();

BaseChain bc = new BaseChain( BASE, length, CHAR_REP_LIMIT );

int[] chain = new int[ length ];

//check all permutations of repeated characters

for( int i = 0; bc.numNonZero() != FULL; i++ ) {

String newStr = "";

//iterate through all letters of word

for( int j = 0; j < length; j++ ) {

//iterate through all reps of each letter

for( int k = 0; k <= chain[j]; k++ ) {

newStr += Character.toString( charList[j] );

}

}

String[] wordList = descrambleAnagram( newStr );

masterList.addAll( Arrays.asList( wordList ) );

chain = bc.add();

}

masterList = (ArrayList<String>)removeDuplicates( masterList );

Object[] objArray = masterList.toArray();

String[] strArray = Arrays.copyOf( objArray, objArray.length, String[].class);

//@@DEBUG

printExecutionTime( beginTime );

return strArray;

}

/**

@param str The String to find the anagrams of. Does not need to contain repeat letters. The

function will add the additional repeated letters on a permutative basis

@return String[] The list of descrambled anagram words

@see descrambleReps( String str, int totalRepLimit )

*/

public String[] descrambleReps( String str ) {

final int DEFAULT_REP_LIMIT = 2;

return descrambleReps( str, DEFAULT_REP_LIMIT );

}

/**

BaseChain is a data structure that uses an array to count

iteratively similar to counting in different base systems.

Each subsequent index contains integers which are equal up

to the value of the base counting system minus 1

Eg. Base-2 BaseChains count from zero up to one

Eg. Base-7 BaseChains count from zero up to six

@see descrambleReps( String str )

*/

private class BaseChain {

private int base; //Describes the base system of the chain

private int length; //Describes the number of chain indices

private int[] chain; //Holds the quantities of each index

private int limit; //Describes the limit to the number of nonzero quantities of the chain

//--> by default, the limit is equal to the length of the chain

private boolean updated = false;

/**

Create an empty chain (of zeros) of the stated base

@param base The base of the chain

@param length The number of links of the chain

*/

public BaseChain( int base, int length ) {

this.base = base;

this.length = length;

this.limit = length;

chain = new int[ length ];

}

/**

Create an empty chain (of zeros) of the stated base.

The chain is limited to having a specified number of nonzero elements

@param base The base of the chain

@param length The number of links of the chain

*/

public BaseChain( int base, int length, int limit ) {

this.base = base;

this.length = length;

this.limit = limit;

chain = new int[ length ];

}

/**

Increase the basechain by 1

@return int[] The int array of chain values

@see addNoLimit();

@see addLimit();

*/

public int[] add( ) {

updated = true;

if( limit == length )

return addNoLimit();

else

return addLimit();

}

/**

Increase the basechain by 1

@return int[] The int array of chain values

@see add()

@see addLimit()

*/

private int[] addNoLimit( ) {

boolean doContinue = true;

for( int i = 0; i < length && doContinue; i++ ) {

//add one since not at base value - 1

if( chain[i] != base - 1 ) {

chain[i] += 1;

doContinue = false;

//element is at max value, so reset to zero and continue loop

} else {

chain[i] = 0;

doContinue = true;

}

}

return chain;

}

/**

Increase the limited basechain by 1.

Since the chain is limited to a number of nonzero

elements, adding must count according to the permutations

that are allowed, disallowing there to be more than the

limit-number of nonzero elements

@return int[] The int array of chain values

@see add()

@see addNoLimit()

*/

private int[] addLimit( ) {

int totalNonZeros = numNonZero();

boolean doContinue = true;

for( int i = 0; i < length && doContinue; i++ ) {

//add one if not at limit

if( chain[i] != base - 1 && ( totalNonZeros != limit || doContinue ) ) {

chain[i] += 1;

doContinue = false;

//set previous elements to zero and add one to end of contiguous nonzero elements

//--> when the chain is full

} else if( chain[i] != base - 1 && totalNonZeros == limit && !doContinue ) {

int j = i+1;

while( j < length && chain[j] != 0 ) {

chain[j++] = 0;

}

chain[j] += 1;

doContinue = false;

//element is at max value, so reset to zero and continue loop

} else {