These notes have been written specifically for my CS302 lecture on enumeration, so they are best read within that context.
Overview: Don't read the lengthy problem description yet.
This problem gives you an encrypted string, and a function for encrypting and decrypting given a password, which is itself a three-letter string. However, you are not given the password. The problem description gives you a way to say that decryption is successful. Your job is to to furnish the password that decrypts the string.
The way to solve this problem is to enumerate all possible passwords, and then test to see which of the possible ones decrypts successfully. Here, n is 26 (passwords are composed of lower-case letters) and l is three. Thus, there are 263 = 17576 potential passwords. That's a pretty small number, so we should be able to perform the enumeration quickly.
Solution: Ok, now that I've given you an overview, let's solve the problem. Go ahead and read it from the link above. You are given a parameter cipherText which is a string of 3 to 50 characters that contains only lowercase letters and spaces. You are to discover a password, which is a three-letter string containing only lowercase letters, that would generate the cipherText from a legal clear text string. What is a legal clear text string? It is one composed of words and spaces, where words are contiguous lowercase letters between 2 and 8 characters in size that contain at least one vowel. Words are always separated by a single space. When you discover the password, you are to return the clear text.
To generate cipherText from clear text, you associate each potential character c in the clear text with a number. That number is (c-'a'+1) if c is a lowercase letter, and 0 if c is a space. To generate the first character of cipherText, you add the first character of the clear text to the first letter of the password, take the result modulo 27 and convert the number back to a character. To generate the second character of cipherText, you add the second character of the clear text to the second letter of the password, take the result modulo 27 and convert the number back to a character. Keep doing this, and when you run out of password letters, start back at the beginning.
Thus, for example, if the clear text is "a bee" and the password is "abz", then the cipherText will be calculated with the following table:
| i | clear_text[i] | password[i%3] | ciphertext[i] |
| 0 | 'a' = 1 | 'a' = 1 | 2 = 'b' |
| 1 | ' ' = 0 | 'b' = 2 | 2 = 'b' |
| 2 | 'b' = 2 | 'z' = 26 | 28%27=1 = 'a' |
| 3 | 'e' = 5 | 'a' = 1 | 6 = 'f' |
| 3 | 'e' = 5 | 'b' = 2 | 7 = 'g' |
So, the ciphertext will be "bbafg".
Armed with this information, what we want to do is generate all 17576 potential passwords, and for each password, we decrypt the message and test whether it corresponds to legal clear text. If so, we return the clear text. The problem description says that we are guaranteed that there will be one unique password that generates legal clear text, and that makes our life simpler. We'll generate the passwords using the exact same technique as in divmod.cpp in the CS302 lectures on enumeration. Here's a solution in Solution.cpp:
class SimpleRotationDecoder {
public:
string decode(string cipherText);
int is_legal();
string cleartext;
};
string SimpleRotationDecoder::decode(string ciphertext)
{
string password;
string rv;
int i, j, k;
/* Initialize password and cleartext.
Convert all spaces in ciphertext to 'a'-1. */
password.resize(3);
cleartext.resize(ciphertext.size()+1, 'a'-1);
for (i = 0; i < ciphertext.size(); i++) {
if (ciphertext[i] == ' ') ciphertext[i] = 'a'-1;
}
/* Next, enumerate all three-letter passwords */
for (i = 0; i < 26*26*26; i++) {
j = i;
for (k = 0; k < 3; k++) {
password[k] = 'a' + (j%26);
j /= 26;
}
/* Use the password to decipher "ciphertext" into "cleartext" */
for (j = 0; j < ciphertext.size(); j++) {
k = (ciphertext[j]-('a'-1)) - (password[j%3]-('a'-1));
if (k < 0) k += 27;
k += ('a'-1);
cleartext[j] = k;
}
/* If the cleartext is legal, convert 'a'-1 back to spaces,
remove that extra space at the end, and return the cleartext. */
if (is_legal()) {
cleartext.resize(cleartext.size()-1);
for (i = 0; i < cleartext.size(); i++) {
if (cleartext[i] == 'a'-1) cleartext[i] = ' ';
}
return cleartext;
}
}
/* Return the empty string if you have failed. */
return "";
}
|
A few things about this code. First, we change all spaces to the character ('a'-1) (it's a backquote). That way, we don't have to special-case the space, and we can simply add/subtract characters.
Second, we sentinelize cleartext with a backquote at the end. It makes our life easier writing is_legal().
Third, we perform the decryption calculation using an integer k rather than a big arithmetic calculation on chars. That's because I don't want to worry about being constrained to a single char in the calculation.
When we find a legal clear text, we have to convert those backquotes back into spaces, remove the sentinel, and return it.
Now, look at is_legal():
/* This method tests to see if the string "cleartext" is legal, according to
the topcoder definition of legal. You should note first that I have changed
spaces to 'a'-1, because then I don't have to put special case in to recognize
spaces. Also, you should note that I have put an extra space at the end of the
string, again to reduce the amount of special code that I have to write. That
is a version of using a sentinel. */
int SimpleRotationDecoder::is_legal()
{
string vowels = "aeiou";
int i, last_space, vowel_present;
last_space = -1;
vowel_present = 0;
for (i = 0; i < cleartext.size(); i++) {
if (cleartext[i] == 'a'-1) {
if (i-last_space <= 2 || !vowel_present) return 0;
last_space = i;
vowel_present = 0;
} else {
if (vowels.find(cleartext[i]) != string::npos) vowel_present = 1;
if (i-last_space > 8) return 0;
}
}
return 1;
}
|
It is straightforward code, but note how the sentinel and the use of last_space helps us, since we don't have to test explicitly that the first and last characters are lowercase letters. Also, note how I use the find() method of strings to test whether the character is a vowel.
Compile, test, submit!