Dictionary algorithm, computing all case options

Question

I am building this algorithm as part of a larger project for a network security class. The gist of this part is that I have been given a dictionary, and I need to find every possible option for a word in both upper and lowercase.

My teacher selected a word out of this dictionary, and messed with the case of a few random letters in it, then created the SHA-256 hash value for it. We have been given the hash value and now have to find the word.

I figured I would create two new dictionaries, use the first one to create all possible options of the upper lowercase combinations, then use that second one to create a third with all the hash values.

Example:

to
tO
To
TO

My first thought was that it looked a lot like counting in binary, and that's what I have based this algorithm off of. The only problem is that it's pretty slow.

   public class DictionaryBuilder {

private Scanner in;
private PrintWriter out;

public DictionaryBuilder() {

}

public File createHashDictionary(File dictionary) throws IOException {
    File hashDict = new File("HashDictionary.txt");
    in = new Scanner(dictionary);
    out = new PrintWriter(hashDict);
    String word;
    String wordList[];

    while (in.hasNext()) {
        wordList = getSmallWordList(in.nextLine());
        for (int i = 0; i < wordList.length; i++) {
            out.println(wordList[i]);
        }

    }
    in.close();
    out.close();
    return hashDict;
}

public String[] getSmallWordList(String _word) {
    System.out.println(_word);
    char[] word = _word.toCharArray();

    int length = (int) (Math.pow(2, _word.length()));

    char[][] binaryList = new char[word.length][length];

    int weirdCount = length / 2;

    for (int i = 0; i < word.length; i++) {
        //System.out.println();
        int count = 0;
        int onOff = 1;

        for (int n = 0; n < length; n++) {
            if (count == weirdCount) {
                onOff++;
                count = 0;
            }
            if ((onOff % 2 == 0)) {
                binaryList[i][n] = Character.toLowerCase(word[i]);
                System.out.print(binaryList[i][n]);
                count++;
            } else {
                binaryList[i][n] = Character.toUpperCase(word[i]);
                //System.out.print(binaryList[i][n]);
                count++;
            }
        }
        weirdCount = weirdCount / 2;
    }

    //System.out.println();
    //System.out.println();
    String wordList[] = new String[length];

    for (int i = 0; i < wordList.length; i++) {
        wordList[i] = "";
        for (int n = 0; n < word.length; n++) {
            wordList[i] = wordList[i] + "" + binaryList[n][i];

        }
        if(i%10==0){
        System.out.println(wordList[i]);}
    }

    return wordList;
}

Main method:

    public class Launch {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) throws NoSuchAlgorithmException, IOException {

    File dictionary = new File("Dictionary");

    DictionaryBuilder build = new DictionaryBuilder();
    File x = build.createHashDictionary(dictionary);

   Scanner in = new Scanner(x);
   System.out.println(in.nextLine());


}

It's stuck on "Antidisestablishmentarian." Can I streamline this?

I'll try to write a full answer later, but if you're specifically worried about the speed of generating the variants then you could look into Gray codes. — Peter Taylor
– Peter Taylor, Commented Feb 24, 2016 at 8:28
i have tried antidiseastablismnetarianism by its self... Problem is hat there are somewhere around 2^25 possible options for upper and lowercase..... (i doubt i spelled it right here) — R.Hull
– R.Hull, Commented Feb 24, 2016 at 16:43
@greybeard i dont understand what your asking,, my thoughts are that since its either upper or lowercase, its the same as on/off or binary, so i just took the word length, got the possible permutations, and attempt to generate all of them using a similar method i was taught when learning binary — R.Hull
– R.Hull, Commented Feb 24, 2016 at 16:47
(previous comment/formatting screwed up (hey, I remember how!) - sorry, next try:) (Why did you place this question in Code Review? There is no code to improve, there are fundamental assumptions (insights?) to get right - does at least as well on SE and properly presented at CS.) looked a lot like counting in binary - great. Now, what does take a significant amount of time? Can you re-use the result of one time-consuming step? What if you could? (Think about the S in SHA and what cryptographic hash functions are used for/dreamt up to be.) — greybeard
– greybeard, Commented Feb 24, 2016 at 20:21

vnp · Accepted Answer · 2016-02-24 19:35:54Z

You are absolutely correct - it is binary counting. In the case of antidiseastablismnetarianism you'd need to produce \$2^{28}\$ words, that is quite a few. No surprise you are stuck, but unfortunately there is no real way around.

You may streamline the word generation a bit (most likely it wouldn't affect the bottom line) by doing a more natural binary counting. For example,

    int length = 1 << word.length;

    for (int counter = 0; counter < length; ++counter) {
        for (int pos = 0; pos < word.length; ++pos) {
            binaryList[pos][counter] = (counter & (1 << pos))?
                toUpper(word[pos]): toLower(word[pos]);
        }
    }

Peter Taylor · Accepted Answer · 2016-02-25 09:38:35Z

        for (int i = 0; i < wordList.length; i++) {
            out.println(wordList[i]);
        }

It's generally good style to use foreach-style loops where possible, because they're slightly less verbose (and hence easier to read) and they eliminate some classes of error.

    int length = (int) (Math.pow(2, _word.length()));

Bit shifting is a more idiomatic way of doing this.

    char[][] binaryList = new char[word.length][length];

As I understand your approach (which needs some comments to explain it better), the indices are the right way around for the first pass, but the second pass transposes the table. An approach based on transposition of a large 2D array can never have good cache coherence. As I hinted in a comment, a faster approach which makes minimal changes is based on Gray codes.

    for (int i = 0; i < wordList.length; i++) {
        wordList[i] = "";
        for (int n = 0; n < word.length; n++) {
            wordList[i] = wordList[i] + "" + binaryList[n][i];

        }
        if(i%10==0){
        System.out.println(wordList[i]);}
    }

This code is not ready for review. Ditch the debugging code and sort out the basic formatting first.

However, in addition I would like to point out that

        for (int n = 0; n < word.length; n++) {
            wordList[i] = wordList[i] + "" + binaryList[n][i];
        }

is just plain wrong. It turns a linear operation into a quadratic one through looped copying.

The fast approach here, using Gray codes, would look something like:

public String[] getSmallWordList(String _word) {
    char[] word = _word.toCharArray();

    int length = 1 << word.length;

    String wordList[] = new String[length];

    for (int i = 0; i < wordList.length; i++) {
        // TODO Gray code update goes here, and toggles the case of precisely one character

        wordList[i] = new String(word);
    }

    return wordList;
}

Stack Exchange Network

Dictionary algorithm, computing all case options

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Dictionary algorithm, computing all case options

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions