Levenshtein distance for block-answer comparison

Measuring similarity between block-based answers is useful in BlockSu, but similar text does not prove equivalent programs. I treat Levenshtein distance as a measure of insertions, deletions and substitutions rather than a correctness judge. The archive's Compute and GetSimilarityRatio flow applies that idea to answer comparison; this character-level demonstration is not the complete scoring implementation.

Define the distance before turning it into a score

Changing kitten to sitting takes three edits: replace k with s, replace e with i and append g. The classic unit-cost model assigns one to each insertion, deletion and substitution. It does not add a special one-step transposition rule for swapping adjacent characters; that would be a different variant.

static int Distance(string left,string right)
{
    ArgumentNullException.ThrowIfNull(left);
    ArgumentNullException.ThrowIfNull(right);
    var costs=new int[left.Length+1,right.Length+1];
    for(int i=0;i<=left.Length;i++)costs[i,0]=i;
    for(int j=0;j<=right.Length;j++)costs[0,j]=j;
    for(int i=1;i<=left.Length;i++)
        for(int j=1;j<=right.Length;j++)
        {
            int replace=costs[i-1,j-1]+(left[i-1]==right[j-1]?0:1);
            costs[i,j]=Math.Min(replace,Math.Min(costs[i-1,j]+1,costs[i,j-1]+1));
        }
    return costs[left.Length,right.Length];
}
static double Similarity(string a,string b) =>
    a.Length==0&&b.Length==0?1:1d-(double)Distance(a,b)/Math.Max(a.Length,b.Length);
Console.WriteLine(Distance("kitten","sitting"));
Console.WriteLine(Similarity("",""));
Console.WriteLine(Distance("<move/>","<turn/>"));

In a .NET 10 console project the outputs are three, one for two empty strings' similarity, and four for the final XML-like pair. Distance rejects null input. Similarity also needs a caller-side non-null contract or equivalent guards if it is exposed to untrusted input; this helper is not a complete request validation boundary.

Each matrix cell answers a prefix problem

costs[i,j] stores the minimum cost of transforming the first i units of the left string into the first j units of the right. Creating a j-unit string from an empty prefix takes j insertions; deleting an i-unit prefix takes i deletions. Those are the initial row and column.

A new cell compares deletion from the upper neighbor, insertion from the left neighbor and a match or substitution from the diagonal. Equal characters add no diagonal cost. Math.Min combines already computed prefix results instead of recomputing the same subproblems. That is the concrete dynamic programming behavior behind the matrix.

The similarity formula is an application choice

The sample uses one minus distance divided by the longer length. For kitten/sitting it is 1−3/7, approximately 0.571. Levenshtein distance itself does not define this percentage. One changed character has a different normalized effect in a short answer than in a long answer, so thresholds need representative examples rather than a few favorable cases.

Returning one for two empty strings is a mathematical special-case policy. An educational workflow does not have to award full credit to an unanswered question. Input completeness belongs before similarity scoring. A high textual score is still not evidence that the program produces the correct behavior.

Raw Blockly XML contains non-semantic differences

Generated block IDs, metadata and insignificant whitespace can increase textual distance. Conversely, changing one operator or numeric value can drastically alter behavior while barely changing the text. The application must decide which differences are meaningful instead of accidentally awarding points for matching XML formatting.

Normalization also has limits. Deleting identifiers used by variable references can break relationships; sorting blocks or arguments can change execution meaning. Structural comparison, consistent identifier mapping and behavioral testing are separate techniques. The archive's word-level comparison should not be described as identical to this character-level sample.

Bound the input and understand the character model

For lengths m and n, this implementation takes O(mn) time and matrix memory. Keeping only two rows can reduce memory when only the distance is needed; reconstructing an edit path requires additional information. Large submitted XML needs a size limit, and threshold-only decisions may justify a more specialized bounded calculation.

C# char comparison operates on UTF-16 code units, not necessarily one unit per visible character. Unicode normalization and case rules are separate choices. Lowercasing arbitrary XML is not a valid general normalization strategy because element names and values can carry case-sensitive meaning.

Test equal strings, one insertion, one deletion, empty pairs and answers that are textually close but behaviorally different. Explain the decision derived from the number alongside those cases; the metric alone does not define the grading policy.

NIST definition of Levenshtein distance; The .NET Unicode and character model.