#include <iostream>
#include <cassert>
#include <algorithm>
#include <cstddef>

// The Hamming distance between two strings
// of equal length is the number of positions
// at which their characters differ.
//
// The Levenshtein distance is a more general
// measure of the difference between two strings.
//
// Given a string, we can perform a single-character
// edit by doing one of the following:
//   1. replacing an existing character with another,
//   2. deleting a character from the string, or
//   3. inserting a new character into the string.
//
// The Levenshtein distance is the minimum number
// of single-character edits required to transform
// one string into another.
//
// For example, all of the following pairs of
// strings have a Levenshtein distance of one:
//
//     birth      berth
//     catching   caching
//     not        knot
//
// Calculating the Levenshtein distance can be
// done recursively, but proving the correctness
// of this recursion is beyond the scope of this
// course. Nevertheless, you can implement it.
//
// Let lev(a, b) denote the Levenshtein distance
// between strings a and b.
//
//     lev(a, b) =
//
//       length(a)                    if b == "",
//
//       length(b)                    if a == "",
//
//       lev(a[1,..], b[1,..])        if a[0] == b[0],
//
//       1 + min(
//           lev(a[1,..], b[1,..]),
//           lev(a[1,..], b),
//           lev(a, b[1,..])
//       )                            otherwise.
//
// The three recursive calls in the final case
// correspond to replacing, deleting, and
// inserting a character, respectively.
//
// Here, a[1,..] represents the string a
// starting at its second character.
//
// If a is the address of the first character
// of a null-terminated C++ string, then a + 1
// is the address of its second character.
//
// You may want to implement the helper function
// string_length() first.
//
// Note that this recursive algorithm can perform
// many repeated calculations. It is suitable
// for short strings, but becomes very slow for
// longer strings.

// Function declarations
int main();

std::size_t levenshtein(
    char const str1[],
    char const str2[]
);

std::size_t string_length(
    char const str[]
);

// Function definitions
int main() {
    std::cout << levenshtein(
        "birth", "berth"
    ) << std::endl;

    std::cout << levenshtein(
        "catching", "caching"
    ) << std::endl;

    std::cout << levenshtein(
        "not", "knot"
    ) << std::endl;

    std::cout << levenshtein(
        "bear", "bare"
    ) << std::endl;

    // Test the base cases.
    assert( levenshtein( "", "" ) == 0 );
    assert( levenshtein( "cat", "" ) == 3 );
    assert( levenshtein( "", "cat" ) == 3 );

    // Test identical strings.
    assert( levenshtein( "cat", "cat" ) == 0 );

    // Test a replacement, deletion, and insertion.
    assert( levenshtein( "cat", "cut" ) == 1 );
    assert( levenshtein( "cats", "cat" ) == 1 );
    assert( levenshtein( "cat", "cats" ) == 1 );

    // Test a pair requiring multiple edits.
    assert( levenshtein( "bear", "bare" ) == 2 );

    return 0;
}

std::size_t levenshtein(
    char const str1[],
    char const str2[]
) {
    assert( str1 != nullptr );
    assert( str2 != nullptr );

    // Your implementation goes here.

    return 0;
}

std::size_t string_length(
    char const str[]
) {
    assert( str != nullptr );

    // Your implementation goes here.

    return 0;
}





































// Reference implementation
/*
std::size_t levenshtein(
    char const str1[],
    char const str2[]
) {
    assert( str1 != nullptr );
    assert( str2 != nullptr );

    if ( str1[0] == '\0' ) {
        return string_length( str2 );
    } else if ( str2[0] == '\0' ) {
        return string_length( str1 );
    } else if ( str1[0] == str2[0] ) {
        return levenshtein( str1 + 1, str2 + 1 );
    } else {
        // Replace the first character.
        std::size_t const result11{
            levenshtein( str1 + 1, str2 + 1 )
        };

        // Delete the first character of str1.
        std::size_t const result10{
            levenshtein( str1 + 1, str2 )
        };

        // Insert the first character of str2
        // at the beginning of str1.
        std::size_t const result01{
            levenshtein( str1, str2 + 1 )
        };

        return 1 + std::min(
            result11, std::min( result10, result01 )
        );
    }
}

std::size_t string_length(
    char const str[]
) {
    assert( str != nullptr );

    for ( std::size_t k{ 0 }; true; ++k ) {
        if ( str[k] == '\0' ) {
            return k;
        }
    }

    // This point should never be reached.
    assert( false );
    return 0;
}
*/