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.

About these ads

Pages: 1 2

14 Responses to “Credit Card Validation”

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

    import Data.Char
    import Data.List.HT
    
    luhnSum :: Integral a => a -> a
    luhnSum n = digitSum a + digitSum (show . (* 2) . digitToInt =<< b)
        where [a,b] = sliceHorizontal 2 . reverse $ show n
              digitSum = sum . map (fromIntegral . digitToInt)
    
    isValid :: Integral a => a -> Bool
    isValid n = mod (luhnSum n) 10 == 0
    
    makeValid :: Integral a => a -> a
    makeValid n = 10*n + mod (10 - mod (luhnSum $ 10*n) 10) 10
    
  2. [...] today’s Programming Praxis exercise our goal is to write to functions related to the Luhn credit card [...]

  3. Graham said

    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.

  4. Jussi Piitulainen said

    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.

    (define (luhn-digit digits)
      (define (modulo n m) (- n (* m (floor (/ n m))))) ;...                                                                     
      (let loop ((digits digits) (neg-sum 0)
                 (vig '#(0 2 4 6 8 1 3 5 7 9))
                 (vug '#(0 1 2 3 4 5 6 7 8 9)))
        (if (zero? digits)
            (modulo neg-sum 10)
            (loop (quotient digits 10)
                  (- neg-sum (vector-ref vig (modulo digits 10)))
                  vug vig))))
    
    (define (luhn? digits) (= digits (luhn (quotient digits 10))))
    
    (define (luhn digits) (+ (* digits 10) (luhn-digit digits)))
    
    (write (luhn? 49927398716))
    (write (luhn? 3020))
    (write (luhn? 3129))
    (newline)
    
  5. arturasl said

    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…

  6. Mike said
    dd = ((0,0), (1,2), (2,4), (3,6), (4,8),
          (5,1), (6,3), (7,5), (8,7), (9,9))
    
    def luhn(ds):
        '''
        >>> n = "49927398716"
        >>> luhn(n[:-1])
        6
        '''
    
        return -sum(dd[int(d)][~n&1] for n,d in enumerate(ds[::-1])) % 10
    
    def is_valid(ds):
        '''
        n = "49927398716"
        >>> is_valid(n)
        True
        '''
    
        return luhn(ds[:-1]) == int(ds[-1])
    
    def add_check_digit(ds):
        '''
        n = "4992739871"
        >>> add_check_digit(n)
        '49927398716'
        '''
    
        return ds + str(luhn(ds))
    
  7. David said

    Factor Language solution.

    USING: kernel math math.parser math.ranges sequences ;
    IN: luhn
    
    : reversed-digits ( n -- list )
        { } swap
        [ dup 0 > ]
            [ 10 /mod  swapd suffix  swap ]
        while drop ;
    
    : luhn-sum  ( n -- n )
        reversed-digits dup length iota [
            2dup swap nth
            swap odd? [ 2 *  10 /mod + ] when
        ] map sum
        nip ;
    
    : luhn? ( n -- ? )
        luhn-sum 10 mod 0 = ;
    
    : make-luhn ( n -- n )
        10 * dup luhn-sum 10 mod 10 swap - 10 mod + ;
    

    ( scratchpad ) 2771 luhn? .
    f
    ( scratchpad ) 2771 make-luhn dup . luhn? .
    27714
    t
    ( scratchpad ) 49927398716 luhn? .
    t
    ( scratchpad ) 49927398716 make-luhn dup . luhn? .
    499273987168
    t

  8. [...] 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 [...]

  9. My python 3.x solution:

    def luhn_check(num):
        ''' Number - List of reversed digits '''
        digits = [int(x) for x in reversed(str(num))]
        check_sum = sum(digits[::2]) + sum((dig//10 + dig%10) for dig in [2*el for el in digits[1::2]])
        return check_sum%10 == 0
     
    if __name__ == "__main__":
        print(luhn_check(543298376
    
  10. rohit said

    nice solution

  11. Rainer said

    My try in REXX

    
    numeric digits 30
    debug = 0
    
    number = '49927398716'
    
    say number 'is' check_luhn(number)
    
    number = '4992739871'
    say number 'plus check_digit =' add_check_digit(number)
    
    exit
    
    check_luhn: procedure
        parse arg test
        test = reverse(test)
        summe = 0
        ind = 0
        do i = 1 to length(test)
            ind = ind + 1
            ziffer = substr(test,i,1)
            say 'Ziffer' ziffer
            if even(ind) then do
                ziffer = ziffer * 2
                if length(ziffer) > 1 then summe = summe + left(ziffer,1)
            end
            summe = summe + right(ziffer,1)
            say 'Summe' summe
        end
        if (summe//10) > 0 then return 'wrong'
                           else return 'correct'
    
    add_check_digit: procedure
        parse arg urtest
        test = reverse(urtest)	
        summe = 0
        ind = 0
        do i = 1 to length(test)
            ind = ind + 1
            ziffer = substr(test,i,1)
            if odd(ind) then do
                ziffer = ziffer * 2
                if length(ziffer) > 1 then summe = summe + left(ziffer,1)
            end
            summe = summe + right(ziffer,1)
            say 'Summe' summe
        end
        if (summe//10) > 0 then return urtest||(summe%10*10)+10-summe
                           else return urtest||0
    
    even: procedure
        parse arg number
        return \ odd(number)
    
    odd: procedure
        parse arg number
        return (number//2)
    
    
  12. Khanh Nguyen said
    open System
    
    let rec sum_digit inp =
        if inp < 10 then inp else sum_digit (inp / 10) + (inp % 10)
    
    let f (inp: string) =    
        inp.ToCharArray() 
        |> List.ofArray 
        |> List.map (fun x -> (int x) - (int '0')) 
        |> List.rev 
        |> List.zip [1.. String.length inp]
        |> List.map (fun (i, v) -> if i % 2 = 1 then v*2 else v)
        |> List.map sum_digit
        |> List.sum 
    
    let add_check_digit (inp : string) =
        inp + string(10 - (f inp) % 10)
    let isValid (inp : string) = 
        inp = add_check_digit (inp.Remove(String.length inp - 1))
    
    add_check_digit "4992739871"
    isValid "49927398715"
    isValid "49927398716"
    
    
  13. Ben Atwell said

    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]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: