UVA: 850 Programming Challenges (Skiena & Revilla) Volume-3

UVA: 850 - Crypt Kicker II

Background- This is an example chosen plain text to break the  substitution cipher. It was easy to decode it. I chose c++ STL implementation, C implementation could be a little faster. It was a fun using STL algorithms to solve this problem. I managed to get  0.008 sec of timing with this. 

C++ Implementation -

#include <iostream>
#include <string>
#include <sstream>
#include <iterator>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <algorithm>
#include <functional>
#include <cctype>
#include <cstdlib>
#include <stdio.h>
#include <string.h>

using namespace std;

#define _SKIP_LINE_ do{scanf("%*[^\n]"); getc(stdin);}while(0)

char mapping[26];
string analogous[] = {"111", "11111", "11111", "111", "11111", "1111", "111" , "1111", "111"};
string chosen_text("the quick brown fox jumps over the lazy dog");
string no_output("No solution.");
stringstream tokens(stringstream::in | stringstream::out);

string analogous_code(const string& word) {
    string code;
    string::const_iterator w = word.begin();
    map<char, short> hash;
    map<char, short>::iterator it;
    while(w != word.end()) {
        it = hash.find(*w);
        if(it == hash.end()) {
            pair<char, short>p(*w, 1);
            hash.insert(hash.end(), p);
        } else {
            it->second++;
        }
        w++;
    }
    for(short i =0; i < word.size(); i++) {
            code += hash[word[i]]+'0';
    }
    return code;
}

static short decoded_char_count = 0;
bool MAP(const char& c, const char& p) {
    if(isspace(c) == false && mapping[c-'a'] == 0) {
        mapping[c-'a'] = p;
        decoded_char_count++;
    }
    return true;
}

struct decipher {
    decipher() {}
    char operator ()(const char& C) {
        return (isalpha(C) == false ? C : mapping[C-'a']);
    }
    string operator()(const string& C) {
        string P;
        transform(C.begin(), C.end(), back_inserter(P), decipher());
        return P;
    }
};

struct isAnalogous {
    bool operator()( const string& code, const string& analog) { 
        return (code == analog);
    }
};


struct predicate {
    bool operator()( char c ) { return isalpha(c) != 0; }
};

bool cryptanalysis(const vector<string>& cipher) {
    vector<string>::const_iterator it = cipher.begin();
    vector<string> codes;
    set<char> charset;
    while(it != cipher.end()) {
        if(it->size() != chosen_text.size()) {
            it++;
            continue;
        }
        charset.clear();
        copy(it->begin(), it->end(), inserter(charset, charset.end()));
        if(charset.size() != 27) {
            it++;
            continue;
        }
        tokens.clear();
        codes.clear();
        tokens << *it;
        transform(istream_iterator<string>(tokens), istream_iterator<string>(), back_inserter(codes), analogous_code);
        if(codes.size() == 9 && equal(codes.begin(), codes.end(), analogous, isAnalogous()) == true) {
            decoded_char_count = 0;
            equal(it->begin(), it->end(), chosen_text.begin(), MAP);
            if(decoded_char_count == 26)
                return true;
        }
        it++;    
    }
    return false;
} 

/* main
 *  * */
int main() {
    short test_cases  = 0;
    vector<string> cipher;
    string s;
    cin >> test_cases;
    _SKIP_LINE_;
    _SKIP_LINE_;
    while(test_cases > 0 && cin.eof() != true) {
        getline(cin, s);
        //s = s.substr(0, s.size()-1);
        short blankline = count_if(s.begin(), s.end(), predicate());
        if(blankline <= 0) continue;
        cipher.clear();
        memset(mapping, 0, 26);
        while(blankline > 0) {
            cipher.push_back(s);
            getline(cin, s);
            //s = s.substr(0, s.size()-1);
            blankline = count_if(s.begin(), s.end(), predicate());
        }
        if(cryptanalysis(cipher) == true)
            transform(cipher.begin(), cipher.end(), ostream_iterator<string>(cout, "\n"), decipher());
        else
            cout << no_output << endl;
        if(--test_cases > 0)
            cout << endl;
    }
    return 0;
}

If you know how to reduce the timing below this, Please do share -