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.
Problem Statement:
Examples:
Solution: Ok, now that I've given you an overview, let's solve the problem. You are given a parameter cipherText which is the encrypted string, and we are to return the clearText string that can encode to it with some password.
Our strategy is a simple enumeration of passwords. How many of those are there? 26*26*26 = 17576. 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!