Question

question : Take the recursive Java program Levenshtein.java and convert it to the equivalent C program.

Tip: You have explicit permission to copy/paste the main method for this question, replacing instances of System.out.println with printf, where appropriate.

• You can get the assert function from assert.h.
• Try running the Java program on the CS macOS machines. You can compile and run the program following the instructions discussed in class.
  • Assertions are disabled by default. You can enable assertions by running java -ea Levenshtein.

code:

public class Levenshtein
{

private static int testsFailed = 0;
private static int testsExecuted = 0;

public static void main( String[] args )
{
System.out.println( "Testing typical cases.\n" );
testDistance( "kitten", "kitten", 0 );
testDistance( "kitten", "sitting", 3 );
testDistance( "kitten", "mittens", 2 );
testDistance( "balloon", "saloon", 2 );
testDistance( "hello", "doggo", 4 );
testDistance( "\t\thi", "\t\t\t\thi", 2 );

System.out.println( "\nTesting empty/edge cases.\n" );
testDistance( "", "", 0 );
testDistance( "hello", "", 5 );
testDistance( "", "doggo", 5 );
testDistance( "a", "b", 1 );
testDistance( "b", "b", 0 );
testDistance( " ", " ", 0 );

System.out.println( "\nThis might take a while...\n" );
testDistance( "12345678901", "123456789012", 1 ); // how many chars are we looking at?

System.out.println( "\n******These tests will be opposite in the C version******\n" );
System.out.println( "\n******These tests **should** FAIL in the C version*******\n" );
testDistance( "kitten", "mitten\0s", 3 ); // ????
testDistance( "\0totally", "\0different", 9 );

System.out.println( "\nTotal number of tests executed: " + testsExecuted );
System.out.println( "Number of tests passed: " + (testsExecuted - testsFailed) );
System.out.println( "Number of tests failed: " + testsFailed );
}

public static void testDistance( String s, String t, int expected )
{
int distance = levenshtein( s, t );

if ( distance == expected )
{
System.out.println( "Passed! You can get from '" + s + "' to '" + t + "' in " + expected + " moves." );
}
else
{
System.out.println( "FAILED: I thought it would take " + expected + " moves, but apparently it takes " + distance +
" moves to get from '" + s + "' to '" + t + "'." );
testsFailed++;
}

testsExecuted++;
}

public static int levenshtein( String s, String t )
{
int cost;
int distance;
String deleteS;
String deleteT;

if (s.length() == 0)
{
distance = t.length();
}
else if (t.length() == 0)
{
distance = s.length();
}
else
{
if (s.charAt(0) == t.charAt(0))
{
cost = 0;
}
else
{
cost = 1;
}

deleteS = s.substring(1);
deleteT = t.substring(1);

assert(deleteS.length() == s.length() - 1);
assert(deleteT.length() == t.length() - 1);

assert(s.endsWith(deleteS));
assert(t.endsWith(deleteT));

distance = minimum(new int[] { levenshtein(deleteS, t) + 1,
levenshtein(s, deleteT) + 1,
levenshtein(deleteS, deleteT) + cost });
}

return distance;
}

public static int minimum( int minimum[] )
{
int min = 0;
assert( minimum.length > 0 );

if ( minimum.length > 0 )
{
min = minimum[0];

for ( int i = 1; i < minimum.length; i++ )
{
if ( minimum[i] < min )
{
min = minimum[i];
}
}
}

return min;
}
}

Answer 1

solution:

Working code implemented in C and appropriate comments provided for better understanding:

Source code for levenshtein.c:

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

#define DIST_SIZE 3 //Defines the size of the array dist[] initalized in levenshtein()
static int testsExecuted = 0;
static int testsFailed = 0;

static int minimum(int m[],int sizeDist)
//recieves a array of ints to compensate for java's varargs
//returns the minimum int of all the values in m[]
{
int min = 0;
assert(sizeDist > 0);
if(sizeDist > 0)
{
min = m[0];
for(int i = 1; i <sizeDist; i++)
{
if(m[i] < min)
{
min = m[i];
}
}
}
return min;
}

static void substring(char a[],char b[],int pos)
//recieves two strings from levenshtein()
//makes b[] into a substring of a[], from position 1 in a[] to the end of a[]
//equivalent to Java's String method substring(int)
//only works when pos is 1, specific to the java version substring input
//does not return anything
{
while(a[pos] != '\0') //start at the position given from levenstein()
{
b[pos-1] = a[pos]; //since we want b[] to start at 0, pos - 1
pos++;
}
b[pos-1] = '\0'; //have to add in the null terminator at the end of the substring b[]
}

static int lengthString(char a[])
//gets the length of a given string
//does ot include the null terminator
//was using strlen at first, but since strlen returns a long it...
//...didnt work very well with the majority of other types (int)
{
int count = 0;
while(a[count] != '\0')
{
count++;
}
return count;
}

#define T 1; //Define True = 1
#define F 0; //Define False= 0
static int endsWith(char a[], char b[])
//checks if the arrays are equal
//equivalent to java's endsWith() method
{
int i = 0;
int equals = T;
while((a[i+1] != '\0') && (b[i] != '\0'))
{
if(a[i+1] != b[i]) //a[i+1] is used because b[] is (at this point) a...
{ //...substring of a[], which holds on less value than a[]...
equals = F; //...compensating for int i being at the start of b[]
}
i++;
}
return equals;
}
static int levenshtein(char s[],char t[])
//recieves strings s[] and t[] from testDistance() to compute moves
{
int cost;
int distance;
char deleteS[strlen(s)];
char deleteT[strlen(t)];
  
if(strlen(s) == 0)
{
distance = (int)strlen(t);
}
else if(strlen(t) == 0)
{
distance = (int)strlen(s);
}
else
{
if(s[0] == t[0])
{
cost = 0;
}
else
{
cost = 1;
}
substring(s,deleteS,1); //substring is called here with pos = 1
substring(t,deleteT,1); //substring is called here with pos = 1
  
int ds = lengthString(deleteS); //ds stands for deleteSLength
int dt = lengthString(deleteT); //dt stands for deleteTLength
int sLenght = lengthString(s);
int tLenght = lengthString(t);
  
assert(ds == (sLenght-1)); //checking deleteSLength is s[] length minus 1
assert(dt == (tLenght-1)); //checking deleteTLength is t[] length minus 1
  
assert(endsWith(s,deleteS)); //endsWith check function called here
assert(endsWith(t,deleteT)); //endsWith check function called here
  
int d0 = levenshtein(deleteS, t) + 1; //I put each recursion call into its own...
int d1 = levenshtein(s, deleteT) + 1; //...variable for more organization and...
int d2 = levenshtein(deleteS, deleteT) + cost; //... easier debugging
int dist[] = {d0,d1,d2};
distance = minimum(dist,DIST_SIZE);
}
return distance;
}

static void testDistance(char s[],char t[], int expected)
{
int distance = levenshtein(s, t);
if(distance == expected)
{
printf("Passed! You can get from '%s' to '%s' in %d moves.",s,t,expected);
printf("\n");
}
else
{
printf("Failed: i thought it would take %d moves, but apparently it takes %d moves to get from '%s' to '%s'.",expected,distance,s,t);
printf("\n");
testsFailed++;
}
testsExecuted++;
}
int main()
{
printf("Testing typical cases.\n" );
testDistance( "kitten", "kitten", 0 );
testDistance( "kitten", "sitting", 3 );
testDistance( "kitten", "mittens", 2 );
testDistance( "balloon", "saloon", 2 );
testDistance( "hello", "doggo", 4 );
testDistance( "\t\thi", "\t\t\t\thi", 2 );
  
  
printf( "\nTesting empty/edge cases.\n" );
testDistance( "", "", 0 );
testDistance( "hello", "", 5 );
testDistance( "", "doggo", 5 );
testDistance( "a", "b", 1 );
testDistance( "b", "b", 0 );
testDistance( " ", " ", 0 );
printf( "\nThis might take a while...\n" );
testDistance( "12345678901", "123456789012", 1 ); // how many chars are we looking at?
  
printf( "\nThese tests will not succeed in the C version\n" );
testDistance( "kitten", "mitten\0s", 3 ); // ????
testDistance( "\0totally", "\0different", 9 );
  
printf( "\nTotal number of tests executed: %d",testsExecuted );
printf("\n");
printf( "Number of tests passed: %d", testsExecuted - testsFailed);
printf("\n");
printf("Number of tests failed: %d",testsFailed);
printf("\n");
printf("Program completed normally.\n");
return 0;
}

Output Screenshots:

Hope it helps, if you like the answer give it a thumbs up. Thank you.