Verhoeff check digit algorithm

Question

A recent question on credit card validation here on Code Review, led 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.

Answer 1

Your tests look ok. I have three concerns:

• If I read correctly, your "single digit modifications" test cycle is going to have over 1000000000000000000000 cycles. That's... not practical. pick a compromise.
• The positive tests are checking calculate and validate. I see no reason not to check both in your negative tests too.
• You're only checking syntactically valid input. This ties into your question about what the type signature should be.
  • You have a few options for your type signature. Without going over the compromises in detail, I would suggest that the first line in calculate and validate should be an isdigit() check, and raise an exception if it fails.
  • Whatever you do for types, your tests should check that it's handling edge cases as intended, whatever it is you decide you intend.
    • empty strings
    • a single digit (could break validate)
    • all zeros
    • whitespace in different configurations
    • illegal characters

You don't have to address all these points, depending on the use-cases of this project, and whatever else is going on in your life, it may be fine to call it good enough as-is.

Answer 2

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