Skip to content

Instantly share code, notes, and snippets.

@david-meza
Created January 20, 2016 01:29
Show Gist options
  • Save david-meza/89efe35cce2ffd16e535 to your computer and use it in GitHub Desktop.
Save david-meza/89efe35cce2ffd16e535 to your computer and use it in GitHub Desktop.

Luhn

Write a program that can take a number and determine whether or not it is valid per the Luhn formula.

The Luhn formula is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers.

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

Counting from rightmost digit (which is the check digit) and moving left, double the value of every second digit. For any digits that thus become 10 or more, subtract 9 from the result. 1111 becomes 2121. 8763 becomes 7733 (from 2×6=12 → 12-9=3 and 2×8=16 → 16-9=7). Add all these digits together. 1111 becomes 2121 sums as 2+1+2+1 to give a check digit of 6. 8763 becomes 7733, and 7+7+3+3 is 20. If the total ends in 0 (put another way, if the total modulus 10 is congruent to 0), then the number is valid according to the Luhn formula; else it is not valid. So, 1111 is not valid (as shown above, it comes out to 6), while 8763 is valid (as shown above, it comes out to 20).

Write a program that, given a number

Can check if it is valid per the Luhn formula. This should treat, for example, "2323 2005 7766 3554" as valid. Can return the checksum, or the remainder from using the Luhn method. Can add a check digit to make the number valid per the Luhn formula and return the original number plus that digit. This should give "2323 2005 7766 3554" in response to "2323 2005 7766 355".

About Checksums

A checksum has to do with error-detection. There are a number of different ways in which a checksum could be calculated.

When transmitting data, you might also send along a checksum that says how many bytes of data are being sent. That means that when the data arrives on the other side, you can count the bytes and compare it to the checksum. If these are different, then the data has been garbled in transmission.

In the Luhn problem the final digit acts as a sanity check for all the prior digits. Running those prior digits through a particular algorithm should give you that final digit.

It doesn't actually tell you if it's a real credit card number, only that it's a plausible one. It's the same thing with the bytes that get transmitted -- you could have the right number of bytes and still have a garbled message. So checksums are a simple sanity-check, not a real in-depth verification of the authenticity of some data. It's often a cheap first pass, and can be used to quickly discard obviously invalid things.

You will need the Minitest gem. To install it, open a terminal window and run:

gem install minitest

##Source

The Luhn Algorithm on Wikipedia view source

require 'pry'
class Luhn
def initialize(input)
@digits = input.to_s.chars.map(&:to_i)
end
# ---------------- Class Methods ------------------
def self.create_hacky(input)
return input if luhn_number?(input)
9.times do |test_digit|
# test_number = (input.to_s + test_digit.to_s).to_i
test_number = input * 10 + test_digit
return test_number if luhn_number?(test_number)
end
end
def self.create(input)
return input if luhn_number?(input)
new_instance = new(input * 10)
current_sum = new_instance.checksum
input * 10 + (current_sum % 10 == 0 ? current_sum % 10 : 10 - current_sum % 10)
end
# ---------------- Instance Methods ------------------
def valid?
checksum % 10 == 0
end
def checksum
addends.reduce(&:+)
end
def addends
@digits.reverse.each_with_index.map do |digit, idx|
digit *= 2 if idx.odd?
digit > 9 ? digit -= 9 : digit
end.reverse
end
private
def self.luhn_number?(num)
new(num).valid?
end
end
require 'minitest/autorun'
require_relative 'luhn'
class LuhnTest < MiniTest::Unit::TestCase
def test_addends
luhn = Luhn.new(12_121)
assert_equal [1, 4, 1, 4, 1], luhn.addends
end
def test_too_large_addend
luhn = Luhn.new(8631)
assert_equal [7, 6, 6, 1], luhn.addends
end
def test_checksum
luhn = Luhn.new(4913)
assert_equal 22, luhn.checksum
end
def test_checksum_again
luhn = Luhn.new(201_773)
assert_equal 21, luhn.checksum
end
def test_invalid_number
luhn = Luhn.new(738)
assert !luhn.valid?
end
def test_valid_number
luhn = Luhn.new(8_739_567)
assert luhn.valid?
end
def test_validity_of_zero
luhn = Luhn.new(0)
assert luhn.valid?
end
def test_create_valid_number
number = Luhn.create(123)
assert_equal 1230, number
end
def test_create_other_valid_number
number = Luhn.create(873_956)
assert_equal 8_739_567, number
end
def test_create_yet_another_valid_number
number = Luhn.create(837_263_756)
assert_equal 8_372_637_564, number
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment