Effort estimation for converting one character string to another.

//-------------------------------------------------------------------------
/*
Problem Statement:
-------------------
Given two strings string_x and string_y, find the effort required to convert string_x into string_y.

Definition of Effort Required : Number of characters which needs to be ADDED or DELETED from 
string_x inorder to convert string_x into string_y.
*/
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//----- file: stringconversioneffort.c ------------------------------------
//-------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//-------------------------------------------------------------------------
/*
//Function: 
int find_effort(char *string_x, char *string_y, int *char_to_be_added, int *char_to_be_deleted)

//Parameters: 
[in]string_x : source string to be converted
[in]string_y : destination string to which source string needs to be converted
[out]char_to_be_added : number of characters which needs to be added in source string.
[out]char_to_be_deleted : number of characters which needs to be deleted in source string.

//Return-Value:
total effort required
*/
//-------------------------------------------------------------------------
int find_effort(char *string_x, char *string_y, int *char_to_be_added, int *char_to_be_deleted)
{
        int i, j;

        int length_x = strlen(string_x);
        int length_y = strlen(string_y);

        int total_effort = -1;

        if( (length_x == 0) && (length_y != 0) )
        {
                (*char_to_be_added) = length_y;
                (*char_to_be_deleted) = 0;
                total_effort = (*char_to_be_added) + (*char_to_be_deleted);

                return total_effort;
        }
        else if( (length_x != 0) && (length_y == 0) )
        {
                (*char_to_be_added) = 0;
                (*char_to_be_deleted) = length_x;
                total_effort = (*char_to_be_added) + (*char_to_be_deleted);

                return total_effort;
        }
        else if( (length_x == 0) && (length_y == 0) )
        {
                (*char_to_be_added) = 0;
                (*char_to_be_deleted) = 0;
                total_effort = (*char_to_be_added) + (*char_to_be_deleted);

                return total_effort;
        }

        int **c = NULL;
        c = (int**) malloc ((length_x + 1) * sizeof(int*));
        for(i = 0; i <= length_x; ++i)
        {
                c[i] = (int*) malloc ((length_y + 1) * sizeof(int));
                memset(c[i], 0, (length_y + 1));
        }

        for(i = 1; i <= length_x; ++i)
        {
                for(j = 1; j <= length_y; ++j)
                {
                        if(string_x[i-1] == string_y[j-1])
                        {
                                c[i][j] = c[i-1][j-1] + 1;
                        }
                        else if(c[i-1][j] >= c[i][j-1])
                        {
                                c[i][j] = c[i-1][j];
                        }
                        else
                        {
                                c[i][j] = c[i][j-1];
                        }
                }
        }

        for(i = 0; i <= length_x; ++i)
        {
                free(c[i]);
        }
        free(c);

        (*char_to_be_added) = length_y - c[length_x][length_y];
        (*char_to_be_deleted) = length_x - c[length_x][length_y];
        total_effort = (*char_to_be_added) + (*char_to_be_deleted);

        return total_effort;
}


void print_result(char *string_x, char *string_y, int total_effort, int char_to_be_added, int char_to_be_deleted)
{
        printf("Effort Required to convert \n\"%s\"   into\n\"%s\"\ntotal_effort = %d\ncharacters to be added = %d\ncharacters to be deleted = %d\n", string_x, string_y, total_effort, char_to_be_added, char_to_be_deleted);
}

int main(int argc, char *argv[])
{
        if(argc != 3)
        {
                printf("ERROR\nbinary USAGE: [binary_path] [string_x] [string_y]\n");
                return 0;
        }

        char string_x[1024];
        char string_y[1024];

        int total_effort = 0;
        int char_to_be_added = 0;
        int char_to_be_deleted = 0;

        strcpy(string_x, argv[1]);
        strcpy(string_y, argv[2]);

        total_effort = find_effort(string_x, string_y, &char_to_be_added, &char_to_be_deleted);
        print_result(string_x, string_y, total_effort, char_to_be_added, char_to_be_deleted);

        return 0;
}
//-------------------------------------------------------------------------
//----- file: stringconversioneffort.c ------------------------------------
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ gcc -o sce stringconversioneffort.c
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//Outputs:
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce abcd abcde
Effort Required to convert
"abcd"   into
"abcde"
total_effort = 1
characters to be added = 1
characters to be deleted = 0
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce abcde abc
Effort Required to convert
"abcde"   into
"abc"
total_effort = 2
characters to be added = 0
characters to be deleted = 2
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce a1b2c3 ac
Effort Required to convert
"a1b2c3"   into
"ac"
total_effort = 4
characters to be added = 0
characters to be deleted = 4
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce agd 4e
Effort Required to convert
"agd"   into
"4e"
total_effort = 5
characters to be added = 2
characters to be deleted = 3
//-------------------------------------------------------------------------


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//Logic used:
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
Concept of Longest Common Subsequence [LCS] is used to solve the problem.
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

The value c[length_x][length_y] in above function stores length of LCS
of string_x and string_y. This LCS length helps in finding the effort required.
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------

Android App for Computer Science and Engineering exams.

• Check out this simple App which will helps you remain in touch with concepts from Computer Science and Engineering. 
• Concepts from following subjects are included in this App :

• Maths
• Digital Logic
• Computer Architecture and Organization
• Database Systems
• Operating Systems
• Compilers
• Computer Networks
• Software Engineering
• Data Structures and Algorithms

Alternatively, you can play with this App by simply solving "match the columns".


Minimum requirement :

• Firmware\ Android Version 2.1 or higher.

How to Play :

• As in "match the columns", there are 2 columns. Left column for Questions and right column for Answers as shown below :

• You simply try to match each Question with its corresponding Answer.Trick is to match the background colors. 
• That means, the background color of Question should match the background color of its corresponding Answer. 
• You can change the background color of Answers by simply clicking on them.

       

For example consider this "match the column" on Time Complexity :

• Question : Counting Sort
• Correct Answer : O(n)

• Question : Balanced Binary Search Tree
• Correct Answer : O(log(n))

• Question : Selection Sort
• Correct Answer : O(N*N)

• Question : Heap Sort 
• Correct Answer : O(N*log(N))

Please see below pictorial explanation of what does it means by matching the background colors:

Correctly matched the column

Incorrectly matched the column

App Heading :

• While using the App you will notice following heading : 

•  G-YYYY : means this SET was asked in Graduate Aptitude Test In Engineering [Computer Science and Engineering] Year YYYY.

 

Feedback, Suggestions and Contributions : 

• Please use this email address for communication [ csexapp@yahoo.com ]
• Feedback, suggestions and corrections are most welcomed. 
• Also, you can contribute your SETS for other to download. Send four Questions and their corresponding Answers @ the mentioned email address.
• Contributors page :  Appreciating the contributors.

History :  

• Friday, April 19, 2013

• Released  Application Version 1.0
• After installation,  initially the App will contain 10 SETS in its database.
• More SETS can be downloaded as and when they are published.
  

• Monday, April 29, 2013

• Released  New SETS [Question 11 to 20]
• Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.
  

• Tuesday, May 07, 2013

• Released  New SETS [Question 21 to 30]
• Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.

• Monday, June 03, 2013

• Released  New SETS [Question 31 to 40]
• Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.

• Thursday, October 24, 2013

• App Download Count reached 1K mark.

• Tuesday, November 07, 2017

• Released App Version 2.0
• Please remove previous version and install this new version.

• Monday, February 19, 2018

• Released  New SETS [Question 41 to 50]
• Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.

• Sunday, February 25, 2018

• App Download Count reached 2K mark.

• Tuesday, May 15, 2018

• Released  New SETS [Question 51 to 60]
• Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.

• Thursday, May 02, 2019

• Released  New SETS [Question 61 to 70]
• Please use "Download SETS..." facility in the App to directly add New Questions to existing database of Questions.

Direct Download  Link for .apk File:
CSExApp.apk File


Also Available on SlideME

CSExApp Contributors

Appreciating the following Contributors :

1. Shankar / Mumbai / Set 8
2. Siddhesh / Mumbai / Testing the App

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