[SUMMARY] Checking Credit Cards (#122)

Discussion in 'Ruby' started by Ruby Quiz, May 3, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    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:

    puts eval( ARGV.join.gsub(/(\d)?(\d)(?=(?:\d\d)*\d$)/) do
    "#{$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:

    class CreditCard
    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:

    class Array
    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:

    require 'enumerator'

    # ...

    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:

    require "enumerator"
    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:

    # Returns true if Luhn check passes for this number
    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:

    require 'enumerator'
    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..10).mapn { |a, b| [a, b] }

    => [[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...
     
    Ruby Quiz, May 3, 2007
    #1
    1. Advertising

  2. I came to this quiz late, but came up with the following, before
    reading the solution, which uses String.tr to do the double and sum
    instead of an array.

    require 'enumerator'
    def luhn(string)
    string.scan(/./).reverse.enum_for:)each_with_index).inject(0) do
    |sum, (digit, index)|
    digit = digit.tr('0123456789', '0246813579') if index % 2 == 1
    sum += digit.to_i
    end # % 10 == 0
    end

    After seeing the neat use of each_slice instead of each_with_index

    def luhn(string)
    string.scan(/./).reverse.enum_for:)each_slice, 2).inject(0) do |sum, (d1, d2)|
    sum += d1.to_i + (d2||'0').tr('0123456789', '0246813579').to_i
    end % 10 == 0
    end

    No need to define any extra Enumerator methods.

    --
    Rick DeNatale

    My blog on Ruby
    http://talklikeaduck.denhaven2.com/
     
    Rick DeNatale, May 3, 2007
    #2
    1. Advertising

  3. Ruby Quiz

    anansi Guest

    > 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...



    Means that: no quiz tomorrow ?!?


    --
    greets

    (
    )
    (
    /\ .-"""-. /\
    //\\/ ,,, \//\\
    |/\| ,;;;;;, |/\|
    //\\\;-"""-;///\\
    // \/ . \/ \\
    (| ,-_| \ | / |_-, |)
    //`__\.-.-./__`\\
    // /.-(() ())-.\ \\
    (\ |) '---' (| /)
    ` (| |) `
    jgs \) (/


    one must still have chaos in oneself to be able to give birth to a
    dancing star
     
    anansi, May 3, 2007
    #3
  4. On 5/3/07, Rick DeNatale <> wrote:
    >
    > After seeing the neat use of each_slice instead of each_with_index
    >
    > def luhn(string)
    > string.scan(/./).reverse.enum_for:)each_slice, 2).inject(0) do |sum, (d1, d2)|
    > sum += d1.to_i + (d2||'0').tr('0123456789', '0246813579').to_i
    > end % 10 == 0
    > end
    >
    > No need to define any extra Enumerator methods.


    Nice, I like it. When I first thought about using
    enum_for:)each_slice, 2) I was surprised that it even worked.
    Enumerator is a powerful library.

    It seems like I learn something new every time I do one of these
    quizzes, either from making my own solution or reading someone else's.

    Ryan
     
    Ryan Leavengood, May 3, 2007
    #4
  5. On May 3, 2007, at 9:15 AM, anansi wrote:

    >> 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...

    >
    >
    > Means that: no quiz tomorrow ?!?


    Yes. I need a short break. We will have one the following Friday
    though.

    James Edward Gray II
     
    James Edward Gray II, May 3, 2007
    #5
  6. On 5/3/07, Ryan Leavengood <> wrote:

    > Enumerator is a powerful library.


    Yep. And personally, I like the fact that Ruby 1.9 is on the path to:

    1) Move enumerator to the core classes.
    2) Have enumerator methods return an enumerator if they are called
    without a block.

    The second one seems to be slightly controversial, but I love it.

    --
    Rick DeNatale

    My blog on Ruby
    http://talklikeaduck.denhaven2.com/
     
    Rick DeNatale, May 3, 2007
    #6
  7. Ruby Quiz

    anansi Guest

    James Edward Gray II wrote:
    > On May 3, 2007, at 9:15 AM, anansi wrote:
    >
    >>> 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...

    >>
    >>
    >> Means that: no quiz tomorrow ?!?

    >
    > Yes. I need a short break. We will have one the following Friday though.
    >
    > James Edward Gray II
    >




    Maybe someone is interested or has an idea for an unoffical Ruby Quiz
    for this week. I'm bored , so If someone has any idea, feel free to drop
    it ;)



    --
    greets

    (
    )
    (
    /\ .-"""-. /\
    //\\/ ,,, \//\\
    |/\| ,;;;;;, |/\|
    //\\\;-"""-;///\\
    // \/ . \/ \\
    (| ,-_| \ | / |_-, |)
    //`__\.-.-./__`\\
    // /.-(() ())-.\ \\
    (\ |) '---' (| /)
    ` (| |) `
    jgs \) (/


    one must still have chaos in oneself to be able to give birth to a
    dancing star
     
    anansi, May 3, 2007
    #7
  8. anansi wrote:
    > Maybe someone is interested or has an idea for an unoffical Ruby Quiz
    > for this week. I'm bored , so If someone has any idea, feel free to drop

    conway's game of life?
     
    Puria Nafisi Azizi, May 3, 2007
    #8
  9. Ruby Quiz

    anansi Guest

    Puria Nafisi Azizi wrote:
    > anansi wrote:
    >> Maybe someone is interested or has an idea for an unoffical Ruby Quiz
    >> for this week. I'm bored , so If someone has any idea, feel free to drop

    > conway's game of life?
    >


    Never heard about it but read now wiki and sounds interesting, so I
    would try it. Would you suggest a fixed count of columns and rows for
    that, if yes which?

    --
    greets

    (
    )
    (
    /\ .-"""-. /\
    //\\/ ,,, \//\\
    |/\| ,;;;;;, |/\|
    //\\\;-"""-;///\\
    // \/ . \/ \\
    (| ,-_| \ | / |_-, |)
    //`__\.-.-./__`\\
    // /.-(() ())-.\ \\
    (\ |) '---' (| /)
    ` (| |) `
    jgs \) (/


    one must still have chaos in oneself to be able to give birth to a
    dancing star
     
    anansi, May 3, 2007
    #9
  10. anansi wrote:
    > Never heard about it but read now wiki and sounds interesting, so I
    > would try it. Would you suggest a fixed count of columns and rows for

    pass it as an argument
     
    Puria Nafisi Azizi, May 3, 2007
    #10
  11. Ruby Quiz

    anansi Guest

    Puria Nafisi Azizi wrote:
    > anansi wrote:
    >> Never heard about it but read now wiki and sounds interesting, so I
    >> would try it. Would you suggest a fixed count of columns and rows for

    > pass it as an argument
    >


    k so far I would suggest:

    (I)
    passing row and col count as arguments
    (II)
    rules for cell stati:
    1) life : a cell has 2 or 3 alive neighbours
    2) death: a cell has <2 or >3 alive neighbours
    3) birth: an empty field has 3 alive neighbours

    but what's about the initial cells to begin with ?
    any suggestions? randomly with a percentage Input how many cells,
    dependent on fields at all shall be filled ? by the hand of the user ?
    fixed patterns to fill them?

    --
    greets

    (
    )
    (
    /\ .-"""-. /\
    //\\/ ,,, \//\\
    |/\| ,;;;;;, |/\|
    //\\\;-"""-;///\\
    // \/ . \/ \\
    (| ,-_| \ | / |_-, |)
    //`__\.-.-./__`\\
    // /.-(() ())-.\ \\
    (\ |) '---' (| /)
    ` (| |) `
    jgs \) (/


    one must still have chaos in oneself to be able to give birth to a
    dancing star
     
    anansi, May 3, 2007
    #11
  12. anansi wrote:
    > Puria Nafisi Azizi wrote:
    >> anansi wrote:
    >>> Never heard about it but read now wiki and sounds interesting, so I
    >>> would try it. Would you suggest a fixed count of columns and rows for

    >> pass it as an argument
    >>

    >
    > k so far I would suggest:
    >
    > (I)
    > passing row and col count as arguments
    > (II)
    > rules for cell stati:
    > 1) life : a cell has 2 or 3 alive neighbours
    > 2) death: a cell has <2 or >3 alive neighbours
    > 3) birth: an empty field has 3 alive neighbours
    >
    > but what's about the initial cells to begin with ?
    > any suggestions? randomly with a percentage Input how many cells,
    > dependent on fields at all shall be filled ? by the hand of the user ?

    pass as an argument to star with:
    * a glider
    * a glider gun
    * a 10x10 input file
    * a 10x10 random cells
    * an exploder

    pah, is not yet friday
     
    Puria Nafisi Azizi, May 3, 2007
    #12
  13. Ruby Quiz

    Paul Novak Guest

    Re: Checking Credit Cards (#122)

    One more way to do it: mutually recursive functions that each strip
    off the last character and alternate the doubling:

    http://pastie.caboo.se/58669

    or

    def luhn_sum s
    val = s.slice!(-1)
    if val==nil
    return 0
    end
    val.chr.to_i + luhn_helper( s)
    end

    def luhn_helper s
    val = s.slice!(-1)
    if val==nil
    return 0
    end
    (2 * val.chr.to_i).to_s.split("").inject(0){|sum,x|sum + x.to_i} +
    luhn_sum( s)
    end

    def luhn? s
    luhn_sum(s) % 10 == 0
    end

    Regards,

    Paul.
     
    Paul Novak, May 3, 2007
    #13
  14. On May 3, 2007, at 9:35 AM, anansi wrote:

    > James Edward Gray II wrote:
    >> On May 3, 2007, at 9:15 AM, anansi wrote:
    >>>> 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...
    >>>
    >>>
    >>> Means that: no quiz tomorrow ?!?

    >> Yes. I need a short break. We will have one the following Friday
    >> though.
    >> James Edward Gray II

    >
    >
    >
    > Maybe someone is interested or has an idea for an unoffical Ruby
    > Quiz for this week.


    Have you worked all 122 quizzes? ;)

    James Edward Gray II
     
    James Edward Gray II, May 3, 2007
    #14
  15. Ruby Quiz

    Robert Dober Guest

    BTW we missed the score of Pascal's half of a hexagon by the numbers
    of edges of a pentagon (no politics involved here). I express myself
    like this because I am a square head of course;)
    If you get my point you will miss the line under the triangle but I
    could not come up with this.
    Maybe I should just have submitted ten solutions ;)

    Take advantage of your break James.

    Cheers
    Robert
     
    Robert Dober, May 4, 2007
    #15
  16. Ruby Quiz <> writes:

    > 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.


    As if you needed further evidence after my third solution to pp
    Pascal.

    And the one in my solution is not *so* bad. The really nasty Luhn
    implementation was what I posted as a follow-up
    (http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/249669)
    That algorithm was:

    def luhn(s)
    s.scan(/\d/).map{|x|x.to_i}.inject([0,0]){
    |(a,b),c|[b+c%9,a+2*c%9]}[0]%10 == s.scan(/9/).size%10
    end

    Now, here's an explanation of the version in my posted solution:

    First, the code in my solution was this:

    def luhn(s)
    s.scan(/\d/).inject([0,0]){|(a,b),c|[b+c.to_i,
    a+c.to_i*2%9+(c=='9' ? 9 : 0)]}[0]%10 == 0
    end

    The main issue with doing the Luhn algorithm as a straight-forward
    inject command is that you don't know on each digit whether this digit
    is one that should be doubled or not.

    Now, there are a few ways around this:
    1) have a "should_double" variable that you initialize to
    should_double = (s.length % 2 == 0)
    and then in your block do
    should_double = !should_double
    2) reverse the data, and use something like each_index to get
    you the index each time, and double when the index is even
    (most people did this)
    3) like choice (1), but reverse the data and initialize
    should_double to false.

    I chose a different path: at each stage, compute both possibilities.
    That is, do an inject loop with two running totals - one in which the
    number we're dealing with now should be doubled, and one in which it
    shouldn't. At each stage, swap the two totals. At the end, pick the
    total that did not involve doubling the last digit.

    If the Luhn algorithm just involved adding the doubled digits (and
    didn't involve the added complication of adding their digits),
    generating both sums would be just:

    s.scan(/\d/).map{|x|x.to_i}.inject([0,0]){
    |(sum2, sum1),x| [sum1 + x, sum2 + 2*x]
    }

    Note how I swapped sum1 and sum2 in the process.

    Then, to take the sum that did not involve doubling the last digit,
    just do:

    s.scan(/\d/).map{|x|x.to_i}.inject([0,0]){
    |(sum2, sum1),x| [sum1 + x, sum2 + 2*x]
    }[0]

    Now, adding digits of numbers together is the well-known process of
    "casting out nines", and essentially what you're doing with that sum
    is taking the residue modulo 9. (in other language: "finding the
    remainder when dividing by 9") That is, adding the digits together
    turns 2*x into 2*x%9, except that if x is 9 then you get 9, not 0.
    This makes our sum algorithm into:

    s.scan(/\d/).map{|x|x.to_i}.inject([0,0]){
    |(sum2, sum1),x| [sum1 + x, sum2 + 2*x%9 + (x==9 ? 9 : 0)]
    }[0]

    This is almost my luhn method above, except that I used unhelpful
    one-letter variable names and didn't do the map call, preferring
    instead to use .to_i in the body of my inject loop.

    Now, go back and puzzle out the version I mentioned at the top of this
    email. That version was born out of a desire to avoid the ? :
    operator, since I tend to find it ugly.

    --
    s=%q( Daniel Martin --
    puts "s=%q(#{s})",s.to_a.last )
    puts "s=%q(#{s})",s.to_a.last
     
    Daniel Martin, May 6, 2007
    #16
  17. On 5/4/07, Robert Dober <> wrote:
    > BTW we missed the score of Pascal's half of a hexagon by the numbers
    > of edges of a pentagon (no politics involved here). I express myself


    I don't think half a hexagon is what you think it is :)

    martin
     
    Martin DeMello, May 6, 2007
    #17
  18. Ruby Quiz

    Robert Dober Guest

    On 5/6/07, Martin DeMello <> wrote:
    > On 5/4/07, Robert Dober <> wrote:
    > > BTW we missed the score of Pascal's half of a hexagon by the numbers
    > > of edges of a pentagon (no politics involved here). I express myself

    >
    > I don't think half a hexagon is what you think it is :)

    Hmm you think to know what I think, I think you know more than me than ;)
    >
    > martin
    >
    >



    --
    You see things; and you say Why?
    But I dream things that never were; and I say Why not?
    -- George Bernard Shaw
     
    Robert Dober, May 6, 2007
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz
    Replies:
    57
    Views:
    530
    Paul Novak
    May 3, 2007
  2. Todd Benson
    Replies:
    1
    Views:
    171
    Rolando Abarca
    Apr 30, 2007
  3. Daniel Martin
    Replies:
    4
    Views:
    180
  4. Brian Krahmer
    Replies:
    0
    Views:
    122
    Brian Krahmer
    May 1, 2007
  5. Pieter V.
    Replies:
    0
    Views:
    113
    Pieter V.
    May 3, 2007
Loading...

Share This Page