Simple Suffix array and Calculating length of longest common prefix.

class SuffixArray {
    std::vector<std::string> suffixes;
    size_t N;
public:
    SuffixArray(std::string& s) {
        N = s.length();
        suffixes.resize(N);
        for (size_t i = 0; i < N; i++)
            suffixes[i] = s.substr(i);
        std::sort(suffixes.begin() , suffixes.end());
    }
    ~SuffixArray() {
    }
    size_t lcp(std::string& s, std::string& t) {
        size_t N = std::min(s.length(), t.length());
        for (size_t i = 0; i < N; i++)
            if (s[i] != t[i]) 
                return i;
        return N;
    }    
};
Advertisements

fill tool puzzle.

Following matrix is given

10001
10100
00000
00000
00111
00100
00100

With one click, the pixel fill tool turns each black pixel into a white one until there isn’t a black pixel that can be reached from the previous pixel. A pixel is connected with another one in up to eight ways: north, south, east, west and the four diagonals.

Following is my solution in C++.

#include <stdio.h>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <deque>

typedef std::vector<std::vector<bool> > table_t;


class Solver {
public:
    Solver(int H, int W): _height(H),
        _width(W),
        T(H, std::vector<bool>(W)),
        num_of_clicks(0){
    }
    ~Solver() {
    }
    void ReadFile(std::ifstream &ifs){
        int row = 0, col = 0;
        std::string file_line;
        while( ifs.good() ) {
            std::getline(ifs,file_line);
            for ( std::string::const_iterator it =  file_line.begin(); it != file_line.end(); ++it) {
                if ( *it - '0' == 1 ) {
                    T[row][col++] = true;
                } else {
                    T[row][col++] = false;
                }               
            }
            col = 0;
            row++;        
        }
        ifs.close();  
    }
    void solve() {
        for ( int row = 0; row < _height; ++row) {
            for ( int col = 0; col < _width; ++col) {
                if ( T[row][col]  == true )
                    continue;
                neighbours.clear();
                num_of_clicks++;
                neighbours.push_back(std::make_pair(row,col));
                while ( !neighbours.empty()) {
                    std::pair<int,int> elem = neighbours.front();
                    neighbours.pop_front();

                    int R = elem.first;
                    int C = elem.second;                    

                    west       (R, C);
                    east       (R, C);
                    north      (R, C);
                    south      (R, C);
                    north_west (R, C);
                    south_west (R, C);
                    south_east (R, C);
                    north_east (R, C);
                }
            } // colum loop ends here
        } // row loop ends here
        std::cout << num_of_clicks << std::endl;
    }
private:
    int _height;
    int _width;
    table_t T;
    std::deque<std::pair<int,int> > neighbours;
    int num_of_clicks;

    void west(int row, int col) {
        if ( col - 1 >= 0 && T[row][col - 1 ]  == false ) {
            T[row][col - 1 ]  = true;
            neighbours.push_back(std::make_pair(row, col - 1));
        }
    }

    void east(int row, int col) {
        if ( col + 1 < _width && T[row][col + 1 ] == false ) {
            T[row][col + 1 ] = true; 
            neighbours.push_back(std::make_pair(row, col + 1));
        }
    }

    void north(int row, int col) {
        if ( row - 1 >= 0 && T[row - 1][col] == false ) {
            T[row - 1][col] = true;
            neighbours.push_back(std::make_pair(row - 1, col));
        }
    }

    void south(int row, int col) {
        if ( row + 1 < _height && T[row + 1][col] == false ) {
            T[row + 1][col]= true;
            neighbours.push_back(std::make_pair(row + 1, col ));
        }
    }

    void north_west(int row, int col) {
        if (row - 1 >= 0 && col - 1 >= 0 &&
            T[row - 1][col - 1] == false ) {
                T[row - 1][col - 1] = true;
                neighbours.push_back(std::make_pair(row - 1, col -  1));
        }
    }

    void south_west(int row, int col) {
        if ( row + 1 < _height && col - 1 >= 0 &&
            T[row + 1][ col - 1] == false) {
                T[row + 1][ col - 1] = true;
                neighbours.push_back(std::make_pair(row + 1, col - 1));
        }
    }

    void south_east(int row, int col) {
        if ( row + 1 < _height && col + 1 < _width &&
            T[row + 1][col + 1] == false ){
                T[row + 1][col + 1] = true;
                neighbours.push_back(std::make_pair(row + 1, col + 1));
        }
    }

    void north_east(int row, int col) {
        if ( row - 1 >= 0 && col + 1 < _width &&
            T[row - 1][col + 1] == false ) {
                T[row - 1][col + 1] = true;
                neighbours.push_back(std::make_pair(row - 1, col + 1 ));
           
        }
    }
};

int main ( int argc, char **argv) {
    int H = 0;
    int W = 0;
    std::ifstream input(argv[1]);
    if ( input.peek() == EOF ) {
        return 1;
    }
    // Read the first line.
    std::string file_line; 
    std::getline(input,file_line);
    std::istringstream iss;
    iss.clear();
    iss.str(file_line);
    // Get the height and width of the image.
    iss >> H >> W;
    Solver s(H,W);
    s.ReadFile(input);
    s.solve();

    return 0;
}

Printing all paths between two nodes in a graph ( recursive method )

Graph is defined as follows

std::map<T, std::set<T> > graph;

Following is the way to print all the paths between two nodes in a graph.

template < class T>
void print_all_path(T src, T dest ) { 
    std::vector<T> visited;
    visited.push_back(src);
    compute_all_paths(visited,dest);
}
template < class T>
void print_all_path(T src, T dest ) { 
    std::vector<T> visited;
    visited.push_back(src);
    compute_all_paths(visited,dest);
}
template < class T>
void print_all_path(std::vector<T>& visited,  T dest ) {  
    T back           = visited.back();    
    std::set<T> adj_list = graph.find(back)->second;

    for ( std::set<T>::iterator itr = adj_list.begin();  itr != adj_list.end(); ++itr )  {  
        if ( std::find(visited.begin(), visited.end(), *itr) != visited.end())
            continue;
        if (*itr == dest) {
            visited.push_back( *itr );    
            std::copy(visited.begin(),visited.end(),std::ostream_iterator<T>(std::cout," "));
            std::cout << std::endl;  
            visited.erase( visited.begin() + (visited.size() - 1));    
            break;
        }
    }  
    for ( std::set<T>::iterator itr = adj_list.begin();  itr != adj_list.end();  itr++ )  {  
        if ( std::find(visited.begin(), visited.end(), *itr) != visited.end() || *itr == dest ) 
            continue;
        visited.push_back( *itr );    
        print_all_path(visited, dest );            
        visited.erase( visited.begin() + (visited.size() - 1));  
    }  
}  

N frequent item in a file.

You have given a file, consists of line, each line is a search string. Aim is to find top n frequent lines in the file. This problem should not be confused with the data stream data input i.e. online algorithms . In this question entire file is available for analysis.

#include <iostream>
#include <fstream>
#include <string>
#include <map>

typedef std::map<std::string, int> freq_table_t;
typedef std::multimap<std::size_t, freq_table_t::const_iterator> top_n_t;
size_t n = 5;

int main ( int argc, char **argv) {
    std::ifstream ifs(argv[1]);
    if ( ifs.peek() == EOF ) 
        return 1;

    std::string line; 
    freq_table_t freq_table;

    while( ifs.good()&& std::getline(ifs,line) ) {
        if ( freq_table.insert(std::make_pair(line, 1 )).second == false ) 
            freq_table[line]++;
    }
    ifs.close();

    top_n_t top5;
    for (freq_table_t::const_iterator it = freq_table.begin(); it != freq_table.end(); ++it) {
        if (top5.size() < n || it->second > top5.begin()->first)
            top5.insert(std::make_pair(it->second, it));
        if (top5.size() == n + 1)
            top5.erase(top5.begin());
    }
    for ( top_n_t::reverse_iterator ritr = top5.rbegin(); ritr != top5.rend(); ++ritr)
        std::cout << ritr->second->first << std::endl;

    return 0;
}

Disjoint-set data structure C++

In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set.
Union: Combine or merge two sets into a single set.

Because it supports these two operations, a disjoint-set data structure is sometimes called a union-find data structure or merge-find set. The other important operation, MakeSet, which makes a set containing only a given element (a singleton), is generally trivial. With these three operations, many practical partitioning problems can be solved. More details read here.

Following is my implementation for disjoint set data structure, which I used in solving lot of problem/puzzles.

class disjoint_sets {
    struct disjoint_set {
        size_t parent; 
        unsigned rank;
        disjoint_set(size_t i) : parent(i), rank(0) { }
    };
    std::vector<disjoint_set> forest;
public:
    disjoint_sets(size_t n){
        forest.reserve(n);
        for (size_t i=0; i<n; i++)
            forest.push_back(disjoint_set(i));
    }
    size_t find(size_t i){
        if (forest[i].parent == i)
            return i;
        else {
            forest[i].parent = find(forest[i].parent);
            return forest[i].parent;
        }
    }
    void merge(size_t i, size_t j) {
        size_t root_i = find(i);
        size_t root_j = find(j);
        if (root_i != root_j) {
            if (forest[root_i].rank < forest[root_j].rank)
                forest[root_i].parent = root_j;
            else if (forest[root_i].rank > forest[root_j].rank)
                forest[root_j].parent = root_i;
            else {
                forest[root_i].parent = root_j;
                forest[root_j].rank += 1;
            }
        }
    }
};

Two dimensional array processing using std::for_each

#include <vector>
#include <iostream>
#include <algorithm>
 
typedef std::vector<std::vector<short> > table_t;
 
struct process_col { 
      int row_index;
      int col_index;
      process_col(int r) : row_index(r), col_index(0){}
      void operator()(short & data) {
           std::cout << "Value at (" <<row_index <<"," << col_index << ") is " << data << std::endl; 
           col_index++;
      }
}; 
struct process_row {
      int row_index;
      process_row() : row_index(0){}
      void operator()(std::vector<short> & row){
         std::for_each(row.begin(), row.end(), process_col(row_index));
         row_index++;
      }
}; 
int main ( int argc , char **argv) {
    table_t t = table_t(5, std::vector<short>(5));
    int counter = 0;
    for (size_t row = 0; row < 5; ++row)
           for (size_t col = 0; col < 5; ++col)
               t[row][col] = counter++;
 
    std::for_each( t.begin(), t.end(), process_row());
    return 0;
}