Introduction
At the Global Verification Authority, you’ve just been entrusted with a critical assignment.
Across the city, from online purchases to secure logins, countless operations rely on the accuracy of numerical identifiers like credit card numbers, bank account numbers, transaction codes, and tracking IDs.
The Luhn algorithm is a simple checksum formula used to help identify mistyped numbers.
A batch of identifiers has just arrived on your desk.
All of them must pass the Luhn test to ensure they’re legitimate.
If any fail, they’ll be flagged as invalid, preventing mistakes such as incorrect transactions or failed account verifications.
Can you ensure this is done right? The integrity of many services depends on you.
Instructions
Instructions
Determine whether a number is valid according to the Luhn formula.
The number will be provided as a string.
Validating a number
Strings of length 1 or less are not valid.
Spaces are allowed in the input, but they should be stripped before checking.
All other non-digit characters are disallowed.
Examples
Valid credit card number
The number to be checked is 4539 3195 0343 6467.
The first step of the Luhn algorithm is to start at the end of the number and double every second digit, beginning with the second digit from the right and moving left.
4539 3195 0343 6467
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ (double these)
If the result of doubling a digit is greater than 9, we subtract 9 from that result.
We end up with:
8569 6195 0383 3437
Finally, we sum all digits.
If the sum is evenly divisible by 10, the original number is valid.
8 + 5 + 6 + 9 + 6 + 1 + 9 + 5 + 0 + 3 + 8 + 3 + 3 + 4 + 3 + 7 = 80
80 is evenly divisible by 10, so number 4539 3195 0343 6467 is valid!
Invalid Canadian SIN
The number to be checked is 066 123 478.
We start at the end of the number and double every second digit, beginning with the second digit from the right and moving left.
066 123 478
↑ ↑ ↑ ↑ (double these)
If the result of doubling a digit is greater than 9, we subtract 9 from that result.
We end up with:
036 226 458
We sum the digits:
0 + 3 + 6 + 2 + 2 + 6 + 4 + 5 + 8 = 36
36 is not evenly divisible by 10, so number 066 123 478 is not valid!
Dig Deeper
reversed for loop
reversed() with a for loop
class Luhn:
def __init__(self, card_num):
self.isValid = Luhn.luhny_bin(card_num)
def valid(self):
return self.isValid
@staticmethod
def luhny_tune(num):
return dbl - 9 if (dbl := 2 * num) > 9 else dbl
@staticmethod
def luhny_bin(num):
total = 0
pos = 0
for ltr in reversed(num):
if ltr.isdigit():
if not pos % 2:
total+= int(ltr)
else:
total += Luhn.luhny_tune(int(ltr))
pos += 1
elif ltr != " ":
return False
return pos > 1 and not total % 10
The Luhn object is initialized with the card_num value, which is the number to be validated with the Luhn algorithm.
The result of the validation is returned from Luhn’s valid() method.
In this approach, a member variable is set to the result of running the Luhn algorithm.
That variable is returned from the valid() method.
The methods that do the work have the @staticmethod decorator.
This indicates that the method belongs to the class and is not recreated for every object instance.
In the code example the luhny_bin() method initializes the total and pos variables to 0.
It then calls reversed() on the input and iterates the characters from right to left with a for loop.
The isdigit() method is used to see if the character is a digit.
If so, the modulo operator is used to check if the character’s position is evenly divided by 2.
By using the falsiness of 0, the not operator can be used instead of comparing equality to 0.
It can be thought of as the expression not having a remainder.
If the position is evenly divided by 2, then it is even, and the character is converted to an int() and added to the total variable.
If the position is odd, then the number is converted to an int and is passed to the static method which always doubles it,
and will subtract 9 from the doubled value if the doubled value is greater than 9.
It does this using a ternary operator.
Inside the ternary operator an assignment expression assigns the doubled value to the dbl variable with (dbl := 2 * num).
The ternary operator returns dbl - 9 if dbl is greater than 9, otherwise it returns dbl.
The resulting value is added to the total variable.
Whether the digit is even or odd, the position is incremented by 1.
If the character is not a digit, the method returns False if the character is not a space.
If the character is a space, the loop will go to the next iteration without incrementing the position variable.
After the iteration of the characters is done, the method returns if the position is greater than 1 and if the total is evenly divisible by 10.
replace, reverse, enumerate
replace(), reverse, enumerate()
class Luhn:
def __init__(self, card_num):
self.isValid = Luhn.luhny_bin(card_num)
def valid(self):
return self.isValid
@staticmethod
def luhny_tune(num):
return dbl - 9 if (dbl := 2 * num) > 9 else dbl
@staticmethod
def luhny_bin(num):
num = num.replace(' ', '')
if not num.isdigit():
return False
total = 0
for pos, ltr in enumerate(num[::-1]):
if not pos % 2:
total+= int(ltr)
else:
total += Luhn.luhny_tune(int(ltr))
pos += 1
return pos > 1 and not total % 10
The Luhn object is initialized with the card_num value, which is the number to be validated with the Luhn algorithm.
The result of the validation is returned from Luhn’s valid() method.
In this approach, a member variable is set to the result of running the Luhn algorithm.
That variable is returned from the valid() method.
The methods that do the work have the @staticmethod decorator.
This indicates that the method belongs to the class and is not recreated for every object instance.
In the code example the luhny_bin() method uses the replace() method to replace all occurrences of a space in the input with an empty string.
The isdigit() method is then used to see if all of the remaining characters are digits.
If not, the method returns False.
Slicing syntax ([::-1) is used to reverse the characters in the input, which is then passed into the enumerate() method.
The for loop uses enumerate() to iterate the reversed characters in the input, returning the character and its position in the string.
The modulo operator is used to check if the character’s position is evenly divided by 2.
By using the falsiness of 0, the not operator can be used instead of comparing equality to 0.
It can be thought of as the expression not having a remainder.
If the position is evenly divided by 2, then it is even, and the character is converted to an int() and added to the total variable.
If the position is odd, then the number is converted to an int and is passed to the static method which always doubles it,
and will subtract 9 from the doubled value if the doubled value is greater than 9.
It does this using a ternary operator.
Inside the ternary operator an assignment expression assigns the doubled value to the dbl variable with (dbl := 2 * num).
The ternary operator returns dbl - 9 if dbl is greater than 9, otherwise it returns dbl.
The resulting value is added to the total variable.
After the iteration of the characters is done, the method returns if the position is greater than 1 and if the total is evenly divisible by 10.
recursion
Recursion
class Luhn:
def __init__(self, card_num):
self.isValid = Luhn.luhny_bin(0, 0, list(card_num[::-1]))
def valid(self):
return self.isValid
@staticmethod
def luhny_tune(num):
return dbl - 9 if (dbl := 2 * num) > 9 else dbl
@staticmethod
def luhny_bin(pos, sum, chars):
if not chars:
return pos > 1 and sum % 10 == 0
else:
head, *tail = chars
if head.isdigit():
if not pos % 2:
return Luhn.luhny_bin(pos + 1, sum + int(head), tail)
else:
return Luhn.luhny_bin(pos + 1, sum + Luhn.luhny_tune(int(head)), tail)
if head == " ":
return Luhn.luhny_bin(pos, sum, tail)
return False
The Luhn object is initialized with the card_num value, which is the number to be validated with the Luhn algorithm.
The result of the validation is returned from Luhn’s valid() method.
In this approach, a member variable is set to the result of running the Luhn algorithm.
That variable is returned from the valid() method.
The methods that do the work have the @staticmethod decorator.
This indicates that the method belongs to the class and is not recreated for every object instance.
In the code example the __init__ method uses slicing syntax ([::-1]) to reverse the characters in the input,
which is then passed into the list constructor.
The luhny_bin() method takes that list, along with two 0 values that represent the initialized values for the position and the sum.
The luhny_bin() can call itself, which is a behavior called recursion.
Since luhny_bin() can call itself, the first thing it does is to check that it is done calling itself.
This check is called the terminating condition.
It's critical to have a terminating condition, since every call of a recursive function to itself places another
[frame on the stack](https://realpython.com/lessons/stack-frames-and-stack-traces/#:~:text=A%20stack%20frame%20represents%20a,is%20removed%20from%20the%20stack.).
If there is no terminating condition, then the recursive function will keep calling itself until the stack runs out of space
and a stack overflow error will occur.
The luhny_bin() method should terminate when there are no more characters to process.
By using the falsiness of an empty list, the not operator can be used instead of comparing the len() of the list to 0.
When all of the characters have been iterated, the method returns if the position is greater than 1 and if the sum is evenly divisible by 10.
While there are still characters in the list to iterate, the list is destructured into head, *tail.
The isdigit() method is used to see if the head character is a digit.
If so, the modulo operator is used to check if the character’s position is evenly divided by 2.
By using the falsiness of 0, the not operator can be used instead of comparing equality to 0.
It can be thought of as the expression not having a remainder.
If the position is evenly divided by 2, then it is even, and the character is converted to an int() and will be added to the sum variable.
If the position is odd, then the number is converted to an int and is passed to the static method which always doubles it,
and will subtract 9 from the doubled value if the doubled value is greater than 9.
It does this using a ternary operator.
Inside the ternary operator an assignment expression assigns the doubled value to the dbl variable with (dbl := 2 * num).
The ternary operator returns dbl - 9 if dbl is greater than 9, otherwise it returns dbl.
The resulting value will be added to the sum variable.
Whether the digit is even or odd, the position is added to 1 when it and the sum are passed into the next call of the recursive method.
Also passed in is the tail of the list, which is the list of all the remaining characters after the head character.
Note that the sum and position variables are not being directly changed.
(In other words, they are not being mutated.)
The new sum and position values are calculated as the new arguments to the recursive method.
If the head character is a space, the recursive method calls itself with the same position and sum values, and the tail.
If the head character is neither a digit or a space, the method returns False.
Source: Exercism python/luhn