While this looks like a duplicate of the Crypt Kicker Problem , it is not.
I solved the problem, but I'm not all together, which is satisfied with my solution. Problem Operator:
A common but unsafe method of encrypting text is to rearrange the letters of the alphabet. In other words, each letter of the alphabet is successively replaced by another letter in the text. To ensure that encryption is reversible, no two letters are replaced with a single letter.
Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of substitutions and that all words in the decrypted text are dictionaries of known words.
entrance
The input consists of a string containing an integer n, followed by n lowercase words, one per line, in alphabetical order. These n words make up a dictionary of words that can be displayed in decrypted text. After the dictionary there are several lines of input. Each line is encrypted as described above.
The dictionary contains no more than 1000 words. Not a single word exceeds 16 letters. Encrypted strings contain only lowercase letters and spaces and do not exceed 80 characters.
Exit
Decrypt each line and print it to standard output. If there are several solutions, anyone will do. If there is no solution, replace each letter of the alphabet with an asterisk.
Input example
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
Output example
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******
I rudely caused the problem: I translated the dictionary into a set of length. Then I did a recursive brute force, where I tried every possible substitution based on the word length and returned if there was no match. This works, but I am very unhappy with the solution. I may just be obsessed, but there seems to be a more elegant way to solve the problem. My code is below:
#include<iostream> #include<algorithm> #include<vector> #include<sstream> #include<string> #include<map> #include<set> using namespace std; bool Find(vector<set<string > > &dict,vector<string> &line, map<char,char> &dec,int spot){ //Check that the end of the line hasn't been reached if(spot<line.size()){ //Get the size of the current word int sSize=line[spot].size(); string cand; cand.resize(sSize,'A'); //Attempt to decode the current word for(int i=0;i<sSize;i++){ if(dec.find(line[spot][i])!=dec.end()) cand[i]=dec[line[spot][i]]; } //Check all strings in the dictionary of the current length for(set<string>::iterator it=dict[sSize].begin();it!=dict[sSize].end();it++){ bool notMatch=false; for(int i=0;i<sSize;i++) //A is used to signify an undecoded character, this if says if the character was // decoded and it does not equal to corresponding character in the word, it not a match if(cand[i]!='A'&&cand[i]!=(*it)[i]) notMatch=true; if(notMatch) continue; for(int i=0;i<sSize;i++) //if it is a feasible match, then add the learned characters to the decoder if(cand[i]=='A') dec.insert(pair<char,char> (line[spot][i],(*it)[i])); //Keep decoding if(Find(dict,line,dec,spot+1)) return true; //If decoding failed, then remove added characters for(int i=0;i<sSize;i++) if(cand[i]=='A') dec.erase(line[spot][i]); } if(spot==0){ //This means no solution was found, fill decoder with a map to astericks string b="qwertyuiopasdfghjklzxcvbnm"; for(int i=0;i<b.size();i++) dec.insert(pair<char,char> (b[i],'*')); } return false; } return true; } int main(){ int size; cin >> size; vector<set<string> > dict; dict.resize(17); string grab; for(int i=0;i<size;i++){ //Bucket dictionary cin >> grab; dict[grab.size()].insert(grab); } while(getline(cin,grab)){ stringstream in(stringstream::in |stringstream::out); in << grab; vector<string> line; while(in >> grab) line.push_back(grab); map<char,char> dec; Find(dict,line,dec,0); for(int i=0;i<line.size();i++){ for(int j=0;j<line[i].size();j++) cout << dec[line[i][j]]; if(i!=line.size()-1) cout << " "; else cout << endl; } } }
Also, I'm not particularly interested in solutions that won't work in C ++. Just because this is the language I work with in the programming contest, so I am limited to its solution to these problems. I also know that there are many stylistic and secondary things that I could do differently that do not bother me too much, I miss one or two breaks. Basically, I'm just wondering if there is a simpler solution, or if my implementation complicates the situation too much. Thanks.