#!/usr/bin/env python3
"""Auto-generated by AGI Loop cycle #1078
Task: Write a Python function that implements Levenshtein edit distance between two strings
Generated: 2026-02-12T19:25:42.282827
"""

def levenshtein_distance(str1, str2):
    # Create a matrix of size (len(str1)+1) x (len(str2)+1)
    matrix = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

    # Initialize the first row and column
    for i in range(len(str1) + 1):
        matrix[i][0] = i
    for j in range(len(str2) + 1):
        matrix[0][j] = j

    # Fill the matrix
    for i in range(1, len(str1) + 1):
        for j in range(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                cost = 0
            else:
                cost = 1
            matrix[i][j] = min(
                matrix[i - 1][j] + 1,    # Deletion
                matrix[i][j - 1] + 1,    # Insertion
                matrix[i - 1][j - 1] + cost  # Substitution
            )

    # The result is the bottom-right cell of the matrix
    return matrix[len(str1)][len(str2)]

if __name__ == '__main__':
    test_str1 = "kitten"
    test_str2 = "sitting"
    distance = levenshtein_distance(test_str1, test_str2)
    print(f"Levenshtein distance between '{test_str1}' and '{test_str2}': {distance}")