8
\$\begingroup\$

A recent question on credit card validation here on Code Review, lead me down a dark rabbit hole of check digit algorithms. I took a stop at the Verhoeff algorithm and tried to implement it myself.

That lead to the following piece of code:

class Verhoeff:
    """Calculate and verify check digits using Verhoeff's algorithm"""

    MULTIPLICATION_TABLE = (
        (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
        (1, 2, 3, 4, 0, 6, 7, 8, 9, 5),
        (2, 3, 4, 0, 1, 7, 8, 9, 5, 6),
        (3, 4, 0, 1, 2, 8, 9, 5, 6, 7),
        (4, 0, 1, 2, 3, 9, 5, 6, 7, 8),
        (5, 9, 8, 7, 6, 0, 4, 3, 2, 1),
        (6, 5, 9, 8, 7, 1, 0, 4, 3, 2),
        (7, 6, 5, 9, 8, 2, 1, 0, 4, 3),
        (8, 7, 6, 5, 9, 3, 2, 1, 0, 4),
        (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
    )

    INVERSE_TABLE = (0, 4, 3, 2, 1, 5, 6, 7, 8, 9)

    PERMUTATION_TABLE = (
        (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
        (1, 5, 7, 6, 2, 8, 3, 0, 9, 4),
        (5, 8, 0, 3, 7, 9, 6, 1, 4, 2),
        (8, 9, 1, 6, 0, 4, 3, 5, 2, 7),
        (9, 4, 5, 3, 1, 2, 6, 8, 7, 0),
        (4, 2, 8, 6, 5, 7, 3, 9, 0, 1),
        (2, 7, 9, 3, 8, 0, 6, 4, 1, 5),
        (7, 0, 4, 6, 9, 1, 3, 2, 5, 8)
    )

    @classmethod
    def calculate(cls, input_: str) -> str:
        """Calculate the check digit using Verhoeff's algorithm"""
        check_digit = 0
        for i, digit in enumerate(reversed(input_), 1):
            col_idx = cls.PERMUTATION_TABLE[i % 8][int(digit)]
            check_digit = cls.MULTIPLICATION_TABLE[check_digit][col_idx]
        return str(cls.INVERSE_TABLE[check_digit])

    @classmethod
    def validate(cls, input_: str) -> bool:
        """Validate the check digit using Verhoeff's algorithm"""
        check_digit = 0
        for i, digit in enumerate(reversed(input_)):
            col_idx = cls.PERMUTATION_TABLE[i % 8][int(digit)]
            check_digit = cls.MULTIPLICATION_TABLE[check_digit][col_idx]
        return cls.INVERSE_TABLE[check_digit] == 0

I chose to implement it as a class with two class methods because I plan to include other algorithms as well and structuring the code this way seemed reasonable to me.

I'm particularly interested in your feedback on the following aspects:

  1. What do you think about the API? calculate(input_: str) -> str and validate(input_: str) -> bool seem reasonable and symmetric, but I could also imagine using something like calculate(input_: Sequence[int]) -> int/validate(input_: Sequence[int], int) -> bool.
  2. There seems to be reasonable amount of code duplication between the two functions calculate/validate, but I couldn't really wrap my head around how to define one in respect to the other.

In addition to the class above, I also decided to take a shot at some unit tests for the algorithm using pytest.

import string
import itertools

import pytest

from check_sums import Verhoeff

# modification and utility functions to test the check digit algorihm robustness
DIGIT_REPLACEMENTS = {
    digit: string.digits.replace(digit, "") for digit in string.digits
}

def single_digit_modifications(input_):
    """Generate all single digit modifications of a numerical input sequence"""
    for i, digit in enumerate(input_):
        for replacement in DIGIT_REPLACEMENTS[digit]:
            yield input_[:i] + replacement + input_[i+1:]


def transposition_modifications(input_):
    """Pairwise transpose of all neighboring digits

    The algorithm tries to take care that transpositions really change the
    input. This is done to make sure that those permutations actually alter the
    input."""
    for i, digit in enumerate(input_[:-1]):
        if digit != input_[i+1]:
            yield input_[:i] + input_[i+1] + digit + input_[i+2:]


def flatten(iterable_of_iterables):
    """Flatten one level of nesting

    Borrowed from
    https://docs.python.org/3/library/itertools.html#itertools-recipes
    """
    return itertools.chain.from_iterable(iterable_of_iterables)


# Verhoeff algoritm related tests

# Test data taken from 
# https://en.wikibooks.org/wiki/Algorithm_Implementation/Checksums/Verhoeff_Algorithm
VALID_VERHOEF_INPUTS = [
    "2363", "758722", "123451", "1428570", "1234567890120",
    "84736430954837284567892"
]


@pytest.mark.parametrize("input_", VALID_VERHOEF_INPUTS)
def test_verhoeff_calculate_validate(input_):
    """Test Verhoeff.calculate/Verhoeff.validate with known valid inputs"""
    assert Verhoeff.calculate(input_[:-1]) == input_[-1]\
        and Verhoeff.validate(input_)


@pytest.mark.parametrize(
    "modified_input",
    flatten(single_digit_modifications(i) for i in VALID_VERHOEF_INPUTS)
)
def test_verhoeff_single_digit_modifications(modified_input):
    """Test if single digit modifications can be detected"""
    assert not Verhoeff.validate(modified_input)


@pytest.mark.parametrize(
    "modified_input",
    flatten(transposition_modifications(i) for i in VALID_VERHOEF_INPUTS)
)
def test_verhoeff_transposition_modifications(modified_input):
    """Test if transposition modifications can be detected"""
    assert not Verhoeff.validate(modified_input)

The tests cover known precomputed input and check digit values, as well as some of the basic error classes (single-digit errors, transpositions) the checksum was designed to detect. I decided to actually generate all the modified inputs in the test fixture so that it would be easier to see which of the modified inputs cause a failure of the algorithm. So far I have found none.


Note: There is a thematically related question of mine on optimizing the Luhn check digit algorithm.

\$\endgroup\$

This question has an open bounty worth +50 reputation from AlexV ending in 3 days.

The current answers do not contain enough detail.

The existing answer focuses on the algorithm itself. It would be great to also get some feedback on the tests.

  • \$\begingroup\$ Doesn't this heavily hint at simplification of validate? assert Verhoeff.calculate(input_[:-1]) == input_[-1]\ and Verhoeff.validate(input_) \$\endgroup\$ – domen May 30 at 13:06
5
\$\begingroup\$

I've not had much exposure with good tests. So this focuses on the first codeblock.

  1. I think *_TABLE isn't that useful. Instead PERMUTATIONS and INVERSE looks nicer to me.
  2. Given that calculate and validate are almost duplicate functions you should probably define a private helper to handle the common code.
class Verhoeff:
    ...

    @classmethod
    def _find_check_digit(cls, digits):
        check_digit = 0
        for i, digit in digits:
            col_idx = cls.PERMUTATIONS[i % 8][int(digit)]
            check_digit = cls.MULTIPLICATIONS[check_digit][col_idx]
        return check_digit

    @classmethod
    def calculate(cls, input_: str) -> str:
        """Calculate the check digit using Verhoeff's algorithm"""
        check_digit = cls._find_check_digit(enumerate(reversed(input_), 1))
        return str(cls.INVERSES[check_digit])

    @classmethod
    def validate(cls, input_: str) -> bool:
        """Validate the check digit using Verhoeff's algorithm"""
        check_digit = cls._find_check_digit(enumerate(reversed(input_)))
        return cls.INVERSES[check_digit] == 0
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.