Category Archives: Dynamic and Recursive

Sudoku

Posted in Backtracking, Dynamic and Recursive by
/***
Sudoku
Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.

Backtracking Algorithm
Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells. Before assigning a number, we check whether it is safe to assign. We basically check that the same number is not present in current row, current column and current 3X3 subgrid. After checking for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment doesn’t lead to a solution, then we try next number for current empty cell. And if none of number (1 to 9) lead to solution, we return false.
***/

#include<iostream>

using namespace std;

class Sudoku {
public:
       Sudoku(int (*m)[9]);
       ~Sudoku(){ };
       bool fill_Sudoku();
       void print();
private:
       int sudo[9][9];
       // index by number, fill[i][j], j is the row array which fill by the column.
       int fill[10][9];
       bool isSafe(int, int, int);
       bool isSuccess(int*, int*);
};

Sudoku :: Sudoku (int (*m)[9]) {
       //initial sudo[][] and fill[][]
       for(int i = 1; i<10; i++) {
              for(int j = 0; j<9; j++)
                     fill[i][j] = -1;
       }

       for(int i = 0; i<9; i++) {
              for(int j = 0; j<9; j++) {
                     sudo[i][j] = m[i][j];
                     if(sudo[i][j] != 0) {
                           fill[sudo[i][j]][i] = j;
                     }
              }
       }
}

bool Sudoku :: isSafe(int num, int row, int col) {
       if(fill[num][row] != -1) return false;

       for(int i = 0; i<9; i++) {
              if(fill[num][i] == col) return false;
       }

       int r = row / 3;
       int c = col / 3;
       for(int i = r*3; i<r*3+3; i++) {
              for(int j = c*3; j<c*3+3; j++) {
                     if(sudo[i][j] == num) return false;
              }
       }
       return true;
}

bool Sudoku :: isSuccess(int *row, int *col) {
       for(int i = 0; i<9; i++) {
              for(int j = 0; j<9; j++) {
                     if(sudo[i][j] == 0) {
                           *row = i;
                           *col = j;
                           return false;
                     }
              }
       }
       return true;
}

bool Sudoku :: fill_Sudoku() {

       int row, col;
       if(isSuccess(&row, &col)) {
              return true;
       }

       for(int i = 1; i<=9; i++) {
              if(isSafe(i, row, col)) {
                     sudo[row][col] = i;
                     fill[i][row] = col;

                     if(fill_Sudoku()) return true;
                    
                     sudo[row][col] = 0;
                     fill[i][row] = -1;
              }            
       }
       return false;
}

void Sudoku::print() {
       for (int i = 0; i<9; i++)
       {
              for (int j = 0; j<9; j++)
              {
                     cout<<sudo[i][j]<<” “;
              }
              cout<<endl;
       }
}

int main()
{
       // 0 means unassigned cells
       int grid[9][9] = {
       {3, 0, 6, 5, 0, 8, 4, 0, 0},
       {5, 2, 0, 0, 0, 0, 0, 0, 0},
       {0, 8, 7, 0, 0, 0, 0, 3, 1},
       {0, 0, 3, 0, 1, 0, 0, 8, 0},
       {9, 0, 0, 8, 6, 3, 0, 0, 5},
       {0, 5, 0, 0, 9, 0, 6, 0, 0},
       {1, 3, 0, 0, 0, 0, 2, 5, 0},
       {0, 0, 0, 0, 0, 0, 0, 7, 4},
       {0, 0, 5, 2, 0, 6, 3, 0, 0}};
      
       Sudoku sd(grid);
       sd.fill_Sudoku();
       sd.print();

       return 0;


}

Palindrome Integer

Posted in Arrays and Strings, Dynamic and Recursive by
/***
a integer is the palindrome?
***/
#include
using namespace std;
bool ispalindrome(int x, int &y) {
       if(x == 0 || y == 0) return true;
      
       if(ispalindrome(x/10, y)) {
              if (x%10 == y%10) {
                     y /= 10;
                     return true;
              }
              else return false;
       } else return false;
}
void main() {
       int n = 135631;
       if (ispalindrome(n, n))
       {
              cout<<“is palindrome”<<endl;
       } else cout<<“no”<<endl;

}

Check String Chaining

Posted in Amazon, Dynamic and Recursive, Linked List by
/***
You are given an array of Strings, return TRUE if and only if All the strings can be connected in one chain.
Condition for connectivity is , if the last character of one string matches first character of second string, the two string can be connected.
Example : String []arr ={“abc”, “cde”, “cad” , “def” , “eac”} will return TRUE coz all strings can be connected in one chain
“abc”->”cde”->”eac”->”cad”->”def”
Another Example : String []arr ={“acb” , “cde”, “def”, “ead” } returns False coz “cde”->”ead”->”def” is the possible chain but “acb” is left out.
Note : Its not necessary to start with the first String and form the chain, It may happen that you won’t get a chain if you start with first string but you can get a
chain if you Start with any other String. If there exists a possible chain, then your solution should return True.
In the second example , if the first String was suppose “fcb” , then a possible chain would have exists “cde”->”ead”->”def”->”fcb” so True.
***/
/**
Idea: only to check the first item and last item in string
case1: no connection
data structure: linked list
**/
#include
#include
using namespace std;
bool isChaining(string *str, int sz, int index, int rd, bool *b) {
       if(rd == 0) return true;
      
       for(int i = 0; i<sz; i++) {
              if(b[i] && str[index].back() == str[i].front()) {
                     b[i] = false;
                     if(isChaining(str, sz, i, rd-1, b)) return true;
                     b[i] = true;
              }
       }
       return false;
}
void main() {
       string str[] = {“cde”, “cad” , “def” , “eac”, “abc” };
       int sz = sizeof(str) / sizeof(string);
       bool *b = new bool[sz];
       memset(b, true, sz);
       for (int i = 0; i<sz; i++)
       {
              b[i] = false;
              if(isChaining(str, sz, i, sz-1, b))
                     cout<<“true”<<endl;
              else memset(b, true, sz);
       }

}

Highest Stack Box

Posted in Cracking Code, Dynamic and Recursive by
/***
9.10
You have a stack of n boxs, with widths wi, height hi, and depths di.
The boxes cannot be rotated and can only be stacked on top of one another
if each box in the stack is strictly larger than the box above it in width,
height and depth. Implement a method to build the tallest  stack possible,
where the height of a stack is the sum of the heights of each box.
***/
#include
#include
#include
#include

#include
using namespace std;
struct box {
    int h;
    int w;
    int d;
};
struct boxstack {
    int height;
    vector<int> bstack;
};
bool sortbyh(box b1, box b2) {
    if(b1.h < b2.h) return true;
    else return false;
}
class maxstackbox {
public:
    maxstackbox(box *mybox, int size) {
        this->mybox = mybox;
        this->size = size;
    }
    ~maxstackbox() {
        cache.clear();
    }
    void getmaxstack(int index);
    void print();
private:
    box *mybox;
    int size;
    boxstack max;
    bool chkvalid(box b1, box b2);
    map<int, boxstack> cache;
};
bool maxstackbox::chkvalid(box b1, box b2) {
    if(b1.h < b2.h && b1.w < b2.w && b1.d < b2.d) return true;
    else return false;
}
void maxstackbox::getmaxstack(int index) {
    if(index == size) return;
    boxstack cur;
    cur.height = mybox[index].h;
    cur.bstack.push_back(index);
    boxstack curmax;
    for(int i = index; i>0; i–) {
        if (chkvalid(mybox[i-1], mybox[index]))
        {
            if (curmax.height < cache[i-1].height)
                curmax = cache[i-1];
        }
    }
   
    if (!curmax.bstack.empty())
    {
        copy(curmax.bstack.begin(), curmax.bstack.end(),back_inserter(cur.bstack));
        cur.height += curmax.height;
    }
    cache.insert(pair<int, boxstack>(index, cur));
    if (cur.height > max.height)
    {
        max = cur;
    }
    getmaxstack(index+1);
}
void maxstackbox::print() {
    cout<<“max height: “<<max.height<<endl;
    for (int i = 0; i< max.bstack.size(); i++)
    {
        cout<<max.bstack[i]<<“, “;
    }
}
void main() {
    box mybox[5];
    int h = 3;
    int w = 4;
    int d = 2;
    for (int i = 0; i < 5; i++)
    {
        mybox[i].h = h++;
        mybox[i].w = w++;
        mybox[i].d = d++;
    }
    mybox[2].w = 3;
    sort(mybox, mybox+5, sortbyh);
    maxstackbox mb(mybox, 5);
    mb.getmaxstack(0);
    mb.print();
}

Eight Queen Puzzle

Posted in Cracking Code, Dynamic and Recursive by
/***
9.9
Write an algorithm to print all ways of arranging eight queens on an 8X8 chess
board so that none of them share the same row, column or diagonal. In this case,
“diagonal” means all diagonals, not just the two that bisect the board.
M*N
row[n] = col
***/
#include
#include
#include
#include
using namespace std;
#define ROW 8
#define COL 8
bool isvalid(vector<int> row, int r, int col) {
       for(int i = 0; i<r; i++) {
                     if(col == row[i]) return false;
                     if(abs(row[i] – col) == r-i) return false;
       }
      
       return true;
}
void placequeen(vector<int> row, int r, vector<vector<int>> *ways) {
       if(r == ROW) {
              ways->push_back(row);
       }
       else {
              for(int i = 0; i<COL; i++) {
                     if(isvalid(row, r, i)) {
                           row[r] = i;
                           placequeen(row, r+1, ways);
                     }
              }
       }
}
void main() {
       vector<vector<int>> placeway;
       vector<int> row;
       for(int i = 0; i<ROW; i++) row.push_back(INT_MAX);
       placequeen(row, 0, &placeway);
       for(int i = 0; i < placeway.size(); i++) {
              for(int j = 0; j < ROW; j++)
                     cout<<placeway[i][j]<<” “;
              cout<<endl;
       }

}

Paint Fill

Posted in Cracking Code, Dynamic and Recursive by
/***
9.7
Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.
***/
#include
using namespace std;
void paintfill(int *a, int color, int org, int x, int y, int sz) {
       if(x < 0 || y sz-1 || y > sz-1) return;
       if(*(a+x*sz+y) != org || *(a+x*sz+y) == color) return;
       *(a+x*sz+y) = color;
       paintfill(a, color, org, x-1, y, sz);
       paintfill(a, color, org, x+1, y, sz);
       paintfill(a, color, org, x, y-1, sz);
       paintfill(a, color, org, x, y+1, sz);
}
void main() {
       int a[] = {0, 0, 0, 0, 0, 0, 1, 0, 0};
       paintfill(a, 2, 0, 1, 1, 3);
       for (int i = 0; i<3; i++)
       {
              for (int j=0; j<3; j++)
              {
                     cout<<a[i*3+j]<<” “;
              }
              cout<<endl;
       }

}

Valid Parentheses

Posted in Cracking Code, Dynamic and Recursive by
/***
9.6
Implement an algorithm to prink all valid (eg. properly opened and closed combinations of n-pairs of parentheses)
EXAMPLE:
input: 3
Output: ()()(), ((())), ()(()), (()()), (())()
***/
#include
#include
#include
using namespace std;
void validParentheses(int n, set *prt) {
       if(n==0) return;
       if (prt->empty())
       {
              string s;
              s.push_back(‘(‘);
              s.push_back(‘)’);
              prt->insert(s);
       } else {
              set ts;
              set :: iterator it;
              ts = *prt;
              prt->clear();
              for(it = ts.begin(); it != ts.end(); it++) {
                     string s = *it;
                     string :: iterator it1, it2;
                     for(int i=0; i<s.size(); i++) {
                           if(s[i] == ‘(‘) {
                                  s.insert(i, “(“);
                                  string temp = s;
                                  for(int j=i+1; j<s.size(); j++) {
                                         if(temp[j] == ‘)’) {
                                                temp = s;
                                                temp.insert(j+1, “)”);
                                                prt->insert(temp);
                                         }            
                                  }
                           }
                           s = *it;
                     }
                     s.push_back(‘(‘);
                     s.push_back(‘)’);
                     prt->insert(s);
              }
       }
       validParentheses(n-1, prt);
}
void main() {
       int n = 3;
       set partset;
       set :: iterator it;
       validParentheses(n, &partset);
       for (it = partset.begin(); it != partset.end(); it++)
       {
              cout<<*it<<endl;
       }

}

all permutation of string

Posted in Cracking Code, Dynamic and Recursive by
/***
9.5 Write a method to compute all permutations of a string.
IDEA: considering a string
start from the begining,
***/
#include
#include
#include
#include
using namespace std;
void permutation(string str, int index, set *strset) {
       if(index < 0) return;
       set ts = *strset;
       strset->clear();
       set :: iterator it;
       string::iterator its;
       for(it = ts.begin(); it != ts.end(); it++) {
              string s = *it;
              for(its = s.begin(); its != s.end(); its++) {         
                     s.insert(its, str[index]);
                     strset->insert(s);
                     s = *it;
              }
              s.push_back(str[index]);
              strset->insert(s);
       }
       permutation(str, index-1, strset);
}
set allpermutation(string str) {
       set permutationset;
       int sz = str.size();
       string s;
       s.push_back(str[sz-1]);
       permutationset.insert(s);
       permutation(str, sz-2, &permutationset);
       return permutationset;
}
void main() {
       string s = “cat”;
       set permutationset = allpermutation(s);
       set::iterator it;
       for(it = permutationset.begin(); it != permutationset.end(); it++) {
              cout<<*it<<endl;
       }

}

Subset

Posted in Cracking Code, Dynamic and Recursive by
/***
9.4
return all subset of set.
***/
#include
#include
using namespace std;
// Recursive, complexity is O(2^n)
void allsubset(int *a, int index, vector<vector<int>> *subsets) {
       if(index < 0) return;
       int sz = subsets->size();
       for(int i = 0; i<sz; i++) {
              vector<int> v;
              v = (*subsets)[i];
              v.push_back(a[index]);
              subsets->push_back(v);
       }
       allsubset(a, index-1, subsets);
}
void main() {
       int a[] = {1, 3, 5, 7};
       int sz = sizeof(a) / sizeof(int);
       vector<vector<int>> subsets;
       vector<int> v;
       subsets.push_back(v);
       allsubset(a, sz-1, &subsets);
       for (int i = 0; i<subsets.size(); i++)
       {
              for(int j=0; j<subsets[i].size(); j++)
                     cout<<“(“<<subsets[i][j]<<“, “;
              cout<<“)”<<endl;
       }
}

Magic Index

Posted in Cracking Code, Dynamic and Recursive by
/***9.3
A magic index in an array A[0, 1, …, n-1] is defined to be an index such that A[i] = i.
Given a sorted array, write a method to find a magic index, if one exists, in array A.
FOLLOW UP:
What if the values are not distinct?
***/
#include
using namespace std;
bool isMagic(int *a, int begin, int end) {
       if(begin > end) return false;
       int mid = (begin + end) / 2;
       if(mid == a[mid] ) return true;
       else if(mid < a[begin]) return isMagic(a, mid+1, end);
       else if(mid > a[end]) return isMagic(a, begin, mid-1);
       else {
              if(isMagic(a, begin, mid-1)==true || isMagic(a, mid+1, end) == true)
                     return true;
              else return false;
       }
}
void main() {
       int a[] = {1, 1, 3, 4, 5};
       int sz = sizeof(a) / sizeof(int);
       if(isMagic(a, 0, sz-1) == true)
              cout<<“magic”<<endl;
       else cout<<“nothing”<<endl;

}