Friday, November 22, 2013

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.
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------