## Credit Card Validation

### April 8, 2011

This is fairly straight forward. The variable `two?`

alternates between true and false, telling us when to double the current digit. At the end of the input, the check digit is calculated as 10 − *sum* mod 10, except that if the sum is divisible by 10 the check digit is 0; the check digit is added to the end of the input number by multiplying the input number by 10 then adding the check digit. The only trick we employ is to pre-compute the digit-sums of the doubled digits and store them in an array:

`(define (luhn n)`

(define (x2 n) (vector-ref #(0 2 4 6 8 1 3 5 7 9) n))

(let loop ((ds (reverse (digits n))) (s 0) (two? #t))

(cond ((null? ds)

(let* ((sum (modulo s 10))

(check (if (zero? sum) 0 (- 10 sum))))

(+ (* n 10) check)))

(two? (loop (cdr ds) (+ s (x2 (car ds))) #f))

(else (loop (cdr ds) (+ s (car ds)) #t)))))

Checking is even simpler:

`(define (luhn? n)`

(define (x2 n) (vector-ref #(0 2 4 6 8 1 3 5 7 9) n))

(let loop ((ds (reverse (digits n))) (s 0) (two? #f))

(cond ((null? ds) (zero? (modulo s 10)))

(two? (loop (cdr ds) (+ s (x2 (car ds))) #f))

(else (loop (cdr ds) (+ s (car ds)) #t)))))

The definition of the pre-computed array of doubled digits and the calculation of the sum are duplicated between the two functions. If you object to that, you can define the two functions like this:

`(define luhn #f)`

(define luhn? #f)

(letrec ((x2 (lambda (n)

(vector-ref #(0 2 4 6 8 1 3 5 7 9) n)))

(luhn-sum (lambda (n two?)

(let loop ((ds (reverse (digits n))) (s 0) (two? two?))

(cond ((null? ds) s)

(two? (loop (cdr ds) (+ s (x2 (car ds))) #f))

(else (loop (cdr ds) (+ s (car ds)) #t)))))))

(set! luhn (lambda (n)

(let* ((sum (modulo (luhn-sum n #t) 10))

(check (if (zero? sum) 0 (- 10 sum))))

(+ (* n 10) check))))

(set! luhn? (lambda (n)

(zero? (modulo (luhn-sum n #f) 10)))))

In this case the duplicated code is small enough that it probably doesn’t matter, but this technique of hiding the duplicated code inside a `letrec`

can be useful if the duplicated code is larger.

A small test assures us that everything is working properly:

`(define (luhn-test)`

(assert (luhn 4992739871) 49927398716)

(assert (luhn? 49927398716) #t)

(assert (luhn? 49927398715) #f)

(do ((i 0 (+ i 1))) ((= i 10000))

(assert (luhn? (luhn (randint #e1e8))) #t))

(do ((i 0 (+ i 1))) ((= i 100))

(assert (luhn? (luhn (randint (expt 10 i)))) #t)))

We used digits, randint and assert from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/io514WKh.

My Haskell solution (see http://bonsaicode.wordpress.com/2011/04/08/programming-praxis-credit-card-validation/ for a version with comments):

[…] today’s Programming Praxis exercise our goal is to write to functions related to the Luhn credit card […]

I came up with two versions of my intermediate Luhn sum function: one that

creates a list and modifies it in-place, and another that uses iterators

instead. My solution is available on github.

Just numbers; just one recursive branch / two vectors.

First I missed that (- 10 (modulo 30 10)) is 10, not 0.

Then Ikarus thought that (modulo -30 10) => 10. Sigh.

Wanted to see if I still remember Linux assembly so I wrote my answer in it: github. It might be possible to make the answer more readable and shorter, but that would take me an additional hour…

Factor Language solution.

( scratchpad ) 2771 luhn? .

f

( scratchpad ) 2771 make-luhn dup . luhn? .

27714

t

( scratchpad ) 49927398716 luhn? .

t

( scratchpad ) 49927398716 make-luhn dup . luhn? .

499273987168

t

[…] or Canadian Social Insurance Numbers are validated you can take a look at this Programming Praxis article . It’s all about a simple, tiny, patented (now public domain) algorithm invented by […]

My python 3.x solution:

nice solution

My try in REXX

My solution in Python 3.2

def addCCDigits(number):

number = int(str(number)[::-1])

numString = str(number)

check = False

mySum = 0

for ch in numString:

num = int(ch)

if (check):

num = num * 2

strNum = str(num)

for c in strNum:

num2 = int(c)

mySum += num2

else:

mySum += num

check = not check

return mySum

def validate(number):

mySum = addCCDigits(number)

if (mySum % 10 == 0):

return True

else:

return False

def addCheckDigit(number):

mySum = addCCDigits(number * 10 + 1) – 1

digit1 = int(mySum / 10)

goal = (digit1 + 1) * 10;

diff = goal – mySum;

mySum = int(mySum / 10)

strNumber = str(number) + str(diff)

number = int(strNumber)

return number

[\code]