Greplin Challenge.

Someone send me link of Greplin challenges. Interesting problems to solve. I have completed the same and got positive feedback from Greplin. Following are the problems in the challenge.

  • Embedded in this block of text is the password for level 2. The password is the longest substring that is the same in reverse. As an example, if the input was “I like racecars that go fast”  the password would be “racecar”.
  • write code to find the first prime  fibonacci number larger than a given minimum.  For example, the first prime fibonacci number larger than 10 is 13

  • you must find all subsets of an array where the largest number is the sum of the remaining numbers. For example, for an input of:  (1, 2, 3, 4, 6)  the subsets would be     1 + 2 = 3
        1 + 3 = 4
        2 + 4 = 6
        1 + 2 + 3 = 6

Solution and C++ code is posted on my github.

Advertisements

Sudoku solving solution in C++

The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, …, N}), so that each row, column and region contains exactly one of each element of the set. The puzzle can be solved using a variety of algorithms. Couple of solutions I referred are Here and excellent article by Peter Norvig can be found here. A completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any of the 9 blocks of contiguous 3×3 cells. The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.
I have solved the puzzle using C++, but I found another interesting solution which is done in only 3 lines. See Sudoku solver in three lines explained.
Program expect Sudoku puzzle grid in following format

000075400000000008080190000300001060000000034000068170204000603900000020530200000

where 0 represent the space to insert a new solution number.
Source Code:

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include "Timer.h"
bool same_row ( int row, int col ) {
    return ( (row / 9 )== (col / 9 ));
}
bool same_col(int row, int col ) {
    return (((row - col) % 9) == 0);
}
bool same_block(int row, int col) {
    return ( (((row/27) == (col/27)))&&(((row % 9)/3) == ((col % 9)/3)));
}
void solve_r(std::vector<int> data) {
    std::vector<int>::iterator found = std::find(data.begin(), data.end(), 0);
    if ( found == data.end()) {
        std::cout << "---+---+---+---+---+---+---+---+---+" << std::endl;
        int limit = 0;
        for ( std::vector<int>::iterator itr = data.begin(); itr != data.end(); ++itr) {
            std::cout << std::setw(3) << *itr  << "|" ;
            if ( limit == 8 ){
                std::cout << std::endl;
                std::cout << "---+---+---+---+---+---+---+---+---+" << std::endl;
                limit  = 0;
            } else {
                limit++;
            }
        }
        std::cout << std::endl << std::endl;
        return;
    }
    int i = (int)(found - data.begin());
    std::set<int> excluded_numbers;
    for ( int j = 0; j < 81; j++) {
        if ( same_row(i,j) || same_col(i,j) || same_block(i,j)) {
            excluded_numbers.insert(data[j]);
        }
    }
    for ( int m = 1; m <= 9; m++) {
        std::set<int>::iterator found = excluded_numbers.find(m);
        if ( found == excluded_numbers.end()) {
            data[i] = m;
            solve_r(data);
        }
    }
}
int main( int argc, char** argv) {
    std::ifstream inFile(argv[1]);
    if(!inFile) {
        exit ( 0 );
    }
    std::vector<int> data;
    std::string str = "";
    while(std::getline(inFile, str)) {
        data.clear();
        for ( std::string::iterator itr = str.begin(); itr != str.end(); ++itr) {
            std::string s;
            s.push_back(*itr);
            std::stringstream ss(s);
            int i = 0;
            ss >> i;
            data.push_back(i);
        }
        Timer t("Solving");
        solve_r(data);
        t.stop();
    }
}

Download code from Here
Ouput and Time taken for various size puzzles:
Solution for 45 number Suduku puzzle :
Input

001700509573024106800501002700295018009400305652800007465080071000159004908007053

Output:

avinash@avinash-laptop:~/work/suduko$ ./suduko 45.inp 
---+---+---+---+---+---+---+---+---+
  2|  4|  1|  7|  6|  8|  5|  3|  9|
---+---+---+---+---+---+---+---+---+
  5|  7|  3|  9|  2|  4|  1|  8|  6|
---+---+---+---+---+---+---+---+---+
  8|  9|  6|  5|  3|  1|  7|  4|  2|
---+---+---+---+---+---+---+---+---+
  7|  3|  4|  2|  9|  5|  6|  1|  8|
---+---+---+---+---+---+---+---+---+
  1|  8|  9|  4|  7|  6|  3|  2|  5|
---+---+---+---+---+---+---+---+---+
  6|  5|  2|  8|  1|  3|  4|  9|  7|
---+---+---+---+---+---+---+---+---+
  4|  6|  5|  3|  8|  2|  9|  7|  1|
---+---+---+---+---+---+---+---+---+
  3|  2|  7|  1|  5|  9|  8|  6|  4|
---+---+---+---+---+---+---+---+---+
  9|  1|  8|  6|  4|  7|  2|  5|  3|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s

avinash@avinash-laptop:~/work/suduko$ cat 40.inp 
096040001100060004504810390007950043030080000405023018010630059059070830003590007
avinash@avinash-laptop:~/work/suduko$ ./suduko 40.inp 
---+---+---+---+---+---+---+---+---+
  3|  9|  6|  2|  4|  5|  7|  8|  1|
---+---+---+---+---+---+---+---+---+
  1|  7|  8|  3|  6|  9|  5|  2|  4|
---+---+---+---+---+---+---+---+---+
  5|  2|  4|  8|  1|  7|  3|  9|  6|
---+---+---+---+---+---+---+---+---+
  2|  8|  7|  9|  5|  1|  6|  4|  3|
---+---+---+---+---+---+---+---+---+
  9|  3|  1|  4|  8|  6|  2|  7|  5|
---+---+---+---+---+---+---+---+---+
  4|  6|  5|  7|  2|  3|  9|  1|  8|
---+---+---+---+---+---+---+---+---+
  7|  1|  2|  6|  3|  8|  4|  5|  9|
---+---+---+---+---+---+---+---+---+
  6|  5|  9|  1|  7|  4|  8|  3|  2|
---+---+---+---+---+---+---+---+---+
  8|  4|  3|  5|  9|  2|  1|  6|  7|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s
avinash@avinash-laptop:~/work/suduko$ cat 35.inp 
290500007700000400004738012902003064800050070500067200309004005000080700087005109
avinash@avinash-laptop:~/work/suduko$ ./suduko 35.inp 
---+---+---+---+---+---+---+---+---+
  2|  9|  3|  5|  4|  1|  6|  8|  7|
---+---+---+---+---+---+---+---+---+
  7|  1|  8|  2|  9|  6|  4|  5|  3|
---+---+---+---+---+---+---+---+---+
  6|  5|  4|  7|  3|  8|  9|  1|  2|
---+---+---+---+---+---+---+---+---+
  9|  7|  2|  8|  1|  3|  5|  6|  4|
---+---+---+---+---+---+---+---+---+
  8|  4|  6|  9|  5|  2|  3|  7|  1|
---+---+---+---+---+---+---+---+---+
  5|  3|  1|  4|  6|  7|  2|  9|  8|
---+---+---+---+---+---+---+---+---+
  3|  6|  9|  1|  7|  4|  8|  2|  5|
---+---+---+---+---+---+---+---+---+
  1|  2|  5|  3|  8|  9|  7|  4|  6|
---+---+---+---+---+---+---+---+---+
  4|  8|  7|  6|  2|  5|  1|  3|  9|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s
avinash@avinash-laptop:~/work/suduko$ cat 30.inp 
370000001000700005408061090000010000050090460086002030000000000694005203800149500
avinash@avinash-laptop:~/work/suduko$ ./suduko 30.inp 
---+---+---+---+---+---+---+---+---+
  3|  7|  5|  9|  8|  4|  6|  2|  1|
---+---+---+---+---+---+---+---+---+
  1|  6|  9|  7|  2|  3|  8|  4|  5|
---+---+---+---+---+---+---+---+---+
  4|  2|  8|  5|  6|  1|  3|  9|  7|
---+---+---+---+---+---+---+---+---+
  9|  4|  3|  6|  1|  8|  7|  5|  2|
---+---+---+---+---+---+---+---+---+
  2|  5|  1|  3|  9|  7|  4|  6|  8|
---+---+---+---+---+---+---+---+---+
  7|  8|  6|  4|  5|  2|  1|  3|  9|
---+---+---+---+---+---+---+---+---+
  5|  1|  7|  2|  3|  6|  9|  8|  4|
---+---+---+---+---+---+---+---+---+
  6|  9|  4|  8|  7|  5|  2|  1|  3|
---+---+---+---+---+---+---+---+---+
  8|  3|  2|  1|  4|  9|  5|  7|  6|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s
avinash@avinash-laptop:~/work/suduko$ cat 25.inp 
000075400000000008080190000300001060000000034000068170204000603900000020530200000
avinash@avinash-laptop:~/work/suduko$ ./suduko 25.inp 
---+---+---+---+---+---+---+---+---+
  6|  9|  3|  8|  7|  5|  4|  1|  2|
---+---+---+---+---+---+---+---+---+
  1|  4|  5|  6|  3|  2|  7|  9|  8|
---+---+---+---+---+---+---+---+---+
  7|  8|  2|  1|  9|  4|  3|  5|  6|
---+---+---+---+---+---+---+---+---+
  3|  5|  7|  4|  2|  1|  8|  6|  9|
---+---+---+---+---+---+---+---+---+
  8|  1|  6|  9|  5|  7|  2|  3|  4|
---+---+---+---+---+---+---+---+---+
  4|  2|  9|  3|  6|  8|  1|  7|  5|
---+---+---+---+---+---+---+---+---+
  2|  7|  4|  5|  1|  9|  6|  8|  3|
---+---+---+---+---+---+---+---+---+
  9|  6|  8|  7|  4|  3|  5|  2|  1|
---+---+---+---+---+---+---+---+---+
  5|  3|  1|  2|  8|  6|  9|  4|  7|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0.1 s
  System CPU Time: 0.01 s
  Wait Time      : 0.01 s
  -------------------------------
  Elapsed Time   : 0.12 s

Some STL one-liners

Copy elements from one container to another.

std::copy( source.begin(), source.end(), std::back_inserter( container ) );

copying containers to the output: And copying the input stream into a container

std::vector<int>   data;
std::copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(),std::back_inserter(data));
std::copy(data.begin(),data.end(),std::ostream_iterator<int>(std::cout,"\n"));

vector erase and remove

vector<int> v;
...
v.erase(remove(v.begin(), v.end(), 42), v.end());

bind1st/bind2nd/mem_fun

// will call a->func(v[i])
for_each(v.begin(), v.end(), bind1st(mem_fun(&A::func), &a));
// will call w[i]->func(72)
for_each(w.begin(), w.end(), bind2nd(mem_fun(&A::func), 72));

One for looping over each line in a file. From a Andrew Koenig column in Dr. Dobbs.

for (string s; getline(stream,s); ) {
  // Process line
}

Fill an array with random numbers

std::generate(V.begin(), V.end(), rand);

Reading entire file in one go.

std::istreambuf_iterator < char > begin(std::cin), end;
std::string str(begin, end);

Generating prime number from 0 to n

When Initially I looked into this problem, it looks very difficult and time taking problem. But after some searching I found one Aha! algorithm. Sieve of Eratosthenes, (Greek: κόσκινον Ἐρατοσθένους). Eratosthenes, an ancient Greek mathematician written beautiful algorithm for finding all prime numbers up to a specified integer.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
Create a list of consecutive integers from two to n: (2, 3, 4, …, n).
Initially, let p equal 2, the first prime number.
Starting from p, count up by p and cross out thus found numbers in the list (which will be 2p, 3p, 4p, etc.).
Find the first number not yet crossed out after p; let p now equal this number (which is the next prime).
Repeat steps 3 and 4 until p is greater than n.
All the numbers in the list which are not crossed out are prime.

Algorithm is taken from wikipedia article
Following is my implementation :

#include <iostream>
#include <vector>
#include <algorithm>
#include "Timer.h"
void prime_generator(int n, std::vector<int>& prime_list ) {
    Timer t("Prime number generation starts");
    std::vector<int> sequence(n + 1,1);
    for ( int index = 2; index <= n; ++index) {
        if( sequence[index] ) {
            for ( int i = 2 * index; i <= n ; i += index ) {
                if ( sequence[i] ) {
                    sequence[i] = 0;
                }
            }
        }
    }
    for ( int i = 2; i <= n; i++) {
        if ( sequence[i]){
            prime_list.push_back(i);
        }
    }
    t.stop();
}
int main( int argc, char **argv ) {
    std::vector<int> prime_list;
    prime_list.reserve(10000000);
    prime_generator( 10000000 , prime_list );
    for ( std::vector<int>::iterator itr = prime_list.begin(); itr != prime_list.end(); ++itr) {
        std::cout << *itr << std::endl;
    }
}

For Timer Class see my previous post.
Time taken to generate prime number from 0 to 10000000.

avinash@avinash-laptop:~/work/prime$ ./a.out 
  Prime number generation starts
  -------------------------------
  User CPU Time  : 0.46 s
  System CPU Time: 0.04 s
  Wait Time      : 0.01 s
  -------------------------------
  Elapsed Time   : 0.51 s

Coin change Problem ( C++ Solution)

coins Suppose we need to make change for 67¢. We want to do this using the fewest number of coins possible. Pennies, nickels, dimes and quarters are available.

Formal description of the problem is as follows:

Let D = {d1, d2, …, dk} be a finite set of distinct coin denominations.

Example: d1 = 25¢, d2 = 10¢, d3 = 5¢, and d4 = 1¢.
• We can assume each di is an integer and d1 > d2 > … > dk.
• Each denomination is available in unlimited quantity.

  • The Coin-Changing problem:
    – Make change for n cents, using a minimum total number of coins.
    – Assume that dk = 1 so that there is always a solution.

Solution using dynamic programming is as follows:

  • Let D = {d1, d2, …, dk} be the set of coin denominations, arranged such that d1 = 1¢. As before, the problem is to make change for n cents using the fewest number of coins.
  • Use a table C[1..k, 0..n]:
    – C[i, j] is the smallest number of coins used to make change for j cents, using only coins d1, d2, …, di.
    – The overal number of coins (the final optimal solution) will be computed in C[k, n].
#include <vector>
#include <iostream>
#include <string>
int compute_change(std::vector<int> &d, int size) {
    int k = (int)d.size();
    std::vector<std::vector<int> > table(k , std::vector<int>(size + 1));
    for ( int row = 0; row < k ; row++) 
        table[row][0]  = 0;    
    for ( int col = 0; col <= size ; col++) 
        table[0][col]  = col;
    for ( int row = 1 ; row < k; row++) {
        for ( int col = 1 ; col <= size; col++) {
            if ( col < d[row] )  
                table[row][col] = table[row - 1][col];
            else 
                table[row][col] = std::min(table[row - 1][col], 1 + table[row][col - d[row]]);
        }
    }
    return table[k - 1][size - 1];
}
int main ( int argc, char **argv) {
    int points[] = { 1, 2, 3, 17, 23, 42, 98};
    std::vector<int> d (points, points + sizeof(points) / sizeof(int));
    int solution =  compute_change(d,2349 );
    return 0;
}

Code can be downloaded from here

Knapsack Problem ( C++ Solution )

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Read more here. Here is the my solution to the problem using bottom up dynamic programming approach.

#include <vector>
#include <iostream>
#include <iomanip>
#include <string>
struct item {
    int value;
    int capacity;
};    
class Knapsack {
public:
    Knapsack(int knapsack_size, int item_size);
    ~Knapsack();
    void add_items(int value, int capacity);
    int  solve();
    void get_items_selected(std::vector<item>& resultItems);
    friend std::ostream &operator <<( std::ostream&, const Knapsack& );
private:
    void init_knapsack_table();
    std::vector<item> m_items;
    int m_knapsack_size;
    int m_item_size;
    // 2D matrix to store intermediate 
    // result of the knapsack calculation.
    std::vector<std::vector<int> > m_knapsack_table;
    // 2D matrix to store the intermediate
    // result for which item is selected
    // Later this matrix is used to get which items
    // are selected for optimal calculation.
    std::vector<std::vector<int> > m_selection_table;
protected:
};
Knapsack::Knapsack(int knapsack_size, int item_size):
                   m_knapsack_size(knapsack_size),
                   m_item_size(item_size),
                   m_knapsack_table(item_size + 1,std::vector<int>(knapsack_size + 1)),
                   m_selection_table(item_size + 1,std::vector<int>(knapsack_size + 1)){
    m_items.reserve(m_item_size);
}
void Knapsack::add_items(int value, int capacity) {
    item t;
    t.value = value;
    t.capacity = capacity;
    m_items.push_back(t);
}
int Knapsack::solve() {
    // Initialize the first row in both the
    // tables, these values are used as default
    // as if no items are selected and no capacity
    // is available.
    // This is the default case for bottom-up approach.
    for ( int i = 0; i < m_knapsack_size + 1 ; i++) {
        m_knapsack_table [0][i]  = 0;
        m_selection_table[0][i]  = 0;
    }
    int row = 1;
    for ( std::vector<item>::iterator itemIterator = m_items.begin();
                                      itemIterator != m_items.end();
                                      ++itemIterator) {
        item currentItem = *itemIterator;
        int col = 0; // col is capacity available.
        while ( col < m_knapsack_size + 1 ) {
            //1. Check if item can be fit by it's own.
            if ( currentItem.capacity > col ) {
                //2. Get the solution for the already solved
                //   knapsack problem.
                m_knapsack_table[row][col] = m_knapsack_table[row - 1][col];
                // Update the selection table as we are not able to accomodate this item
                // eventually we are not selecting this ite.
                m_selection_table[row][col] = 0;
            } else {
                // We are now considering the item.
                int capacity_remaining = col - currentItem.capacity;
                int new_value  = currentItem.value + m_knapsack_table[row - 1][capacity_remaining];
                int prev_value = m_knapsack_table[row - 1][col];
                if ( prev_value >= new_value) {
                    // There is no gain here to consider this item.
                    m_knapsack_table[row][col] = m_knapsack_table[row - 1][col];
                    m_selection_table[row][col] = 0;
                } else {
                    // Add this item into the knapsack.
                    m_knapsack_table[row][col]  = new_value;
                    // Update the selection table as we are considering
                    // this item.
                    m_selection_table[row][col] = 1;
                }
            }
            col++;
        }
        row++;
    }
    return m_knapsack_table[m_item_size][m_knapsack_size];
}
void Knapsack::get_items_selected(std::vector<item>& resultItems) {
    int row = m_item_size;
    int col = m_knapsack_size;
    int cap = m_knapsack_size;
    while ( cap > 0 ) {
        if ( m_selection_table[row][col] == 1) {
            resultItems.push_back(m_items[row - 1]);
            cap = cap - m_items[row - 1].capacity;
            col = cap;
        }             
        row = row - 1;
    }
}
std::ostream &operator << (std::ostream &out, const Knapsack &knp ) {
    out << std::endl;
    out << "SOLUTION MATRIX" << std::endl << std::endl;
    out << std::setw(15) << "Capacity |";
    for ( int i = 0; i <= knp.m_knapsack_size; i++) {
        out << std::setw(5) << i ;
    }
    out << std::endl;
    out << std::endl;
    int row = 0;
    out << std::setw(15) << "NONE |";
    int col = 0;
    while ( col < knp.m_knapsack_size + 1 ) {
        out << std::setw(5) << knp.m_knapsack_table[row][col];
        col++;
    }
    out << std::endl;
    row++;
    for ( std::vector<item>::const_iterator itemIterator = (knp.m_items).begin();
                                      itemIterator != knp.m_items.end();
                                      ++itemIterator) {
        out << "(V:" 
            << std::setw(2) 
            << itemIterator->value 
            << ", " 
            << "W:" 
            << itemIterator->capacity 
            << ")" 
                << std::setw(4) 
            << "|" ;
        col = 0;
        while ( col < knp.m_knapsack_size + 1 ) {
            out << std::setw(5) << knp.m_knapsack_table[row][col];
            col++;
        }
        row++;
        out << std::endl;
    }
    out << std::endl;
    out << "SELECTION MATRIX" << std::endl << std::endl;
    out << std::setw(15) << "Capacity |";
    for ( int i = 0; i <= knp.m_knapsack_size; i++) {
        out << std::setw(5) << i ;
    }
    out << std::endl;
    out << std::endl;
    row = 0;
    out << std::setw(15) << "NONE |";
    col = 0;
    while ( col < knp.m_knapsack_size + 1 ) {
        out << std::setw(5) << knp.m_knapsack_table[row][col];
        col++;
    }
    out << std::endl;
    row++;
    for ( std::vector<item>::const_iterator itemIterator = (knp.m_items).begin();
                                      itemIterator != knp.m_items.end();
                                      ++itemIterator) {
        out << "(V:" 
            << std::setw(2) 
            << itemIterator->value 
            << ", " 
            << "W:" 
            << itemIterator->capacity 
            << ")" 
            << std::setw(4) 
            << "|" ;
        col = 0;
        while ( col < knp.m_knapsack_size + 1 ) {
            out << std::setw(5) << knp.m_selection_table[row][col];
            col++;
        }
        row++;
        out << std::endl;
    }
    return out;
}
Knapsack::~Knapsack() {
}
int main ( int argc, char **argv) {
    Knapsack knp(18,7);
    knp.add_items(12,4 );
    knp.add_items(10,6 );
    knp.add_items(8 ,5 );
    knp.add_items(11,7 );
    knp.add_items(14,3 );
    knp.add_items(7 ,1 );
    knp.add_items(9 ,6 );
    int solution  = knp.solve();
    std::cout << knp;
    std::vector<item> resultItems;
    knp.get_items_selected(resultItems);
   std::cout << "SOLUTION" << std::endl;
    std::cout << '\t' << "Value : " << solution << std::endl;
    std::cout << '\t' << "Items : " << std::endl;
    for ( std::vector<item>::iterator itr = resultItems.begin();
                                      itr != resultItems.end();
                                      ++itr) {
        std::cout    << '\t' << '\t' << "(V:" 
                    << std::setw(2) 
                    << itr->value 
                    << ", " 
                    << "W:" 
                    << itr->capacity 
                    << ")" 
                    << std::endl;
    }
    return 0;
}

Running this on the added items you will get following output.

knapsack

Download the source from Here