Take the recursive Java program Levenshtein.java and convert it to the equivalen
ID: 3787304 • Letter: T
Question
Take the recursive Java program Levenshtein.java and convert it to the equivalent C program. 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. " ); testDistance( "kitten", "kitten", 0 ); testDistance( "kitten", "sitting", 3 ); testDistance( "kitten", "mittens", 2 ); testDistance( "balloon", "saloon", 2 ); testDistance( "hello", "doggo", 4 ); testDistance( " hi", " hi", 2 ); System.out.println( " Testing empty/edge cases. " ); testDistance( "", "", 0 ); testDistance( "hello", "", 5 ); testDistance( "", "doggo", 5 ); testDistance( "a", "b", 1 ); testDistance( "b", "b", 0 ); testDistance( " ", " ", 0 ); System.out.println( " This might take a while... " ); testDistance( "12345678901", "123456789012", 1 ); // how many chars are we looking at? System.out.println( " These tests will be opposite in the C version " ); testDistance( "kitten", "mittens", 3 ); // ???? testDistance( "totally", "different", 9 ); System.out.println( " Total 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(levenshtein(deleteS, t) + 1, levenshtein(s, deleteT) + 1, levenshtein(deleteS, deleteT) + cost); } return distance; } public static int minimum( int... minimum ) // varargs! see: https://docs.oracle.com/javase/8/docs/technotes/guides/language/varargs.html { 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; } }
Explanation / Answer
PROGRAM CODE:
/*
* levenshtein.c
*
* Created on: 05-Feb-2017
* Author: kasturi
*/
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
static int testsFailed = 0;
static int testsExecuted = 0;
static int levenshtein( char[] , char[] );
static void testDistance( char[], char[], int );
static int minimum( int[], int);
char *substring(char*, int, int );
int endsWith(char[], char[]);
int main(void) {
printf( "Testing typical cases. " );
testDistance( "kitten", "kitten", 0 );
testDistance( "kitten", "sitting", 3 );
testDistance( "kitten", "mittens", 2 );
testDistance( "balloon", "saloon", 2 );
testDistance( "hello", "doggo", 4 );
testDistance( " hi", " hi", 2 );
printf( " Testing empty/edge cases. " );
testDistance( "", "", 0 );
testDistance( "hello", "", 5 );
testDistance( "", "doggo", 5 );
testDistance( "a", "b", 1 );
testDistance( "b", "b", 0 );
testDistance( " ", " ", 0 );
printf( " This might take a while... " );
testDistance( "12345678901", "123456789012", 1 ); // how many chars are we looking at?
printf( " These tests will be opposite in the C version " );
testDistance( "kitten", "mittens", 3 ); // ????
testDistance( "totally", "different", 9 );
printf( " Total number of tests executed: %d ", testsExecuted );
printf( "Number of tests passed: %d " , (testsExecuted - testsFailed) );
printf( "Number of tests failed: %d " , testsFailed );
return 0;
}
int endsWith(char string[], char substring1[])
{
char temp[100];
int pos = strlen(string) - strlen(substring1);
strcpy(temp, substring(string, pos, strlen(string)));
return strcmp(temp, substring1);
}
static int minimum( int minimum[], int length)
{
int min = 0;
assert(length > 0 );
if ( length > 0 )
{
min = minimum[0];
for ( int i = 1; i < length; i++ )
{
if ( minimum[i] < min )
{
min = minimum[i];
}
}
}
return min;
}
char *substring(char *string, int position, int length)
{
char *pointer;
int c;
pointer = malloc(length+1);
if (pointer == NULL)
{
printf("Unable to allocate memory. ");
exit(1);
}
for (c = 0 ; c < length ; c++)
{
*(pointer+c) = *(string+position);
string++;
}
*(pointer+c) = '';
return pointer;
}
static int levenshtein( char s[], char t[] )
{
int cost;
int distance;
char deleteS[100];
char deleteT[100];
if (strlen(s) == 0)
{
distance = strlen(t);
}
else if (strlen(t) == 0)
{
distance = strlen(s);
}
else
{
if (s[0] == t[0])
{
cost = 0;
}
else
{
cost = 1;
}
strcpy(deleteS , substring(s, 1, strlen(s)));
strcpy(deleteT ,substring(t, 1, strlen(t)));
assert(strlen(deleteS) == (strlen(s) - 1));
assert(strlen(deleteT) == (strlen(t) - 1));
assert(endsWith(s, deleteS) == 0);
assert(endsWith(t, deleteT) == 0);
int min[] = {levenshtein(deleteS, t) + 1, levenshtein(s, deleteT) + 1, levenshtein(deleteS, deleteT) + cost};
distance = minimum(min, sizeof(min)/sizeof(int));
}
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 );
}
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);
testsFailed++;
}
testsExecuted++;
}
OUTPUT:
Testing typical cases.
Passed! You can get from 'kitten' to 'kitten' in 0 moves.
Passed! You can get from 'kitten' to 'sitting' in 3 moves.
Passed! You can get from 'kitten' to 'mittens' in 2 moves.
Passed! You can get from 'balloon' to 'saloon' in 2 moves.
Passed! You can get from 'hello' to 'doggo' in 4 moves.
Passed! You can get from ' hi' to ' hi' in 2 moves.
Testing empty/edge cases.
Passed! You can get from '' to '' in 0 moves.
Passed! You can get from 'hello' to '' in 5 moves.
Passed! You can get from '' to 'doggo' in 5 moves.
Passed! You can get from 'a' to 'b' in 1 moves.
Passed! You can get from 'b' to 'b' in 0 moves.
Passed! You can get from ' ' to ' ' in 0 moves.
This might take a while...
Passed! You can get from '12345678901' to '123456789012' in 1 moves.
These tests will be opposite in the C version
FAILED: I thought it would take 3 moves, but apparently it takes 1 moves to get from 'kitten' to 'mitten'.
FAILED: I thought it would take 9 moves, but apparently it takes 0 moves to get from '' to ''.
Total number of tests executed: 15
Number of tests passed: 13
Number of tests failed: 2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.