Utility function for generating required number digits after decimal point.

#include <stdio.h>
#include <string.h>


/**
-------------------------------------------------------------------
Problem :
-------------------------------------------------------------------
For a given fraction [x / y] finding "n" number of digits after the 
decimal point. 

"x" and "y" are positive integers

The value after the decimal will not be rounded but will be 
truncated to "n" digits
-------------------------------------------------------------------
 
-------------------------------------------------------------------
Example :
-------------------------------------------------------------------
[1]
x = 22
y = 7
x / y = 3.1428571428571428571428571428571...
Required DigitsAfterDecimalPoint = 20
BufferPrecision = "14285714285714285714"
 
[2]
x = 7
y = 22
x / y = 0.3181818181818181818181818181818...
Required DigitsAfterDecimalPoint = 20
BufferPrecision = "31818181818181818181"

[3]
x = 7
y = 7
x / y = 1.00000000000000000000000000000000...
Required DigitsAfterDecimalPoint = 20
BufferPrecision = "00000000000000000000"
-------------------------------------------------------------------

-------------------------------------------------------------------
Function Description :
-------------------------------------------------------------------
void GetRequiredPrecision(int _x, int _y, int _iDigitsAfterDecimalPoint, char *_pcBufferPrecision);
[in]_x : Dividend
[in]_y : Divisor
[in]_iDigitsAfterDecimalPoint : The number of digits which are required after the decimal point
[out]_pcBufferPrecision : Pointer to buffer which will hold the result.
_pcBufferPrecision should point to a buffer of length (_iDigitsAfterDecimalPoint + 1)
-------------------------------------------------------------------
/**/
void GetRequiredPrecision(int _x, int _y, int _iDigitsAfterDecimalPoint, char *_pcBufferPrecision)
{
 if((_x % _y) == 0)
 {
  memset(_pcBufferPrecision, '0', _iDigitsAfterDecimalPoint);
  _pcBufferPrecision[_iDigitsAfterDecimalPoint] = 0;
  return;
 }

 int table[11];
 table[0] = _y * 0;
 table[1] = _y * 1;
 table[2] = _y * 2;
 table[3] = _y * 3;
 table[4] = _y * 4;
 table[5] = _y * 5;
 table[6] = _y * 6;
 table[7] = _y * 7;
 table[8] = _y * 8;
 table[9] = _y * 9;
 table[10] = _y * 10;

 int iCount = 0;
 int iReminder = _x % _y;  
 int iNewReminder = 0;

 while(_iDigitsAfterDecimalPoint-- > 0)
 {
  iNewReminder = (iReminder << 3) + (iReminder << 1);

  if((iNewReminder >= table[0]) && (iNewReminder <= (table[1]-1)))
  {
   _pcBufferPrecision[iCount] = '0';
   iReminder = iNewReminder;
  }   
  else if((iNewReminder >= table[1]) && (iNewReminder <= (table[2]-1)))
  {
   _pcBufferPrecision[iCount] = '1';
   iReminder = iNewReminder - table[1];
  }
  else if((iNewReminder >= table[2]) && (iNewReminder <= (table[3]-1)))
  {
   _pcBufferPrecision[iCount] = '2';
   iReminder = iNewReminder - table[2];
  }
  else if((iNewReminder >= table[3]) && (iNewReminder <= (table[4]-1)))
  {
   _pcBufferPrecision[iCount] = '3';
   iReminder = iNewReminder - table[3];
  }
  else if((iNewReminder >= table[4]) && (iNewReminder <= (table[5]-1)))
  {
   _pcBufferPrecision[iCount] = '4';
   iReminder = iNewReminder - table[4];
  }
  else if((iNewReminder >= table[5]) && (iNewReminder <= (table[6]-1)))
  {
   _pcBufferPrecision[iCount] = '5';
   iReminder = iNewReminder - table[5];
  }
  else if((iNewReminder >= table[6]) && (iNewReminder <= (table[7]-1)))
  {
   _pcBufferPrecision[iCount] = '6';
   iReminder = iNewReminder - table[6];
  }
  else if((iNewReminder >= table[7]) && (iNewReminder <= (table[8]-1)))
  {
   _pcBufferPrecision[iCount] = '7';
   iReminder = iNewReminder - table[7];
  }
  else if((iNewReminder >= table[8]) && (iNewReminder <= (table[9]-1)))
  {
   _pcBufferPrecision[iCount] = '8';
   iReminder = iNewReminder - table[8];
  }
  else if((iNewReminder >= table[9]) && (iNewReminder <= (table[10]-1)))
  {
   _pcBufferPrecision[iCount] = '9';
   iReminder = iNewReminder - table[9];
  }
  ++iCount;   
 }

 _pcBufferPrecision[iCount] = 0;
}

int main(int argc, char*argv[])
{
 int x = 22;
 int y = 7;
 char BufferPrecision[21];
 int iDigitsAfterDecimalPoint = 20;
 GetRequiredPrecision(x, y, iDigitsAfterDecimalPoint, BufferPrecision);
 printf("after dividing %d by %d, the %d digits after decimal point are\n%s", x, y, iDigitsAfterDecimalPoint, BufferPrecision);
 return 0;
}

Smallest Repeating Prefix in a non empty String.

/**
-------------------------------------------------------------------
Problem :
-------------------------------------------------------------------
Finding Smallest Repeating Prefix "p" in a non-empty string "s". 
Length of "s" = slen.
Length of "p" = plen.

Following equation should be satisfied
slen = plen * k, where k > 0. 
-------------------------------------------------------------------

-------------------------------------------------------------------
Constraints :
-------------------------------------------------------------------
time  : O(n)
space : O(n)
-------------------------------------------------------------------

-------------------------------------------------------------------
Example :
-------------------------------------------------------------------
[1]
s = ababab
slen = 6
p = ab
plen = 2
k = 3


[2]
s = abh
slen = 3
p = abh
plen = 3
k = 1
-------------------------------------------------------------------
/**/

#include <iostream>
#include <conio.h> 

#include <vector>
#include <string>

using namespace std;


void kmpPreprocess( string &str,  int slen, vector &barray)
{
    int i = 0;
    int j = -1;
    barray[i] = j;
    while(i < slen)
    {
        while( (j >= 0) && (str[i] != str[j]) )
        {
            j = barray[j];
        }
        ++i;
        ++j;
        barray[i] = j;
    }
}

void print_barray( string &s, vector &barray)
{
    int i;
    int slen = s.length();

    cout << endl;
    cout << "index  :  ";
    for(i = 0; i < (slen+1); ++i)
    {
    cout << i << " ";
    }
    cout << endl;

    cout << "string :    ";
    for(i = 0; i < slen; ++i)
    {
    cout << s[i] << " ";
    }
    cout << endl;
    cout << "barray : ";
    for(i = 0; i < (slen+1); ++i)
    {
    cout << barray[i] << " ";
    }
    cout << endl;
}


int using_barray_method_1(string &s, vector &barray)
{        
    string srp_curr = s;    
    int srp_length_curr;
    int srp_length_prev;

    srp_length_curr = srp_curr.length();
    srp_length_prev = srp_length_curr;
    
    while( (srp_length_curr = barray[srp_length_curr]) > 0)
    {    
        if( (srp_length_prev % srp_length_curr) == 0)
        {     
            int k = srp_length_prev / srp_length_curr;

            string chain_of_k_parts;
            chain_of_k_parts.clear();
            while(k--)
            {
                chain_of_k_parts.append(srp_curr.c_str(), srp_length_curr); 
            }

            if(srp_curr.compare(chain_of_k_parts) == 0)
            {
                srp_length_prev = srp_length_curr;                         
                
                srp_curr = srp_curr.substr(0, srp_length_prev);
            }            
        }
    }

    return srp_length_prev;
}


int using_barray_method_2(string &s, vector &barray)
{
    int slen = s.length();

    int srp_length = slen;

    if( (slen % (slen - barray[slen])) == 0 ) 
    {
        srp_length = slen - barray[slen];        
    }

    return srp_length;
}


int find_smallest_repeating_prefix_length(string &s) 
{
    int slen = s.length();

    if(slen == 0)
    {
        return -1;
    }

    vector barray(slen+1);
    
    kmpPreprocess(s, slen, barray);    
    print_barray(s, barray);

        
    int srp_length = -1;

    srp_length = using_barray_method_1(s, barray);
    srp_length = using_barray_method_2(s, barray);
                
    return srp_length;
}


bool check(int slen, int plen, int k)
{
    if( slen == (plen * k) )
    {
        return true;
    }
    else
    {
        return false;
    }
}


void process_string(string &s)
{
    int plen = find_smallest_repeating_prefix_length(s);

    if(plen == -1)
    {
        cout << "error in input string" << endl;
        getch();
        return;
    }

    int i;
    int slen = s.length();    

    int k = slen / plen;    

    if(check(slen, plen, k) == true)
    {
        cout << "[successfully satisfied]  slen == (plen * k)" << endl;
    }
    else
    {
        cout << "[fail to satisfy]  slen != (plen * k)" << endl;
        getch();
        return;
    }

    cout << "s = " << s << endl;
    cout << "slen = " << slen << endl;

    cout << "p = ";
    for(i = 0; i < plen; ++i)
    {
        cout << s[i]; 
    }
    cout << endl;

    cout << "plen = " << plen << endl;    
    cout << "k = " << k << endl;    
}


void main()
{
    string s;
    
    s = "ababab";
    process_string(s);    
    cout << endl << endl;

    s = "abh";
    process_string(s);
    cout << endl << endl;    

    getch();
}


/**
-------------------------------------------------------------------
Output :
-------------------------------------------------------------------

index  :  0 1 2 3 4 5 6
string :    a b a b a b
barray : -1 0 0 1 2 3 4
[successfully satisfied]  slen == (plen * k)
s = ababab
slen = 6
p = ab
plen = 2
k = 3



index  :  0 1 2 3
string :    a b h
barray : -1 0 0 0
[successfully satisfied]  slen == (plen * k)
s = abh
slen = 3
p = abh
plen = 3
k = 1
-------------------------------------------------------------------
/**/


These methods works on following logic :

"barray" stores lengths of various Borders of the string.

Border "b" of a string "s" is a proper prefix which is also the proper suffix of a string "s".

Therefore we can see a border of a string "s" as a prefix "p" which is repeated atleast two times in that string "s".



For more information on Border and how barray is created, please refer Knuth-Morris-Pratt Algorithm.

KMP Algorithm



-----------------------------------------------------------------------------------------------------

Method 1: (using_barray_method_1)

reference : Utilization of KMP Algorithm

-----------------------------------------------------------------------------------------------------

We recursively try to find smallest repeating prefix inside an existing\current smallest repeating prefix.

We start by considering the original string "s" itself as the smallest repeating prefix.

[1] The next smallest prefix "x" (and not the smallest 'REPEATING' prefix) which is repeated in the string "s" can be found

using the "barray" [refer Knuth-Morris-Pratt Algorithm].

[2] Now we check whether this smallest prefix "x" is the smallest repeating prefix in the string "s".

This is done by

[a] checking whether the (length of "x") fully divides (length of "s")

i.e [((strlen(s) % strlen(x)) == 0]

[b] if "x" fully divides "s" then let k = strlen(s) / strlen(x);

[3] Now we try to confirm whether repeating string "x", 'k' number of time give us string "s".

i.e, if string "xxxx...[k times]" == string "s", then we can say string "x" can be the smallest repeating prefix which is repeated 'k' number of times in string "s".

[4] Now if there is a smallest repeating prefix "y" in "x" then it will be our new smallest repeating prefix in "s".

This is true because length of "y" will be smaller then "x".

So we make "s" = "x" and repeat the above steps to find smallest repeating prefix in "x".

-----------------------------------------------------------------------------------------------------



-----------------------------------------------------------------------------------------------------

Method 2: (using_barray_method_2)

-----------------------------------------------------------------------------------------------------

There is one more direct and fast method to find smallest repeating prefix after computing "barray" of string "s".

Came to know about this direct method when discussing this problem on one of the forums Smallest Repeating Prefix

Dateng LIN suggested this method.

-----------------------------------------------------------------------------------------------------

Substring Matching Algorithm : BMH

/**
---------------------------------------------------------------------------
problem :
----------
- find all occurrences of a provided pattern(sub-string) in a given text. 
---------------------------------------------------------------------------
input :
----------
- unsigned char* text : the text string to be searched.
- int n : length of text string.
- unsigned char* pattern : the pattern(sub-string) to be searched in the text.        
- int m : length of pattern.
---------------------------------------------------------------------------
output :
----------
- all position within text from where the pattern can be found.
---------------------------------------------------------------------------
constraints :
-------------
- for each element or letter 't' of text : 0 <= t <= 254.
- for each element or letter 'p' of pattern : 0 <= p <= 254.
- text of pattern cannot contain any letter or element with value 255. 
---------------------------------------------------------------------------
/**/
 
//-------------------------------------------------------------------------
#include <iostream>
#include <conio.h>

#define MAX_ALPHABET_SIZE 256
#define CHARACTER_NOT_IN_THE_TEXT 255

void boyer_moore_horspool(unsigned char* text, int n, unsigned char* pattern, int m)
{
 int d[MAX_ALPHABET_SIZE], i, j, k, lim;

 // Preprocessing
 for(k = 0; k < MAX_ALPHABET_SIZE; ++k) 
 {
  d[k] = m; 
 }

 for(k = 0; k < m; ++k )
 {
  d[pattern[k]] = m - k;
 }

 // To avoid having code
 pattern[m] = CHARACTER_NOT_IN_THE_TEXT; 

 lim = n - m;

 // Searching
 for(k = 0; k <= lim; k += d[text[k + m]]) 
 {
  i = k;
  j = 0;
  while(text[i] == pattern[j])
  {
   ++i;
   ++j;
  }

  if(j == m)
  {
   cout << "pattern found in text at position : " << k << endl;
   if( (k + (m<<1)) >= n)
   {
    break;
   }
  }
 }
}
//-------------------------------------------------------------------------

/**
---------------------------------------------------------------------------
solution :
------------
- complexity : 
average case = O(n) , O(length of text, n).
worst case = O(nm), O([length of text:n]*[length of pattern:m]). 
---------------------------------------------------------------------------
/**/


void main()
{
//positions.....012345678901234567890
 char text[] = "ZZACCABCDBDABCDABCDQQ";
 char pattern[] = "ABCD";
 boyer_moore_horspool(text, strlen(text), pattern, strlen(pattern));

 getch();
}

/**
---------------------------------------------------------------------------
output :
------------
pattern found in text at position : 5
pattern found in text at position : 11
pattern found in text at position : 15
---------------------------------------------------------------------------
/**/

Have used the above code from the following link :
Boyer-Moore-Horspool Algorithm

Substring Matching Algorithm : KMP

Here is the link to a good algorithm for finding all occurrences
of a sub-string(or pattern) in a given text(or string).

Knuth-Morris-Pratt Algorithm.

finding duplicate entry in an array.

/**
---------------------------------------------------------------------------
problem : 
----------
- find first duplicate value in the given array without modifying the array.
---------------------------------------------------------------------------
input : 
----------
- int *a : array of integers
- int l : number of elements in a
- int m : loose upper bound for value of an element of array a.  
        : 0 <= value_of_element_of_a < m
- relation between l and m : l > m
---------------------------------------------------------------------------
output : 
----------
- first duplicate value occuring in the array.
---------------------------------------------------------------------------
constraints : 
------------- 
- space requirement should be O(1)
- after the function returns the array should be same as original.
---------------------------------------------------------------------------
/**/

//-------------------------------------------------------------------------
int find_firstduplicate(int *a, int l, int m)
{
 int original = 0;
 int index = 0;
 int is_index_already_used = 0;
 const int adjustment_for_zero_value = 1;
 int duplicate = -1;

 for(index = 0; index <= m; ++index)
 {
  is_index_already_used = 0;
  original = a[index];

  if(a[index] < 0)
  {
   //means there is already an element with value = index
   is_index_already_used = 1;

   //reversing the step of procedure to handle zero value
   a[index] += adjustment_for_zero_value;

   //original value of the element
   original = abs(a[index]);
  }
  
  if(a[original] >= 0)
  {
   //negating
   a[original] = (- a[original]);
   
   //substracting 1, to handle zero value, since (minus ZERO) = (ZERO) 
   a[original] = a[original] - adjustment_for_zero_value;

   //restoring the fact that index is used.
   a[index] -= is_index_already_used;   
  }
  else
  {
   //duplicate found.
   duplicate = original;
   break;   
  }
 }

 //readjusting the values of array so that they resemble the original.
 for(index = 0; index <= m; ++index)
 {
  if(a[index] < 0)
  {   
   a[index] += adjustment_for_zero_value;
   a[index] = - a[index];
  }
 } 

 return duplicate;
}
//-------------------------------------------------------------------------

/**
---------------------------------------------------------------------------
solution :
- hint : use the value of element as an index 'i' and negate the value at  
index i.
- complexity : O(m) 
---------------------------------------------------------------------------
/**/

void main()
{
 int m = 5;
 int a[] = {1, 0, 3, 0, 4, 5};
 int l = sizeof(a) / sizeof(a[0]);
 int duplicate = find_firstduplicate(a, l, m);
 if(duplicate != -1)
 {
  cout << "first duplicate = " << duplicate << endl;
 }
 else
 {
  cout << "duplicate does not exist." << endl;
 }
 getch();
}

/**
output :
--------
first duplicate = 0
/**/

70 Years, programmed the world.

"C is quirky, flawed, and an enormous success."
-Dennis MacAlistair Ritchie (September 9, 1941 – October 8, 2011)

He developed see programming language, though which I was saw possibilities through programming.

#include <stdio.h>
int main(int argc, char *argv[])
{
 printf("Hello Heaven\n");
 return 0;
}

Sir Dennis's World...

Top scorer.

Original Newspaper Article.

Publication:

The Economic Times Delhi;

Date: Jul 4, 2011;

Section: Corporate;

Page: 5

TechGig to Launch Season 2 of Indian Programming League

OUR BUREAU NEW DELHI

Technology community site TechGig.com, developed by TimesJobs, will launch the second season of the Great Indian Programming League (GIPL), an innovative method of hiring talented software developers from across the country. TechGig created GIPL to connect with coding buffs who normally work behind the scenes and provide a recruitment platform for companies looking for quality talent.

TechGig.com product head Amit Gupta said: “The IPL is a great way of benchmarking one’s coding skills with some of the best software developers in India. We are now launching Season 2 of the IPL, so there is a lot more action in store.” At GIPL, recruiters looking for high quality technical talent get an objective benchmark to automatically measure the competence of people.

The contest attracts passive candidates to participate even if they aren’t looking for a job. Moreover, the scores are easy to measure, making it easy to find the best people at the top. This renders the contest a great platform to sort and hire. During its first season last month, GIPL got more than 11,000 entries from over 2,700 programmers from across India.

The second contest is coming up due to popular demand from techies and tech firms. In the last season, a large number of coders, programmers and software developers from Delhi NCR, Pune, Bangalore, Hyderabad and Chennai battled it out for iPods, daily movie tickets but more importantly recognition among peers.

Omnitech Infosolutions COO and head of global operations Anurag Shah said: “The Great Indian Programming League is an aspiring initiative taken by techgig.com to not just recognize the talented coders but also provide them a platform to achieve global recognition, which will surely motivate them to feature their best practices in the industry.”

Coding as a field is indeed as promising as other professional fields which require technical as well as domain expertise. Coders play a vital role in the software development and act as a bloodline of the projects. The initiative would bring required awareness and change in perception to help coding attain the deserving limelight, Shah added.

The contest involves writing actual code across five to seven different programming languages, including C #, Java, C and C++, to solve a problem live. The software automatically compiles the code to assess its quality and comprehensiveness in solving the problem.

The second season expects to be more promising going by the reaction of programmers who came from across the country in the first season, just for their love for coding. “Just coding, am mad on coding,” said TCS software developer Vishnu Priya Subramanian while Sameer Namdeo said his motivation was a passion for coding, and chance to evaluate him among peers.

Dotsquares

team lead Deepak Tanwar said GIPL was all about personal enhancement, profile upgrade and opportunity to compete with programmers of different languages.

Users complimented Tech-Gig on the range and complexity of the problems set. Uniprose India product manager Vijendra Kumar pointed out the best part of the contest was that the code could not be seen by other programmers and online instant verification of code.

Winning for software developer Jagdesh from Infosys Technologies Limited was overwhelming while Mahindra Satyam Computer Services Limited project leader Amit Kantilal said: “I feel very proud that I have demonstrated my programming skills. I successfully completed the program to solve the sudoku puzzle which has been on my cards since quite some time.”

Common Pitfall : While using malloc instead of new.

Two mostly used things that help in allocating memory are malloc and new.

Sometimes knowledge of using malloc, for allocating memory in common and less complicated situations, can prove wrong in complicated situations.

Situation [1] (Complication Level 1):
int *pData = (int*)malloc(10 * sizeof(int));
Now to access integers at index from 0 to 9 simply use pData[1] or *(pData+2)...
Very simple!!!

Situation [2] (Complication Level 2):
struct ABC
{
int P1;
char P2;
};
ABC *pData = (ABC*)malloc(10 * sizeof(ABC));
Now to access integer P1 of say 4th struct ABC : pData[3].P1
Again Very simple!!!

Situation [3] (Complication Level 3):
struct ABC
{
int P1;
char P2;
};

struct PQR
{
int P1;
char P2;
ABC P3;
};
PQR *pData = (PQR*)malloc(10 * sizeof(PQR));
Now to access integer P1 of ABC which is inside of say 5th struct PQR : pData[4].P3.P1
Again Moderately simple!!!

In above 3 situations memory was allocated and then utilized according to the structure\ layout of structs.

Situation [4] (Complication Level 4):
struct XYZ
{
int P1;
char P2;
CList P3;
};
XYZ *pData = (XYZ*)malloc(10 * sizeof(XYZ));
Now try to insert elements in the list P3 of say 4th struct XYZ:
pData[3].P3.AddTail(2);
Complie Status OK.
Run Status CRASH!!!
Without reading further think a minute why the code did not worked even though memory was already allocated?

This happened because though memory was allocated for all the data members of list XYZ::P3 but those data members were not initialized with default values.

struct XYZ in above example is composite data type (a class or user defined data type) in which the default value initialization of its data-members is normally done in constructor of the class.

In a composite data type the data-members are created (here created means calling of their respective constructor) prior to the invocation of composite data type constructor itself. ("Refer how Object creation takes place")

So what will initialize the data-members along with the task of allocating the memory for members.
Answer : operator new

XYZ *pData = new XYZ[10];
Here 'new' invokes the constructor of both, the data members of struct XYZ and the struct XYZ itself. Inside the CList constructor, members can be initialized with default values.




Conclusion:
[1]Anyway, in C++ new is the preferred mechanism for memory allocation.
[2]Also try to minimize mixing of malloc and new.

Second technical article.

While working with functions, I found a common pattern. A pattern in which all the parameters constituting the parameter-list were bundled in a struct and that struct was passed as a parameter to the function. Therefore, gave a thought on this, in order to find what can be the pros and cons of this pattern. Outcome was the following article:


Description: An article highlighting advantage of using composite data-type for passing parameters to functions.
Parameter Passing :- by Train vs by Truck.

C\ C++ Pointer confusion.

Working with pointers by passing them here and there and not getting expected result!!!
Don't go here and there but go directly to :
Pointer Alises.

First technical article.

Check out my first technical article on codeproject.com.
Description: An article on creating a framework for command processing using Command Design Pattern.
Converting a class into a CommandHandler.

Hello World

Yes, most of the aspiring programmers starts their programming journey by displaying "Hello World". As simple as that. Today I created my blog and just want to say Hello World. Yes, you guessed right!. I also want to start hitting the keyboard...