Crypt Kicker Algorithm and Solution, what went wro

问题:

Problem Description:

Crypt kicker algorithm is a well-known encryption algorithm but less secure. This UVa problem is to decrypt lines based on this method. The problem statement is as follows:

843 Crypt Kicker

A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter. Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

Input

The input consists of a line containing an integer n, followed by n lower case words, one per line, in alphabetical order. These n words comprise the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above. There are no more than 1000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.

Output

Decrypt each line and print it to standard output. If there is more than one solution, any will do. If there is no solution, replace every letter of the alphabet by an asterisk.

Sample Input

6 and dick jane puff spot yertle bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

Sample Output

dick and jane and puff and spot and yertle

**** * **** * **** * **** * ******

What went wrong?

I had created a Java code to solve it. The algorithm I used is illustrated below. The code seems to be correct. It passes all test cases I had fed to it including uDebug test cases. However, when submitting my code to UVA online judge, it always returns me WRONG ANSWER verdict! Can anyone identify my problem? Does the code have a hidden flaw? or it is the online judge problem?!

Any Help is Highly HIGHLY Appreciated!

Algorithm description:

A first idea coming in mind to solve this problem is to permute all the letters in the alphabet in order to find a mapping. However, this solution is computationally huge. A better Idea is to use backtracking. You map an encrypted word to a dictionary word which has the same length and pattern as the encrypted word. [ to show what word patterns means: 'abc' might be mapped to 'her' however, it cannot be mapped to 'see' as the pattern is dissimilar " three distinct letters word cannot be mapped to two distinct letters word" I took this beautiful idea from this discussion ]. If you find a mapping to this first word, then move to the next word and map it. If the second word did not have a solution then go back to the first word and try another mapping and so on. If there is no suitable mapping to the first word, then declare no solution. For the mapping, I mapped longest words first as they are harder to map.

The code:

Here is my code. I tried to comment out important lines. However, if you find any confusion just ask and I will explain with full details. Thanks,

import java.util.*;

public class P843 {
public static void main(String[] args) {

    Scanner c = new Scanner(System.in);
    int dictionarySize = c.nextInt();
    c.nextLine();

    // get the dictionary from the input stream:
    String[] words = new String[dictionarySize];
    for (int i = 0; i < words.length; i++)
        words[i] = c.nextLine();

    // get encrypted input
    String line = c.nextLine();
    while (c.hasNextLine()) {
        if (line.length() == 0) {
            System.out.println();
            line = c.nextLine();
            continue;
        }
        ArrayList<String> eWordsList = new ArrayList<>();
        for(String eWord : line.split(" "))
            if(eWord.length() != 0)
                eWordsList.add(eWord);
        String[] eWords = eWordsList.toArray(new String[0]);

        String[] dWords = decryptWords(eWords, words);
        for (int i = 0; i < dWords.length; i++)
            if (i != dWords.length - 1)
                System.out.print(dWords[i] + " ");
            else
                System.out.println(dWords[i]);

        line = c.nextLine();

    }

}

private static String[] decryptWords(String[] eWords, String[] words) {

    String[] dWords = new String[eWords.length];

    // get copy of the dWords so that the original version not destroyed
    String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);
    // sort by length from the greatest to the smallest
    Arrays.sort(eWordsCopy, new Comparator<String>() {
        @Override
        public int compare(String w1, String w2) {
            return Integer.compare(w2.length(), w1.length());
        }
    });

    // initialize a key array to hold decrypted letters:
    char[][] keyArray = new char[2][26];
    for (int i = 0; i < 26; i++) {
        keyArray[0][i] = (char) ('a' + i);
        keyArray[1][i] = '*';
    }


    // restore keyArray original values if there is no solution to all words
    if (!matchWords(words, eWordsCopy, keyArray))
        for (int i = 0; i < 26; i++) {
            keyArray[0][i] = (char) ('a' + i);
            keyArray[1][i] = '*';
        }
    for (int i = 0; i < eWords.length; i++) {
        StringBuilder temp = new StringBuilder();
        for (int j = 0; j < eWords[i].length(); j++)
            temp.append(keyArray[1][eWords[i].charAt(j) - 97]);
        dWords[i] = temp.toString();
    }
    return dWords;
}

private static boolean matchWords(String[] words, String[] eWords, char[][] keyArray) {
    ArrayList<String> promisingWords = new ArrayList<>();
    String eWord = eWords[0];

    // store the current state of keyArray
    char[][] originalKeyArray = new char[2][26];
    for (int i = 0; i < keyArray.length; i++)
        if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);
    // get promising words that may match
    for (String word : words)
        if (word.length() == eWord.length()
                && wordPattern(word).equals(wordPattern(eWord)))
            promisingWords.add(word);

    for (String word : promisingWords) {
        if (mapWord(eWord, word, keyArray)) {
            if (eWords.length > 1) {
                // recursive call:
                if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
                    return true;
                else {
                    // remove the word from the dictionary to try another one
                    for (int i = 0; i < keyArray.length; i++)
                        if (keyArray[i].length >= 0)
                            System.arraycopy(originalKeyArray[i], 0, keyArray[i], 0, keyArray[i].length);
                }
            }
            // if there are now decrypted words, then return true
            else
                return true;
        }
    }
    // if there is no word mapped, then return false
    return false;
}

private static boolean mapWord(String eWord, String word, char[][] keyArray) {
    // store the current state of keyArray
    char[][] originalKeyArray = new char[2][26];
    for (int i = 0; i < keyArray.length; i++)
        if (keyArray[i].length >= 0) System.arraycopy(keyArray[i], 0, originalKeyArray[i], 0, keyArray[i].length);

    // check one-to-one from the decrypted word to the dictionary word:
    for (int i = 0; i < eWord.length(); i++)
        if ((keyArray[1][eWord.charAt(i) - 97] != word.charAt(i)
                && keyArray[1][eWord.charAt(i) - 97] != '*')
                || !isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray)) {
            // restore original array back
            for (int j = 0; j < keyArray.length; j++)
                if (keyArray[j].length >= 0)
                    System.arraycopy(originalKeyArray[j], 0, keyArray[j], 0, keyArray[j].length);
            return false;
        }

        // update the key array:
        else
            keyArray[1][eWord.charAt(i) - 97] = word.charAt(i);

    return true;
}

private static boolean isLetterMapped(char eLetter, char letter, char[][] keyArray) {
    for (int i = 0; i < 26; i++)
        if (keyArray[1][i] == letter && keyArray[0][i] != eLetter)
            return false;
    return true;
}

// generate a word pattern
private static String wordPattern(String word) {
    if (word.length() > 0) {
        StringBuilder mapped = new StringBuilder();
        int count = 0;
        HashMap<Character, Character> mapping = new HashMap<>();
        for (int i = 0; i < word.length(); i++)
            if (!mapping.containsKey(word.charAt(i)))
                mapping.put(word.charAt(i), (char) (48 + count++));
        for (int i = 0; i < word.length(); i++)
            mapped.append(mapping.get(word.charAt(i)));
        return mapped.toString();
    } else {
        return "";
    }
}
}

回答1:

The primary problem appears to be that your program fails to decrypt (or do anything with) the last line of input. This happens because the loop condition c.hasNextLine() is evaluated after you've already read the line you're going to work on in that iteration of the loop.

Additionally, I observe that you have solved a different problem than the challenge presents, albeit a closely related one. You are supposed to

Decrypt each line

(emphasis added), but what you actually do is decrypt the words of each line. The input description does not promise that the encrypted lines will be without leading or trailing whitespace, or that there will not be more than one space between adjacent words. If any of those occur, then your program does not reproduce them in its output.

Furthermore, although I am inclined to take the problem description to mean that the the dictionary words are alone on their lines, without any leading or trailing whitespace, if that were not actually the case then your approach to reading them would include the spaces with them. It would be easy to protect against that by just trim()ing each on input.

My largest stylistic criticism is this: do not omit braces around the bodies of loops or if or else blocks, even when those bodies consist of only one statement. Doing so makes your code harder to read, and lays a trap for future maintainers, including future you. Such omissions have been the cause of at least one high-profile security issue within the last couple of years.

回答2:

With the help of @John Bollinger, The problem finally get resolved and accepted. Refer to his answer above for for more details about my silly error :( in the code.

I am now posting the final version of the code here. Improvements made include the following:

• Fixing the error while reading from the input stream.
• Changing the keyArray from 2D array to 1D array.
• Beautify the code more by adding curly braces and commenting more lines.

The code is here:

import java.util.*;

public class P843 {
    public static void main(String[] args) {

        Scanner c = new Scanner(System.in);
        int dictionarySize = c.nextInt();

        // this line is to flush out the input stream
        c.nextLine();

        // get the dictionary from the input stream:
        String[] words = new String[dictionarySize];
        for (int i = 0; i < words.length; i++) {
            words[i] = c.nextLine();
            // remove white spaces surrounding dictionary words if there is any
            words[i] = words[i].trim();
        }

        // get encrypted input
        String line;
        while (c.hasNextLine()) {
            line = c.nextLine();
            if (line.length() == 0) {
                System.out.println();
                continue;
            }

            // remove whitespaces
            String[] eWords = line.split(" ");
            for (int i = 0; i < eWords.length; i++) {
                eWords[i] = eWords[i].trim();
            }

            // decrypt words:
            String[] dWords = decryptWords(eWords, words);

            // print the decrypted line
            for (int i = 0; i < dWords.length; i++) {
                if (i != dWords.length - 1) {
                    System.out.print(dWords[i] + " ");
                } else {
                    System.out.println(dWords[i]);
                }
            }
        }

    }

    private static String[] decryptWords(String[] eWords, String[] words) {

        String[] dWords = new String[eWords.length];

        // get copy of the dWords so that the original version not destroyed
        String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);

        // sort by length from the greatest to the smallest
        Arrays.sort(eWordsCopy, new Comparator<String>() {
            @Override
            public int compare(String w1, String w2) {
                return Integer.compare(w2.length(), w1.length());
            }
        });

        // initialize a key array to hold decrypted letters:
        // for example: 'a' would be mapped to keyArray[0] and 'z' would be mapped to keyArray[25]
        char[] keyArray = new char[26];
        for (int i = 0; i < 26; i++) {
            // initialize the keyArray to '*'
            keyArray[i] = '*';
        }


        // restore keyArray original values if there is no solution to all words
        if (!matchWords(words, eWordsCopy, keyArray)) {
            for (int i = 0; i < 26; i++) {
                keyArray[i] = '*';
            }
        }

        // decrypt line using the mapping stored in keyArray
        for (int i = 0; i < eWords.length; i++) {
            StringBuilder temp = new StringBuilder();
            for (int j = 0; j < eWords[i].length(); j++) {
                temp.append(keyArray[eWords[i].charAt(j) - 97]);
            }
            dWords[i] = temp.toString();
        }
        return dWords;
    }

    private static boolean matchWords(String[] words, String[] eWords, char[] keyArray) {
        ArrayList<String> promisingWords = new ArrayList<>();
        String eWord = eWords[0];

        // store the current state of keyArray
        char[] originalKeyArray = new char[26];
        System.arraycopy(keyArray, 0, originalKeyArray, 0, originalKeyArray.length);

        // get promising words that may match
        for (String word : words) {
            if (word.length() == eWord.length()
                    && wordPattern(word).equals(wordPattern(eWord))) {
                promisingWords.add(word);
            }
        }

        for (String word : promisingWords) {
            if (mapWord(eWord, word, keyArray)) {
                if (eWords.length > 1) {
                    // recursive call:
                    if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
                        return true;
                    else {
                        // remove the word from the dictionary [by restoring the keyArray original values]
                        // and try another one
                        System.arraycopy(originalKeyArray, 0, keyArray, 0, keyArray.length);
                    }
                } else // if there is no more decrypted words, then return true
                    return true;
            }
        }
        // if there is no suitable mapping, return false
        return false;
    }

    private static boolean mapWord(String eWord, String word, char[] keyArray) {
        // store the current state of keyArray
        char[] originalKeyArray = new char[26];
        System.arraycopy(keyArray, 0, originalKeyArray, 0, keyArray.length);

        // check one-to-one from the decrypted word to the dictionary word:
        for (int i = 0; i < eWord.length(); i++) {
            if ((keyArray[eWord.charAt(i) - 97] != word.charAt(i)
                    && keyArray[eWord.charAt(i) - 97] != '*')
                    || !isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray)) {
                // restore original array back
                System.arraycopy(originalKeyArray, 0, keyArray, 0, keyArray.length);
                return false;
            }

            // update the key array:
            else {
                keyArray[eWord.charAt(i) - 97] = word.charAt(i);
            }
        }

        return true;
    }

    private static boolean isLetterMapped(char eLetter, char letter, char[] keyArray) {
        for (int i = 0; i < 26; i++) {
            if (keyArray[i] == letter && i != (eLetter - 97)) {
                return false;
            }
        }
        return true;
    }

    // generate a word pattern
    private static String wordPattern(String word) {
        if (word.length() > 0) {
            StringBuilder mapped = new StringBuilder();
            int count = 0;
            HashMap<Character, Character> mapping = new HashMap<>();
            for (int i = 0; i < word.length(); i++) {
                if (!mapping.containsKey(word.charAt(i))) {
                    mapping.put(word.charAt(i), (char) (48 + count++));
                }
            }
            for (int i = 0; i < word.length(); i++) {
                mapped.append(mapping.get(word.charAt(i)));
            }
            return mapped.toString();

        } else {
            return "";
        }
    }
}

If you are doing similar problems from this book, programming challenges book, using Java as your weapon, you are more than welcome to pass by and browse my repository where I am intending to put more solutions and tips.

Thanks