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;
}