Before a credit card is submitted to a financial institution, it generally makes sense to run some simple reality checks on the number. The numbers are a good length and it's common to make minor transcription errors when the card is not scanned directly.
The first check people often do is to validate that the card matches a known pattern from one of the accepted card providers. Some of these patterns are:
+============+=============+===============+
| Card Type | Begins With | Number Length |
+============+=============+===============+
| AMEX | 34 or 37 | 15 |
+------------+-------------+---------------+
| Discover | 6011 | 16 |
+------------+-------------+---------------+
| MasterCard | 51-55 | 16 |
+------------+-------------+---------------+
| Visa | 4 | 13 or 16 |
+------------+-------------+---------------+
All of these card types also generate numbers such that they can be validated by the Luhn algorithm, so that's the second check systems usually try. The steps are:
1. Starting with the next to last digit and continuing with every other
digit going back to the beginning of the card, double the digit
2. Sum all doubled and untouched digits in the number
3. If that total is a multiple of 10, the number is valid
For example, given the card number 4408 0412 3456 7893:
Step 1: 8 4 0 8 0 4 2 2 6 4 10 6 14 8 18 3
Step 2: 8+4+0+8+0+4+2+2+6+4+1+0+6+1+4+8+1+8+3 = 70
Step 3: 70 % 10 == 0
Thus that card is valid.
Let's try one more, 4417 1234 5678 9112:
Step 1: 8 4 2 7 2 2 6 4 10 6 14 8 18 1 2 2
Step 2: 8+4+2+7+2+2+6+4+1+0+6+1+4+8+1+8+1+2+2 = 69
Step 3: 69 % 10 != 0
That card is not valid.
This week's Ruby Quiz is to write a program that accepts a credit card number as a command-line argument. The program should print the card's type (or Unknown) as well a Valid/Invalid indication of whether or not the card passes the Luhn algorithm.
Quiz Summary
This quiz is super easy, of course. The reason I ran it though is that I wanted to see how people approached the Luhn algorithm implementation. It's an easy enough process, but I found myself using an odd combination of Regexp and eval() when I was fiddling with it:
"#{$1 + '+' if $1}#{($2.to_i * 2).to_s.split('').join('+')}+"
end ) % 10 == 0 ? "Valid" : "Invalid"
I knew that was ugly and wanted to see how you guys would pretty it up.
You have shown me the light and it tells me... Daniel Martin is crazy. I'll leave it to him to explain his own solution, as punishment for the time it took me to puzzle it out. I had to print that Array inside of the inject() call during each iteration to see how it built up the answer.
I do want to show you a slew of interesting tidbits though. First, let's get the formality of a full solution out of the way. Here's some code from Drew Olson:
def initialize num
@number = num
end
# check specified conditions to determine the type of card
def type
length = @number.size
if length == 15 && @number =~ /^(34|37)/
"AMEX"
elsif length == 16 && @number =~ /^6011/
"Discover"
elsif length == 16 && @number =~ /^5[1-5]/
"MasterCard"
elsif (length == 13 || length == 16) && @number =~ /^4/
"Visa"
else
"Unknown"
end
end
# determine if card is valid based on Luhn algorithm
def valid?
digits = ''
# double every other number starting with the next to last
# and working backwards
@number.split('').reverse.each_with_index do |d,i|
digits += d if i%2 == 0
digits += (d.to_i*2).to_s if i%2 == 1
end
# sum the resulting digits, mod with ten, check against 0
digits.split('').inject(0){|sum,d| sum+d.to_i}%10 == 0
end
end
if __FILE__ == $0
card = CreditCard.new(ARGV.join.chomp)
puts "Card Type: #{card.type}"
if card.valid?
puts "Valid Card"
else
puts "Invalid Card"
end
end
As Drew shows, checking the type() is just a matter of verifying length and prefix against a known list. Nothing tricky here, as long as you don't get into the more complicated cards discussed in the quiz thread.
The valid?() method is the Luhn algorithm I wanted to see. Drew bypasses the need for my crazy Regexp using a trick I'm always harping on: reverse the data. It won't make any difference mathematically if the number is backwards and then you just need to double each second digit. Drew figures out when that is by combining each_with_index() with a little modulo test. From there, it's a simple sum of the digits and the final modulo test to determine validity.
The application code just runs those two methods and prints results.
Looking at Drew's Luhn algorithm again, see how he declares the digits variable and then fills it up? That's the classic inject() pattern, but inject() wasn't an option there since the code needed each_with_index() over just plain each(). This situation seems to call for an inject_with_index(), and look what doug meyer wrote:
def inject_with_index(injected)
each_with_index{|obj, index| injected = yield(injected, obj, index) }
injected
end
end
I guess he felt the same way, though I would have added this method to Enumerable instead of Array. Others used a hand rolled map_with_index() in similar ways.
Now, if you want to get away from all this index checking, you need to take a more functional approach and some solutions definitely did that. Here's the same algorithm we've been examining from Ryan Leavengood's code:
# ...
def self.luhn_check(cc)
# I like functional-style code (though this may be a bit over the top)
(cc.split('').reverse.enum_for(:each_slice, 2).inject('') do |s, (a, b)|
s << a + (b.to_i * 2).to_s
end.split('').inject(0) {|sum, n| sum + n.to_i}) % 10 == 0
end
This process is interesting, I think, so let's walk through it. The card number is split() into digits and reverse()d as we have been seeing.
Then an Enumerator for each_slice() is combined with inject() to build up the new digits. This passes the digits into inject() two at a time, so the block can just double the second one. This will give you an extra nil at the end of an odd card number, but to_i() turn that into a harmless zero.
The digits are again divided and this time summed to get a grand total. Check that for divisibility by ten and we have our answer.
Now Ryan chose to build up the digits and then sum, but you could do both in the same iterator. The first number is only ever one digit, so it's only the second number that needs special handling:
puts ARGV.join.split("").reverse.enum_slice(2).inject(0) { |sum, (l, r)|
sum + l.to_i +
(r.to_i * 2).to_s.split("").inject(0) { |s, d| s + d.to_i }
} % 10 == 0 ? "Valid" : "Invalid"
Ryan's version is probably still a little cleaner though.
Going one step further is to think about that second digit some more. It's the source of the need for tricky code, because it might be a two digit number. However, it doesn't have to be. Nine doubled is 18, but the sum of the digits of 18 is 9. In fact, if you subtract nine from any double over ten you will get the same sum. One way to put this to use is with a trivial lookup table, as Brad Ediger did:
def luhn_valid?
# a trick: double_and_sum[8] == sum_digits(8*2) == sum_digits(16) ==
# 1 + 6 == 7
double_and_sum = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
split(//).reverse.
mapn{|a,b| a.to_i + double_and_sum[b.to_i]}.sum % 10 == 0
end
Skipping over the sum() and mysterious mapn() methods for now, just take in the usage of double_and_sum. Those are the sums of all possible doubles of a single digit. Given that, Brad's solution has to do a lot less busy work than many of the others we saw. I thought this was a clever reduction of the problem.
I'm sure you can guess what that sum() method does, but let's do take a quick peek at mapn(), which is another bit of clever code:
module Enumerable
# Maps n-at-a-time (n = arity of given block) and collects the results
def mapn(&b)
r = []
each_slice(b.arity) {|*args| r << b.call(*args) }
r
end
def sum; inject(0){|s, i| s + i} end
end
You can see that mapn() is essentially, enum_slice(N).map(). The interesting part is that N is chosen from the arity of your provided block. If we ask for two at a time, we get two; ask for three and we get three:
=> [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]]
>> (1..10).mapn { |a, b, c| [a, b, c] }
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, nil, nil]]
That's a pretty smart iterator, I say.
This completes our tour of some of the wild and wacky ideas for applying the Luhn algorithm to card numbers. My thanks to all who shared them.
Ruby Quiz will now take a one week break. Work has been rough this week and I need some down time. I'll be back next week, rested, and with new quizzes...
