Pages

11/22/2011

Luhn Algorithm Implementation in Ruby

Luhn Algorithm (a.k.a. Mod10, Modulus10): 
    used for creating checksum digit for credit cards, IMEI number, SSN in US and Canada.
(for more see http://en.wikipedia.org/wiki/Luhn_algorithm and http://en.wikipedia.org/wiki/Bank_card_number)


Algorithm:
using "7992739871" as an example here.

  1. break string into digits:
    "7992739871" ==> [7,9,9,2,7,3,9,8,7,1]
  2. double every other digit, starting at 2nd digit:
     [7,9,9,2,7,3,9,8,7,1]  ==> [7,18,9,4,7,6,9,16,7,2]
  3. sum 2-digit number into single-digit number: ex. 18=>1+8=9
    trick is: using either 1+val%10 , or just simply val - 9 if value is over 9
    [7,18,9,4,7,6,9,16,7,2] ==> [7,9,9,4,7,6,9,7,4,2]
  4. sum all numbers:
     [7,9,9,4,7,6,9,7,4,2] ==> 67
  5. modulo with 10:
    67%10 ==> 7
  6. use the reminder to subtract from 10:
    10-7 ==> 3
  7. it is the check digit:
    so the final number will be "79927398713"
Implementation in Ruby:

1st implementation: 
   create 'b' as 1,2,1,2... alternative array and use .zip method to make it parallel array, thne using map to do multiplication (dot-product-like). 'k' variable will be digit-summed, and finally the whole array is summed by .inject(&:+)

input = '7992739871'
b = (1..input.length).map{|i| i%2==0?2:1}
output = 10 - input.split('').map(&:to_i).zip(b).map{|i,j| k=i*j; k<10?k:1+k%10}.inject(&:+)%10

2nd implementation:
   This one uses a benefit of .each_with_index method, so we can omit array 'b'. But the loop does not return changed values, we need another variable (sum) to hold the value.

input = '7992739871'
sum = 0
input.split('').map(&:to_i).each_with_index{|v,i| k=(i%2==0)?v:(v*2<10)?v*2:1+(v*2)%10; sum= sum+k}
output = 10 - sum%10

3rd implementation: 
    based on idea of using Hash to reduce computation on sum of 2-digit, we can use this hash ('b' variable) to directly map the doubled digit into sum of 2-digit value. In 'b' variable (summation of 2-digit of doubled value), we'll get
    b => {5=>1, 0=>0, 6=>3, 1=>2, 7=>5, 2=>4, 8=>7, 3=>6, 9=>9, 4=>8}  
   *** 5=>1 means 5*2 => 10 => 1+0 => 1

input = '7992739871'
b=Hash[(0..9).collect{|i| [i,i*2<10?i*2:1+(i*2%10)]}]
sum = 0
input.split(//).collect(&:to_i).each_with_index{|v,i| sum=sum+(i%2==0?v:b[v])}
output = 10 - sum%10
4th implementation:     If combine all the implementation, would it be easier?
(also change to use val-9 in computation for sum of digits)

input = '7992739871'
b=Hash[(0..9).collect{|i| [i,i*2<10?i*2:i*2-9]}]
output = 10 - input.split(//).collect(&:to_i).zip((1..input.length).to_a).map{|v,i| i%2==0?b[v]:v}.inject(&:+)%10

Or into one-liner as:

input = '7992739871'
output = 10 - input.split(//).collect(&:to_i).zip((1..input.length).to_a).map{|v,i| i%2==0?(v*2<10?v*2:v*2-9):v}.inject(&:+)%10

Additionally useful snippets:
   Found these 2 snippets for checking credit card company.

From: https://gist.github.com/1182499
def valid_association?(number)
  number = number.to_s.gsub(/\D/, "") 
  return :dinners  if number.length == 14 && number =~ /^3(0[0-5]|[68])/   # 300xxx-305xxx, 36xxxx, 38xxxx
  return :amex     if number.length == 15 && number =~ /^3[47]/            # 34xxxx, 37xxxx
  return :visa     if [13,16].include?(number.length) && number =~ /^4/    # 4xxxxx
  return :master   if number.length == 16 && number =~ /^5[1-5]/           # 51xxxx-55xxxx
  return :discover if number.length == 16 && number =~ /^6011/             # 6011xx
  return nil
end

From: http://www.missiondata.com/blog/web-development/25/credit-card-type-and-luhn-check-in-ruby/
def ccTypeCheck(ccNumber)
  ccNumber = ccNumber.gsub(/\D/, '')
  case ccNumber
    when /^3[47]\d{13}$/ then return "AMEX"
    when /^4\d{12}(\d{3})?$/ then return "VISA"
    when /^5\d{15}|36\d{14}$/ then return "MC"
    when /^6011\d{12}|650\d{13}$/ then return "DISC"
    when /^3(0[0-5]|8[0-1])\d{11}$/ then return "DINERS"
    when /^(39\d{12})|(389\d{11})$/ then return "CB"
    when /^3\d{15}|1800\d{11}|2131\d{11}$/ then return "JCB"
    else return "NA"
  end
end

No comments:

Post a Comment