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

UVA: 10132 - File Fragmentation

Background- We got to recover a file which has got fragmented some how. Again I preferred C++ STL to do pattern matching and it has given me my best timing of 0.008 sec. Though the implementation looks a bit heavier but it is quite fast.
              The idea here is to chose 2 pair of fragments who can reveal the correct file. If we some length of all fragments we can get file size.  

1. Hash all the fragments based on the size.
2. List the keys having sum = size      
3. Now chose possible unique pair carefully.
4. Now we can construct the file but we running one information short i.e. order of fragments i.e file = part1+part2 or part2+part1
5. #4 is been solved using decision table, like below

C++ Implementation -

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

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

using namespace std;
typedef pair<short, string>  Data;
typedef multimap<short, string> Hash;
typedef    pair<Hash::iterator, Hash::iterator> Range;

stringstream tokens(stringstream::in | stringstream::out);

string second(const Data & word) {
    return word.second;    
}

short first(const Data & word) {
    return word.first;    
}
bool Compare (const Data& i, const Data& j) {
  return (i.second == j.second);
}

struct Count {
  short operator()(short x, const Data& v) const { return x + 1; }
  short operator()(const Data& v, short x) const { return x + 1; }
};

struct Summer {
  short operator()(short x, const Data& v) const { return x + v.first; }
  short operator()(const Data& v, short x) const { return x + v.first; }
};

short find_unique_fregments(Hash& fregments, Range& range) {
    short min = numeric_limits<short>::max();
    for(Hash::const_iterator it = fregments.begin(); it != fregments.end();) {
        Range r = fregments.equal_range(it->first);
        short total = accumulate(r.first, r.second, 0, Count());
        if(total <= 2) {
            range = r;
            return total;
        } else if (total < min) {
            min = total;
            range = r;
        }
        it = r.second;
    }
    return min;    
}

void recover(Hash& fregments, string& file) {
    if(fregments.size() == 2) {
        Hash::iterator it = fregments.begin();
        file = it->second;
        file += (++it)->second;
        return;
    }
    
    short no_of_file = fregments.size() /2 ;
    short file_size = (accumulate(fregments.begin(), fregments.end(), 0, Summer())) / no_of_file;
    Range part1;
    short count = find_unique_fregments(fregments, part1);
    
    if(count == fregments.size()) {
        file = part1.first->second;
        while(++(part1.first) != part1.second && part1.first->second == file);
        if(part1.first != part1.second) file += part1.first->second;
        else file+=file;
        return;
    }

    vector<Data> head;
    unique_copy(part1.first, part1.second, back_inserter(head), Compare);
    Range part2 = fregments.equal_range(abs(file_size - part1.first->first));
    vector<Data> tail;
    unique_copy(part2.first, part2.second, back_inserter(tail), Compare);

    map<string, short> decision_table;
    map<string, short>::iterator it;
    string permutation;
    string reverse;
    
    if (head.size() == 1) {
        permutation = head.begin()->second + tail.begin()->second;
        reverse = tail.begin()->second + head.begin()->second;
        if(permutation == reverse) {
            file = permutation;
            return;
        } else {
            decision_table.insert(decision_table.end(), make_pair(permutation, 1));
            decision_table.insert(decision_table.end(), make_pair(reverse, 1));
            Hash::iterator one; 
            if(part1.first != fregments.begin())
                one = fregments.begin();
            else
                one = fregments.upper_bound (fregments.begin()->first);
            Range range = fregments.equal_range(file_size - one->first);
            for(Hash::iterator two = range.first; two != range.second; two++) {
                permutation = one->second + two->second;
                reverse = two->second + one->second;
                if(decision_table.find(permutation) != decision_table.end()) {
                    file = permutation;
                    return;
                } else if(decision_table.find(reverse) != decision_table.end()) {
                    file = reverse;
                    return;
                }
            } 
        }
    } else {
        short loop_count = 2;
        vector<Data>::iterator one = head.begin();
        while (one != head.end() && loop_count-- > 0) {
            vector<Data>::iterator two = tail.begin();
            while (two != tail.end()) {
                permutation = one->second + two->second;
                it = decision_table.find(permutation);
                if(it != decision_table.end()) {
                    file = permutation; return;
                } else {
                    decision_table.insert(it, make_pair(permutation, 1));
                }
                // insert reverse 
                reverse = two->second + one->second;
                if( permutation != reverse) {
                    it = decision_table.find(reverse);
                    if(it != decision_table.end()) {
                        file = reverse; return;
                    } else {
                        decision_table.insert(it, make_pair(reverse, 1));
                    }
                }
                two++;
            }
            one++;
        }
    }
    // decision can not be made chose any one 
    file = decision_table.begin()->first;
}

/* main
 *  * */
int main() {
    short testcases  = 0;
    cin >> testcases;
    _SKIP_LINE_;
    _SKIP_LINE_;
    string line;
    string word;
    Hash fregments;
    string file;
    file.resize(256);
    while(testcases-- > 0 && cin.eof() != true) {
        while(true) {
            tokens.clear();
            getline(cin, line);
            tokens << line;
            if(cin.eof() == true || (line.find_first_not_of(" \r") == string::npos)) break;
            tokens >> word;
            fregments.insert(fregments.end(), make_pair(word.size(), word));
        }
        if(fregments.size() > 0 && (fregments.size() & 0x01) == 0) {
            recover(fregments, file);
            cout << file << endl;
            if(testcases > 0)
                cout << endl;
        }
        file.clear();
        fregments.clear();
    }
    return 0;
}

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 - 

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

UVA: 10010 - Where's Waldorf?

Background- We got to do 8-way searching in a grid here. Obviously 8-way recursion was choice here but I preferred hashing the grid first because judges inputs are doing multiple search on the same grid. Since there are n search on the same grid so it is better to hash all letters position in the grid O(n)  operation which are starting positions for search. This has 0.012 sec of timing on UVA judges input. Certainly 8-way recursion will cost more. 

C Implementation - 

#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <stdio.h>
#include <string.h>
using namespace std;
#define _SKIP_LINE_ do{scanf("%*[^\n]"); getc(stdin);}while(0)
const short size = 50;
char GRID[size+1][size+2];
short M, N, W;
vector<string> words;
typedef pair<short, short> Pos;

struct Compare {
  bool operator() (const Pos& lhs, const Pos& rhs) const {
      if(lhs.first == rhs.first)
          return lhs.second < rhs.second;
      else return lhs.first < rhs.first;
  }
};

typedef set<Pos, Compare> Positions;

map<char, Positions> Hash;

void print() {
    for(short i = 1; i <= M; ++i) {    
        for(short j = 1; j <= N; ++j)
            cout << GRID[i][j];
        cout << endl;
    }
    copy(words.begin(), words.end(), ostream_iterator<string>(cout, "\n")); 
}

void Search(const string& word) {
    Positions::const_iterator p = Hash[word[0]].begin();
    Positions::const_iterator end = Hash[word[0]].end();
    Positions::const_iterator prev = end;
    short n = word.size();
    const char* w = word.c_str();
    short x = 0;
    short r = 0;
    short c = 0;
    while(p != prev && p != end) {
        const short i = p->first;
        const short j = p->second;
        prev = p;
        switch(1) {
            // right
            case 1:
                if(j+n-1 <= N && strncmp(GRID[i]+j, w, n) == 0)  
                    break;
            // left
            case 2:
                if(j-n+1 >= 1) {  
                    for(c=j, x=0; c > 0 && x < n; --c,++x) 
                        if(GRID[i][c] != w[x]) 
                            break;
                    if(x == n) break;
                }
            // down
            case 3:
                if(i+n-1 <= M) { 
                    for(r=i, x=0; r < i+n; ++r, ++x) 
                        if(GRID[r][j] != w[x]) 
                            break;
                    if(x == n) break;
                }
            // up
            case 4:
                if(i-n+1 >= 1) { 
                    for(r=i, x=0; r > 0 && x < n; --r, ++x) 
                        if(GRID[r][j] != w[x]) 
                            break;
                    if(x == n) break;
                }
            // up right digonal
            case 5:
                if(i-n+1 >= 1 &&  j+n-1 <= N) { 
                    for(r=i, c=j, x=0; r > 0 && c < j+n; --r, ++c, ++x) 
                        if(GRID[r][c] != w[x]) 
                            break;
                    if(x == n) break;
                }
            // down right digonal
            case 6:
                if(i+n-1 <= M &&  j+n-1 <= N) {
                    for(r=i, c=j, x=0; r < i+n && c < j+n; ++r, ++c, ++x) 
                        if(GRID[r][c] != w[c-j]) 
                            break;
                    if(x == n) break;
                }
            // up left digonal
            case 7:
                if(i-n+1 >= 1 &&  j-n+1 >= 1) { 
                    for(r=i, c=j, x=0; r > 0 && c > 0 && x < n; --r, --c, ++x) 
                        if(GRID[r][c] != w[x]) 
                            break;
                    if(x == n) break;
                }
            // down left digonal
            case 8:
                if(i+n-1 <= M &&  j-n+1 >= 1) { 
                    for(r=i, c=j, x=0; r < i+n && c > 0; ++r, --c, ++x) 
                        if(GRID[r][c] != w[r-i]) 
                            break;
                    if(x == n) break;
                }
            default:
                ++p;
        }
    }
    if(p == end) 
        cout << 0 << " " << 0 << endl;
    else 
        cout << p->first << " " << p->second << endl;
}

/* main
 *  * */
int main() {
    short test_cases  = 0;
    cin >> test_cases;
    while(test_cases > 0 && cin.eof() != true) {
        cin >> M >> N;
        _SKIP_LINE_;
        Hash.clear();
        // READ and Hash GRID
        for(short r=1; r <= M; ++r) {
            for(short c=1; c <= N; ++c) {
                cin >> GRID[r][c];
                GRID[r][c] = ::tolower(GRID[r][c]);
                Hash[GRID[r][c]].insert(make_pair(r, c));
            }
            GRID[r][N+1] = '\0';
            _SKIP_LINE_;
        }
        // READ WORD
        cin >> W;
        _SKIP_LINE_;
        words.clear();
        words.resize(W);
        for(short c=0; c < W; ++c) {
            getline(cin, words[c]);
            transform(words[c].begin(), words[c].end(), words[c].begin(), ::tolower);
        }
        for_each(words.begin(), words.end(), Search);    
        if(--test_cases > 0)
            cout << endl;
    }
    return 0;
}