5
\$\begingroup\$

A DNI (Spain's National Identification Document) is formed by 8 digits and a letter, and they are related to one another as follows:

number % 23 -> letter_index

Where the sequence of letters to be indexed is TRWAGMYFPDXBNJZSQVHLCKET

The following program allows calculating the letter given the number, finding some missing numbers, and finding all possible DNIs given some of the numbers and the letter:

from dataclasses import dataclass, field
from typing import Optional, List


@dataclass
class Dni:

    LENGTH_NUMS_ONLY = 8
    LENGTH = LENGTH_NUMS_ONLY + 1

    number: Optional[int] = None
    letter: Optional[str] = None
    missing_digits: List[int] = field(default_factory=lambda: [])

    def get_number_as_str(self) -> str:
        '''Return the number representing unknown digits as "?"

        For example, if number=11_011_111 and missing_digits=[2],
        returned value is "11?11111"
        '''
        number = self.number if self.number is not None else 0
        number_as_str = str(number).zfill(Dni.LENGTH_NUMS_ONLY)

        # number is converted to list so that missing digits can be replaced
        number_as_list = list(number_as_str)
        if self.missing_digits:
            for missing_digit in self.missing_digits:
                number_as_list[missing_digit] = '?'

        return ''.join(number_as_list)

    def get_letter_as_str(self) -> str:
        '''Return the letter or "?" if lettter is not known'''
        return self.letter.upper() if self.letter else '?'

    def __str__(self):
        return self.get_number_as_str() + self.get_letter_as_str()

    @classmethod
    def from_dni(clss, dni):
        return Dni(dni.number, dni.letter, [i for i in dni.missing_digits])
from typing import Iterable, Generator, Optional
import itertools

from dni_calculator import Dni


class DniCalculator:

    _LETTERS = 'TRWAGMYFPDXBNJZSQVHLCKET'

    def find_letter(self, dni: Dni) -> Optional[Dni]:
        '''Find the letter corresponding to the given dni

        Example:
            find_letter(Dni(11111111)) -> 11111111H

        Args:
            dni: The dni whose letter is to be found.
                All of its digits have to be present
        '''
        if dni.missing_digits and len(dni.missing_digits) != 0:
            print(f'Invalid dni given: "{dni}". '
                + 'There cannot be missing numbers when finding a letter')
            return None
        if dni.letter is not None:
            if self._check_valid(dni):
                print(f'The given dni is already complete and valid: "{dni}"')
                return Dni.from_dni(dni)
            else:
                print(f'Letter provided. Wont look for it "{dni}"')
                return None
        res_dni = Dni.from_dni(dni)
        res_dni.letter = self._get_letter(dni.number)
        return res_dni

    def _get_letter(self, dni_number: int) -> str:
        '''Return the letter corresponding to the given dni_number'''
        return self._LETTERS[dni_number % 23]

    def _check_valid(self, dni: Dni) -> bool:
        '''Check whether the given dni is valid

        Args:
            dni: A Dni with all digits and letter present
                Example: Dni(11_111_111, 'H')
        '''
        return self._get_letter(dni.number) == dni.letter

    def find_missing_num(self, dni: Dni) -> Optional[Dni]:
        '''Find the first complete dni valid for the given dni

        Args:
            dni: The dni for which to find the missing numbers

                It should have at least one missing digit.
                It also has to contain the letter.

                Examples:
                    Dni(11_111_011, 'H', [5])
                    Dni(11_100_111, 'H', [3, 4])
        '''
        return next(self.find_all_possible_dnis(dni), None)

    def find_all_possible_dnis(self, dni: Dni) -> Generator[Dni, None, None]:
        '''Find the all of the valid dnis for the given dni

        Args:
            dni: The dni for which to find the missing numbers

                It should have at least one missing digit.
                It also has to contain the letter.

                Examples:
                    Dni(11_111_011, 'H', [5])
                    Dni(11_100_111, 'H', [3, 4])
        '''
        if dni.letter is None:
            print(f'Cannot fing missing numbers if no letter is given: "{dni}"')
            return None

        num_missing_digits = len(dni.missing_digits)
        if num_missing_digits == 0:
            if self._check_valid(dni):
                print(f'The given dni is already complete and valid: "{dni}"')
                yield Dni.from_dni(dni)
                return None
            else:
                print(f'All digits provided. Unable to find missing ones "{dni}"')
                return None

        res_dni = Dni.from_dni(dni)
        missing_digits = res_dni.missing_digits
        res_dni.missing_digits = []
        prev_digits_to_check = 0
        for digits_to_check in self._get_generator_for_digits(missing_digits):
            res_dni.number -= prev_digits_to_check
            res_dni.number += digits_to_check
            prev_digits_to_check = digits_to_check
            if self._check_valid(res_dni):
                yield Dni.from_dni(res_dni)

    def _get_generator_for_digit(self, digit_pos: int) -> Generator[int, None, None]:
        '''Return the different value the digit at position digit_pos can have

        Examples:
            digit_pos=7 -> 0, 1, 2, ..., 8, 9
            digit_pos=6 -> 0, 10, 20, ..., 80, 90
            digit_pos=0 -> 0, 10_000_000, ..., 90_000_000

        Args:
            digit_pos: A number from 0 to 9
        '''
        power = Dni.LENGTH_NUMS_ONLY - digit_pos
        for number in range(0, 10 ** power, 10 ** (power-1)):
            yield number

    def _get_generator_for_digits(self, digits_pos: Iterable[int]) -> Generator[int, None, None]:
        '''Returns all combinations of values the digits at position digits_pos can have

        Examples:
            digit_pos=(7,) -> 0, 1, 2, ..., 8, 9
            digit_pos=(6,) -> 0, 10, 20, ..., 80, 90
            digit_pos=(0,) -> 0, 10_000_000, ..., 90_000_000
            digit_pos=(6, 7) -> 0, 1, 2, ..., 98, 99
            digit_pos=(5, 7) -> 0, 1, 2, ..., 9, 100, 101, ... 109, 200, ..., 908, 909
            digit_pos=(0, 5) -> 0, 10_000_000, 10_000_100, 10_000_200, ..., 90_000_900

        Args:
            digits_pos: An iterable whose values have to be between 0 and 9
                For the output to be in an expectable order, the iterable
                has to return the numbers in increasing order.

                For example, if digits_pos=(7, 6), the yielded values will be:
                0, 10, 20, 30, ... 90, 1, 11, 21, ...
        '''
        digits_generators = [self._get_generator_for_digit(digit_pos)
                             for digit_pos in digits_pos]
        digits_generator = itertools.product(*digits_generators)
        # return digits_generator
        return map(sum, digits_generator)

And here are some tests:

from dni_calculator import Dni, DniCalculator

dni_calc = DniCalculator()

assert dni_calc.find_letter(Dni(11_111_111)) == Dni(11_111_111, 'H')
assert dni_calc.find_letter(Dni(71_091_510)) == Dni(71_091_510, 'M')
assert dni_calc.find_letter(Dni(82_416_679)) == Dni(82_416_679, 'C')

assert dni_calc.find_missing_num(Dni(11_111_011, 'H', missing_digits=[5])) == Dni(11_111_111, 'H')
assert dni_calc.find_missing_num(Dni(75_623_008, 'E', missing_digits=[5])) == Dni(75_623_608, 'E')
assert dni_calc.find_missing_num(Dni(20_602_203, 'M', missing_digits=[3, 6])) == Dni(20_612_283, 'M')

dnis_generator = dni_calc.find_all_possible_dnis(Dni(5240700, 'Q', missing_digits=[6, 7]))
expected_results = (
    Dni(5240704, 'Q'),
    Dni(5240727, 'Q'),
    Dni(5240750, 'Q'),
    Dni(5240773, 'Q'),
    Dni(5240796, 'Q'),
 )
for dni, expected_result in zip(dnis_generator, expected_results):
    assert dni == expected_result

The full code providing a simple CLI interface using fire can be found at m-alorda/dni_calculator

\$\endgroup\$
3
\$\begingroup\$

Basics

PEP257 asks for double quotes and not single quotes for docstrings.

These:

LENGTH_NUMS_ONLY = 8
LENGTH = LENGTH_NUMS_ONLY + 1

should be type-hinted as ClassVar[int].

By convention the class reference variable for class methods is cls, not clss.

from_dni does not actually refer to cls, but it should: rather than constructing via Dni, you should construct cls. Beyond that, though, I'd sooner expect this to be an instance method copy that returns a copy of self.

Ideally Dni should be made immutable by passing frozen=true to its decorator. This will reveal some design warts: currently DniCalculator is responsible for mutating Dni.missing_digits, but it should not be.

_get_generator_for_digit may be static, or better yet a class method on Dni itself.

This:

print(f'Invalid dni given: "{self}". '
      + 'There cannot be missing numbers when finding a letter')

doesn't need the + and can use implicit concatenation.

find_letter should raise instead of print. Printing can be done at the outer level.

Typo: lettter -> letter

[i for i in dni.missing_digits] can just be list(dni.missing_digits).

_check_valid would be more natural as a @property is_valid on Dni itself.

This test:

for dni, expected_result in zip(dnis_generator, expected_results):

hides a failure mode where there is a length mismatch. Using zip_longest will fix this.

Congruential acceleration

Recognize that a problem such as finding all numbers for

052407??Q

is really a congruence relation of the form

$$ 5,240,700 + 10x + y \equiv 16 \mod 23 $$

You should be able to apply equivalence relation identities such that you find all answers analytically rather than by brute force; for your example:

$$ y \equiv 16 - 5,240,700 \mod 23 $$ $$ y \equiv 4 \mod 23 $$ $$ y = 4 + 23 n, 0 \le n \le 4 $$

I've not shown this in the implementation below.

Suggested

from dataclasses import dataclass
from typing import Iterable, Optional, ClassVar, Tuple, Sequence
import itertools


@dataclass(frozen=True)
class Dni:
    LETTERS: ClassVar[str] = 'TRWAGMYFPDXBNJZSQVHLCKE'
    LENGTH_NUMS_ONLY: ClassVar[int] = 8
    LENGTH: ClassVar[int] = LENGTH_NUMS_ONLY + 1

    digits: Tuple[Optional[int], ...]
    letter: Optional[str] = None

    @classmethod
    def from_number(cls, x: int, letter: Optional[str] = None) -> 'Dni':
        if x >= 10**cls.LENGTH_NUMS_ONLY:
            raise ValueError(f'{x} has incorrect length')
        return cls(
            digits=tuple(int(c) for c in str(x)),
            letter=letter,
        )

    @classmethod
    def parse(cls, s: str) -> 'Dni':
        *digits, letter = s
        if len(digits) != cls.LENGTH_NUMS_ONLY:
            raise ValueError(f'{s} has incorrect length')

        return cls(
            digits=tuple(
                None if d == '?' else int(d) for d in digits
            ),
            letter=None if letter == '?' else letter,
        )

    @property
    def is_complete(self) -> bool:
        return (
            self.letter is not None and
            not any(d is None for d in self.digits)
        )

    @property
    def number(self) -> int:
        x = 0
        for digit in self.digits:
            if digit is None:
                raise ValueError('Partial number cannot be linearised')
            x = 10*x + digit
        return x

    @property
    def number_as_str(self) -> str:
        """Return the number representing unknown digits as "?"

        For example, if number=11_011_111 and missing_digits=[2],
        returned value is "11?11111"
        """

        number_as_list = []
        for d in self.digits:
            number_as_list += '?' if d is None else str(d)

        return ''.join(number_as_list)

    @property
    def letter_as_str(self) -> str:
        """Return the letter or "?" if letter is not known"""
        if self.letter is None:
            return '?'
        return self.letter

    def __str__(self) -> str:
        return self.number_as_str + self.letter_as_str

    def copy(self) -> 'Dni':
        return Dni(self.digits)

    @classmethod
    def _get_letter(cls, number: int) -> str:
        return cls.LETTERS[number % len(cls.LETTERS)]

    @property
    def expected_letter(self) -> str:
        """Find the letter corresponding to the given dni

        Example:
            expected_letter(Dni(11111111)) -> 11111111H

        Args:
            dni: The dni whose letter is to be found.
                All of its digits have to be present
        """
        return self._get_letter(self.number)

    @classmethod
    def _get_generator_for_digit(cls, digit_pos: int) -> Sequence[int]:
        """Return the different value the digit at position digit_pos can have

        Examples:
            digit_pos=7 -> 0, 1, 2, ..., 8, 9
            digit_pos=6 -> 0, 10, 20, ..., 80, 90
            digit_pos=0 -> 0, 10_000_000, ..., 90_000_000

        Args:
            digit_pos: A number from 0 to 9
        """
        power = cls.LENGTH_NUMS_ONLY - digit_pos
        return range(0, 10**power, 10**(power - 1))

    @classmethod
    def _get_generator_for_digits(cls, digits_pos: Iterable[int]) -> Iterable[int]:
        """Returns all combinations of values the digits at position digits_pos can have

        Examples:
            digit_pos=(7,) -> 0, 1, 2, ..., 8, 9
            digit_pos=(6,) -> 0, 10, 20, ..., 80, 90
            digit_pos=(0,) -> 0, 10_000_000, ..., 90_000_000
            digit_pos=(6, 7) -> 0, 1, 2, ..., 98, 99
            digit_pos=(5, 7) -> 0, 1, 2, ..., 9, 100, 101, ... 109, 200, ..., 908, 909
            digit_pos=(0, 5) -> 0, 10_000_000, 10_000_100, 10_000_200, ..., 90_000_900

        Args:
            digits_pos: An iterable whose values have to be between 0 and 9
                For the output to be in an expectable order, the iterable
                has to return the numbers in increasing order.

                For example, if digits_pos=(7, 6), the yielded values will be:
                0, 10, 20, 30, ... 90, 1, 11, 21, ...
        """
        digits_generators = (cls._get_generator_for_digit(digit_pos)
                             for digit_pos in digits_pos)
        digits_generator = itertools.product(*digits_generators)
        return map(sum, digits_generator)

    @property
    def missing_num(self) -> Optional['Dni']:
        """Find the first complete dni valid for the given dni

        Args:
            dni: The dni for which to find the missing numbers

                It should have at least one missing digit.
                It also has to contain the letter.

                Examples:
                    Dni(11_111_011, 'H', [5])
                    Dni(11_100_111, 'H', [3, 4])
        """
        return next(self.all_possible_dnis, None)

    @property
    def all_possible_dnis(self) -> Iterable['Dni']:
        """Find the all of the valid dnis for the given dni

        Args:
            dni: The dni for which to find the missing numbers

                It should have at least one missing digit.
                It also has to contain the letter.

                Examples:
                    Dni(11_111_011, 'H', [5])
                    Dni(11_100_111, 'H', [3, 4])
        """

        base = sum(
            0 if d is None else d * 10**(self.LENGTH_NUMS_ONLY - i)
            for i, d in enumerate(self.digits, 1)
        )

        digits_pos = [i for i, d in enumerate(self.digits) if d is None]
        for addend in self._get_generator_for_digits(digits_pos):
            number = addend + base
            letter = self._get_letter(number)
            if self.letter is None or letter == self.letter:
                yield Dni.from_number(number, letter)


def test():
    assert Dni.from_number(11_111_111).expected_letter == 'H'
    assert Dni.from_number(71_091_510).expected_letter == 'M'
    assert Dni.from_number(82_416_679).expected_letter == 'C'

    dni = Dni.parse('11111?11H').missing_num
    assert dni.letter == 'H'
    assert dni.number == 11_111_111

    dni = Dni.parse('75623?08E').missing_num
    assert dni.letter == 'E'
    assert dni.number == 75_623_608

    dni = Dni.parse('206?22?3M').missing_num
    assert dni.letter == 'M'
    assert dni.number == 20_612_283

    dnis_generator = Dni.parse('052407??Q').all_possible_dnis
    expected_numbers = (
        5240704,
        5240727,
        5240750,
        5240773,
        5240796,
    )
    for dni, expected_number in itertools.zip_longest(dnis_generator, expected_numbers):
        assert dni.number == expected_number
        assert dni.letter == 'Q'


if __name__ == '__main__':
    test()
\$\endgroup\$
3
  • \$\begingroup\$ Thank you for taking the time to write all of this helpful feedback. I also knew there had to be a better way to find all possible dnis, but I did not know about congruence relations. Lastly, there is something I'm not sure of: Why do you think using property is better than methods? For simple things like number, number_as_str or even expected_letter, I can understand. But for some others, like all_possible_dnis I feel like properties hide the fact that some actual (even expensive) calculation is being done (Dni.parse('????????H').all_possible_dnis) \$\endgroup\$
    – m-alorda
    Aug 31 at 18:48
  • \$\begingroup\$ If you're worried about property computation expense, apply an LRU cache. @property is just syntax sugar and is more convenient to invoke than the equivalent function notation. \$\endgroup\$
    – Reinderien
    Aug 31 at 18:50
  • \$\begingroup\$ I agree with @m-alorda - when creating objects, .methods() are actions the class undertakes on itself, and .properties are characteristics of the object. Conventions help to faciliate communicate between developers. \$\endgroup\$
    – C. Harley
    Sep 1 at 23:10

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.