Calculating the Hamming distance between two strings with LINQ

Question

I'm in need of help. I'm writing a function that compares the Hamming distance between to string parameters, which means you have to return the number of times the elements at the same index in each string was not the same.

I already manage to finish the method with a for loop, but with this Linq method it only passes 8 out of the 9 tests.

My initial loop:

public static int Distance(string firstStrand, string secondStrand)
{
    int count = 0;

    if(firstStrand.Length>secondStrand.Length || firstStrand.Length<secondStrand.Length){throw new ArgumentException();}
    else if(firstStrand.Length == 0 || secondStrand.Length == 0){count = 0;}
    else if(firstStrand == secondStrand){count = 0;}
    else
    {
        for(int i = 0; i < firstStrand.Length; i++)
        {
            if(firstStrand[i] != secondStrand[i])
            {
                count++;
            }
        }
    }


    return count;
}

My attempt with Linq:

public static int Distance(string firstStrand, string secondStrand)
{
    int count = 0;

    if (firstStrand.Length > secondStrand.Length || firstStrand.Length < 
    secondStrand.Length) { throw new ArgumentException(); }
    if(firstStrand.Length == 0 && secondStrand.Length == 0) { count = 0; }
    else if (firstStrand == secondStrand) { count = 0; }
    else
    {

        var result = firstStrand.Zip(secondStrand, (c, b) => c != b);

        foreach (int value in result)
        {
            count++;
        }

    }
        return count;
}

}

The test file:

[Fact]
public void Empty_strands()
{
    Assert.Equal(0, Hamming.Distance("", ""));
}

[Fact]
public void Single_letter_identical_strands()
{
    Assert.Equal(0, Hamming.Distance("A", "A"));
}

[Fact]
public void Single_letter_different_strands()
{
    Assert.Equal(1, Hamming.Distance("G", "T"));
}

[Fact]
public void Long_identical_strands()
{
    Assert.Equal(0, Hamming.Distance("GGACTGAAATCTG", "GGACTGAAATCTG"));
}

[Fact]
public void Long_different_strands()
{
    Assert.Equal(9, Hamming.Distance("GGACGGATTCTG", "AGGACGGATTCT"));
}

[Fact]
public void Disallow_first_strand_longer()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("AATG", "AAA"));
}

[Fact]
public void Disallow_second_strand_longer()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("ATA", "AGTG"));
}

[Fact]
public void Disallow_left_empty_strand()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("", "G"));
}

[Fact]
public void Disallow_right_empty_strand()
{
    Assert.Throws<ArgumentException>(() => Hamming.Distance("G", ""));
}

}

I hope you guys can point me in the direction. I'm still fairly new to Linq.

Answer 1

1. Install System.Numerics.Tensors Package (From Microsoft).

2. Call it

   ReadOnlySpan<byte> byte1 = [1, 2, 3, 4, 5];
   ReadOnlySpan<byte> byte2 = [1, 2, 3, 4, 5];
   int hammingDistance = System.Numerics.Tensors.TensorPrimitives.HammingDistance(byte1, byte2);
   

Here is the documentation page.
Here is the source code

Answer 2

The problem with your implementation is that while you compare the character values, you never take into account the results of that comparison. You just count the total length of the compared values, which will be the same as the length of the input strings.

You have nine test cases, but even with this serious flaw in your implementation, eight succeed because:

• Zero-length strings will trivially result in a count of zero
• Identical strings will result in a count of the length of the string, via your == optimization
• Test cases involving different-length strings throw exceptions, so never care about the computed count

There is only one test case that actually exercises the comparison code in a non-trivial way, and so of course that's the one that fails.

It seems to me a much more effective implementation of your method would look like this:

public static int Distance(string firstStrand, string secondStrand)
{
    if (firstStrand.Length != secondStrand.Length) { throw new ArgumentException(); }

    return firstStrand.Zip(secondStrand, (c, b) => c != b).Count(f => f);
}

Some notes:

• There's no point in comparing the Length property so many times. Checking whether the first length is less than the second, and then whether it's greater than the second, is the same as checking whether they are not equal. And once you've cleared that requirement, then you don't need to check both lengths to know whether both lengths are zero.
• There's also no point in trying to optimize special-cases like you have. To compare the strings for equality, you need to scan through both anyway. That "optimization" can actually hurt performance, at least for certain kinds of data, because it will lead to excessive iterations of the string. And optimizing the zero-length case also isn't useful; zero-length strings are the least of your worries when it comes to making this comparison. Much better to just keep the code simple.

Answer 3

This linq-implementation passes all the tests:

public static int Distance(string firstStrand, string secondStrand)
    {
        var count = 0;

        if (firstStrand.Length > secondStrand.Length || firstStrand.Length < secondStrand.Length) { throw new ArgumentException(); }

        if (firstStrand.Length == 0 || secondStrand.Length == 0) { count = 0; }
        else if (firstStrand == secondStrand) { count = 0; }
        else
        {
            count += firstStrand.Where((t, i) => t != secondStrand[i]).Count();
        }

        return count;
    }