SPOJ.com - Problem PROG0434

PROG0434 - Credit card

no tags

Most credit cards are assigned a unique number that can be validated by an algorithm developed by Hans Peter Luhn from IBM. The Luhn algorithm can detect almost any single-letter, almost all transpositions of adjacent digits except 09 and 90, and many other errors. In 1960 a patent on the Luhn algorithm was granted to IBM (U.S. Patent 2950048), but nowadays it can be freely used by everyone.

The Luhn algorithm verifies a credit card number against its included check digit, which is appended to a partial credit card number to generate the full credit card number. This credit card number must pass the following test:

From the rightmost digit, which is the check digit, moving left, double the value of every second digit. If the product of this doubling operation is greater than 9 (e.g. $7 \times 2 = 14$), then sum the digits of the product (e.g. $10 = 1 + 0 = 1$; $14 = 1 + 4 = 5$).
Take the sum of all resulting digits, including the check digit.
If the total sum is divisible by 10, the credit card number is valid. Otherwise the credit card number is invalid.

According to the Luhn algorithm, the credit card number 49927398716 is valid. The sum is calculated as follows: $$ 6 + (2) + 7 + (1 + 6) + 9 + (6) + 7 + (4) + 9 + (1 + 8) + 4 = 70 $$ and this result is divisible by 10. In this example, we have enclosed the digits of the numbers that have been doubled in between brackets.

Assignment

Your task is to write the following three functions, that each take a credit card number as a string argument.

A function luhn that returns the sum of the digits of the credit card number, as computed by the Luhn algorithm.
A function valid that returns a Boolean value indicating whether or not the credit card number is valid according to the Luhn algorithm.
A function addcheck that completes the (partial) credit card number with an additional check digit, that results in a valid full credit card number (returned by the function) according to the Luhn algorithm.

Make sure to make optimal reuse of your source code when implementing these three functions.

Example

>>> luhn('49927398716')
70
>>> luhn('49927938716')
67
>>> luhn('79927398716')
73

>>> valid('49927398716')
True
>>> valid('49927938716')
False
>>> valid('79927398716')
False

>>> addcheck('4992739871')
'49927398716'
>>> addcheck('4992793871')
'49927938719'
>>> addcheck('7992739871')
'79927398713'

De meeste bankkaarten hebben een uniek nummer waarvan de geldigheid kan gecontroleerd worden aan de hand van een algoritme dat ontwikkeld werd door Hans Peter Luhn van IBM. Dit algoritme kan bijna alle fouten opsporen die het resultaat zijn van één verkeerd ingegeven cijfer, de omwisseling van twee opeenvolgende cijfers, en tal van andere fouten. IBM nam in 1954 een patent op het algoritme (U.S. Patent 2950048), maar nu mag het door iedereen vrij gebruikt worden.

Het algoritme van Luhn werkt van rechts naar links, waarbij het cijfer helemaal achteraan een controlecijfer is. Het controlecijfer moet de volgende test doorstaan.

Startend vanaf het cijfer dat links van het controlecijfer staat, schuiven we telkens twee cijfers op naar links. We verdubbelen telkens de waarde van elk van deze cijfers. Als deze verdubbeling resulteert in een getal van twee cijfers, dan tellen we de cijfers van dit getal bij elkaar op. Op die manier wordt het cijfer 7 bijvoorbeeld verdubbeld tot 14, waarna de som van de cijfers gelijk is aan 5.
Daarna nemen we de som van de cijfers van het kaartnummer, inclusief het controlecijfer.
Als de totale som deelbaar is door tien, dan is kaartnummer geldig. Anders is het kaartnummer ongeldig.

Volgens dit algoritme is het kaartnummer 49927398716 dus geldig. De som wordt immers als volgt berekend $$ 6 + (2) + 7 + (1 + 6) + 9 + (6) + 7 + (4) + 9 + (1 + 8) + 4 = 70 $$ en dat resultaat is deelbaar door 10. Hierbij wordt de som van de cijfers na de verdubbeling aangegeven tussen ronde haakjes.

Opgave

Je opdracht bestaat erin om de volgende drie functies te schrijven, waarbij telkens een kaartnummer als string aan de functie moet doorgegeven worden.

Een functie luhn die de som van de cijfers van het kaartnummer teruggeeft, zoals die wordt berekend volgens het algoritme van Luhn.
Een functie geldig die aangeeft of het gegeven kaartnummer al of niet geldig is volgens het algoritme van Luhn.
Een functie controle die het gegeven kaartnummer aanvult met een controlecijfer, zodat het een geldig kaartnummer wordt volgens het algoritme van Luhn.

Zorg er bij de implementatie van deze functies voor dat je zo optimaal mogelijk hergebruik maakt van je broncode.

Voorbeeld

>>> luhn('49927398716')
70
>>> luhn('49927938716')
67
>>> luhn('79927398716')
73
"""

>>> geldig('49927398716')
True
>>> geldig('49927938716')
False
>>> geldig('79927398716')
False

>>> controle('4992739871')
'49927398716'
>>> controle('4992793871')
'49927938719'
>>> controle('7992739871')
'79927398713'

Submit solution!

Added by:	Peter Dawyndt
Date:	2013-09-11
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None