Intermediate Exercism • go

Hamming

Challenge Overview

Calculate the Hamming distance between two DNA strands.

Introduction

Your body is made up of cells that contain DNA. Those cells regularly wear out and need replacing, which they achieve by dividing into daughter cells. In fact, the average human body experiences about 10 quadrillion cell divisions in a lifetime!

When cells divide, their DNA replicates too. Sometimes during this process mistakes happen and single pieces of DNA get encoded with the incorrect information. If we compare two strands of DNA and count the differences between them, we can see how many mistakes occurred. This is known as the “Hamming distance”.

The Hamming distance is useful in many areas of science, not just biology, so it’s a nice phrase to be familiar with :)

Instructions

Calculate the Hamming distance between two DNA strands.

We read DNA using the letters C, A, G and T. Two strands might look like this:

GAGCCTACTAACGGGAT
CATCGTAATGACGGCCT
^ ^ ^  ^ ^    ^^

They have 7 differences, and therefore the Hamming distance is 7.

Implementation notes

The Hamming distance is only defined for sequences of equal length, so an attempt to calculate it between sequences of different lengths should not work.

Dig Deeper

Iterate bytes

Iterate as bytes

// Package hamming is a small library for determining the hamming distance between two strands.
package hamming

import "errors"

// Distance accepts two strands and returns their hamming distance.
func Distance(strand1, strand2 string) (distance int, err error) {
	if len(strand1) != len(strand2) {
		return 0, errors.New("strands must be of equal length")
	}

	for i := range len(strand1) {
		if strand1[i] != strand2[i] {
			distance++
		}
	}
	return distance, nil
}

The Distance() function is defined with named return values which are initialized with their zero values.

The len() function is used to compare the lengths of the strands in bytes. Since at the time of writing all of the characters are ASCII, getting the length of bytes is the same as getting the number of characters. If the strands are not the same length, then 0 is returned along with the new error.

The ways to iterate characters are by Unicode runes, or by each letter being a string, or by each letter being a byte. The runes are from range on a string, the strings from Split(), and the bytes from indexing into the string. Another way to iterate runes is to convert the string to a rune slice and range on it. The difference between ranging on a rune slice vs ranging on a string is that the index returned from a string is the position of the next rune in bytes, not which rune it is. For example, if the first unicode character is two bytes, then the second unicode character index will be 2 when ranging on a string and 1 when ranging on a rune slice. As of the time of this writing we can iterate bytes, since all of the characters are ASCII.

The for loop iterates from 0 until the length of the first strand. Indexing into a string gets the byte at that position. If the bytes are different at the same index for each strand, then the distance is incremented. After the loop is finished, distance is returned along with a nil error.

Iterate runes

Iterate as runes

// Package hamming is a small library for determining the hamming distance between two strands.
package hamming

import (
	"errors"
	"unicode/utf8"
)

// Distance accepts two strands and returns their hamming distance.
func Distance(strand1 string, strand2 string) (distance int, err error) {
	if utf8.RuneCountInString(strand1) != utf8.RuneCountInString(strand2) {
		return 0, errors.New("strands must be of equal length")
	}

	strand1Runes := []rune(strand1)
	strand2Runes := []rune(strand2)

	for idx, rooney := range strand1Runes {
		if rooney != strand2Runes[idx] {
			distance++
		}
	}
	return distance, nil
}

The Distance() function is defined with named return values which are initialized with their zero values.

The utf8 RuneCountInString() function is used to compare the lengths of the strands in runes. This isn’t necessary when all of the input characters are single-byte ASCII, but if any character was a multi-byte character, then the RuneCountInString() function would be needed to give the accurate number of characters. The len() function used on a string would give the number of bytes, which would be inaccurate for returning the number of characters for multi-byte characters.

If the strands don’t have the same number of runes, then 0 is returned along with the new error.

The two strands are used to create rune slices.

The runes of the first strand are iterated. The rune in each iteration is compared with the rune at the same index in the other strand. If the runes are different at the same index for each strand, then the distance is incremented. After the loop is finished, distance is returned along with a nil error.

Source: Exercism go/hamming

💡 View Solution

package hamming

import "errors"

func Distance(a, b string) (int, error) {
    if len(a) != len(b) {
        return 0, errors.New("strands must be of equal length")
    }
    count := 0
    for i := range a {
        if a[i] != b[i] { count++ }
    }
    return count, nil
}