Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Write the shortest (fewest number of characters) function that performs the Luhn algorithm checksum on a number.

Requirements:

  • Use the Modulus 10 version (original)
  • Function should accept a string of numbers (e.g. credit card number)
  • Returns true if the number passes, false if not
  • Please include the number of characters your program takes up, to make judging easier (suggested tool).

Tips

  • Try not to accidentally post your own credit card or account numbers, if you use them to test :)
  • Description of algorithm on Wikipedia page (see link at top of question)
share|improve this question
    
Do we have to make a function? Or a full program? If it's a full program how can we take input, and also, what is accepted as returning true or false? –  Juan Jan 27 '11 at 21:58
    
Let me clarify- thanks –  Chris Laplante Jan 27 '11 at 22:00
1  
is the credit card number given as a string or as a number? –  Alexandru Jan 27 '11 at 22:01
1  
String. Two reasons: If it was given as a number, it might be too much for some languages to handle. Secondly, you would need to cast it to a string to access each individual character anyway. –  Chris Laplante Jan 27 '11 at 22:03
    
Do this need to work with both odd-length and even-length strings? I'm assuming so, but imagine this is a pitfall folks may not notice, since Luhn counts even digits from the right. –  MtnViewMark Jan 29 '11 at 7:03
show 1 more comment

19 Answers

up vote 15 down vote accepted

Golfscript - 24 chars

-1%{2+0!:0)*109%+}*10%8=

Explanation:

  1. -1% reverses the string
  2. { begins a block (which we use as a loop). Each character in the strings is pushed as it's ascii value.
    1. 2+ adds 2. (the ascii value of a digit is 48+n, so we have 50+n now and the last digit is n)
    2. 0!:0 inverts the value of 0 and stores it (everything is a variable), so we have 1 on the first iteration, 0 on the second, etc.
    3. )* adds one to this value and multiplies it, so we multiply by 2, then 1, then 2, etc.
    4. 109% is remainder modulo 109. This affects only values 5-9 which have been doubled and reduces them to the correct value.
    5. + adds this value to the running sum
  3. }* ends the block and does a 'fold' operation. First, the first character is pushed (since we have reversed, this is the check digit). Then, alternate pushing and executing the block. Thus, we are using the first character's ascii value as the starting value for the running sum.
  4. 10% takes the remainder modulo 10.
  5. 8= will return 1 if the value is 8. We use this because we did not normalize the first pushed character (the check digit).

One might think that we could use 8- instead of 2+ to save a character by changing 109% to 89%, except then we would need to add a space so the - is subtraction (instead of -0).

share|improve this answer
add comment

GolfScript, 44 chars

-1%{16%}%2/1,\+{(\.{0=2*.9>9*-+}{;}if+}*10%!

Selected commentary

Interestingly, the first two items below demonstrate three completely different uses of the % operator: array selection, map, and mod. Most GolfScript operators are "context-sensitive", giving them hugely divergent behaviours depending on what types the arguments are.

  1. -1% reverses the string. This is important as the digit pairs are counted from the right.
  2. {16%}% converts all the ASCII digits into numbers, by modding them with 16.
  3. 2/ splits the array into groups of 2.
  4. 1, is a cheap way to do [0].
  5. \+ effectively prepends the 0 to the digits array. It does this by swapping then concatenating.

The 0 is prepended in preparation for the fold that comes in next. Rather than taking an explicit initial value, GolfScript's fold uses the first item in the array as the initial value.

Now, let's look at the actual fold function. This function takes two arguments: the folded value, and the current item on the array (which in this case will be an array of 2 or (uncommonly) 1, because of the 2/ earlier). Let's assume the arguments are 1 [2 3].

  1. (\. splits out the leftmost array element, moves the remaining array to the front, then copies it. Stack now looks like: 1 2 [3] [3].
  2. The if checks if the array is empty (which is the case for the last group when dealing with an odd-sized account number). If so, then no special processing happens (just pop off the empty array).
  3. For an even group:
    1. 0= grabs the first (only, in this case) element of the array. 1 2 3
    2. 2* doubles the number. 1 2 6
    3. .9>9*- subtracts 9 from the number if it's greater than 9. Implemented as: copy the number, compare with 9, multiply the result (which is either 0 or 1) with 9, then subtract. 1 2 6
    4. + finally adds that to the first number. 1 8
  4. + (after the if) adds the result of the if to the original value, resulting in the new folded value.

After the folding completes, we simply mod with 10 (10%), and negate the result (!), so that we return 1 iff the sum is a multiple of 10.

share|improve this answer
    
This seems to return 0 for the example number on wikipedia (49927398716) –  gnibbler Feb 1 '11 at 10:51
    
nm. I forgot to use echo -n –  gnibbler Feb 1 '11 at 11:49
1  
@gnibbler: Haha, fail. :-P (Seriously, I got stung by that one too, in my initial testing.) –  Chris Jester-Young Feb 1 '11 at 13:06
1  
A few places to save a few easy characters here. -1% 2/ can be combined into -2/. 1, can be replaced with 0 (0 is coerced to an array, then + is concatenate). 9>9*- can be replaced with 9>+ (since we're only concerned with the last digit). Also, the checking for odd lengths is a bit long, using .,2%,\+ is shorter. After doing this, we can also change {16%}% and (\0= into {16}/ (inside the loop). Once you've done all that, it'll look something like this: .,2%,\+-2/0\+{{16%}/2*.9>+++}*10%!. –  Nabb Feb 2 '11 at 17:15
    
@Nabb: Thanks! I'll incorporate those into my solution, although it looks like you already have one that's kicking serious arse. :-) –  Chris Jester-Young Feb 2 '11 at 17:40
show 1 more comment

Python, 73 69 characters

def P(x):D=map(int,x);return sum(D+[d-d/5*9for d in D[-2::-2]])%10==0
share|improve this answer
    
You can save two more chars by not looping backwards : D[-2::-2] -> D[1::2] as the order of a sum isn't important :) –  plg Feb 1 at 23:14
add comment

C# 119 characters:

bool l(string n){return(String.Join("",n.Reverse().Select((x,i)=>(x-48)*(i%2<1?1:2)+"").ToArray()).Sum(x=>x-48))%10<1;}

Not too bad for a code golf n00b in a statically typed language, I hope.

This can be reduced to 100:

bool l(string n){return String.Join("",n.Reverse().Select((x,i)=>(x-48)*(i%2+1))).Sum(x=>x+2)%10<1;}
share|improve this answer
    
It's a good idea, and an interesting approach, but it doesn't appear to work. At least not with my few tests. It looks like the "i" in your first lambda is supposed to be the index of the character in the string. Does that work as it should? If so, why do you reverse the string only to then modify it based on index position? Seems a bit redundant, no? –  Nellius Feb 1 '11 at 23:48
    
I only tested one of my credit cards and a few off by one errors from it TBH. (Using the VS 2008 debugger) The algorithm is supposed to double every second digit starting with the LAST digit. If I didn't reverse the string, it would be incorrect for strings with odd lengths. –  mootinator Feb 2 '11 at 1:37
    
Turns out I did have the result of i%2<1?1:2 backwards. Thanks. –  mootinator Feb 2 '11 at 1:59
add comment

In Python3 77 characters:

c=lambda a:sum(sum(divmod(int(a[-e-1])<<e%2,10))for e in range(len(a)))%10==0
share|improve this answer
add comment

Golfscript - 34 chars

{15&}%.-2%\);-2%{.+(9%)}%+{+}*10%!

Example number from wikipedia page 4992739871

{15&}%  does a bitwise and of each ascii digit with 00001111
        now I have a list of digits 
        [4 9 9 2 7 3 9 8 7 1 6]
.       makes a copy of the list, now I have two identical lists
        [4 9 9 2 7 3 9 8 7 1 6] [4 9 9 2 7 3 9 8 7 1 6]
-2%     like [::-2] in python takes every second element in reverse
        [4 9 9 2 7 3 9 8 7 1 6] [6 7 9 7 9 4]
\       swap the two lists around
        [6 7 9 7 9 4] [4 9 9 2 7 3 9 8 7 1 6]
);      drop the last digit off the list
        [6 7 9 7 9 4] [4 9 9 2 7 3 9 8 7 1]
-2%     same as before
        [6 7 9 7 9 4] [1 8 3 2 9]
{       for each item in the list ...
.+      ... double it ...
(       ... subtract 1 ...
9%      ... mod 9 ...
)}%     ... add 1 ...
        [6 7 9 7 9 4] [2 7 6 4 9]
+       join the two lists
        [6 7 9 7 9 4 2 7 6 4 9]
{+}*    add the elements up
        70
10%     mod 10
        0
!       invert the result
        1
share|improve this answer
    
The .+(9%) is very innovative (for me, anyway). I like! +1 –  Chris Jester-Young Feb 1 '11 at 13:09
    
Srsly though, GolfScript needs a partitioning operator, so you don't need to do this "drop end item off and repeat" nonsense. :-) –  Chris Jester-Young Feb 1 '11 at 13:14
1  
@Chris, I learned about that many years ago called "casting out nines". It is a neat way to double check longhand additions and multiplications –  gnibbler Feb 1 '11 at 13:22
3  
This won't work for a value of 0 being doubled (0(9%) is 9 and not 0). –  Nabb Feb 2 '11 at 16:59
add comment

There must be a better/shorter way, but here's my Haskell solution in 96 characters:

l=(==0).(`mod`10).sum.zipWith($)(cycle[id,\x->x`mod`5*2+x`div`5]).reverse.map((+(-48)).fromEnum)

Sadly the digitToInt function can only be used if you import Data.Char first. Otherwise I could get down to 88 characters by replacing ((+(-48)).fromEnum) with digitToInt.

share|improve this answer
add comment

Ruby - 85 characters

def f s
l=s.size
s.chars.map{|k|(i=k.to_i*((l-=1)%2+1))%10+i/10}.inject(:+)%10==0
end
share|improve this answer
add comment

PHP 108 characters:

<?function v($s,$t=0){for($i=strlen($s);$i>=0;$i--,$c=$s[$i])$t+=$c+$i%2*(($c>4)*-4+$c%5);return!($t % 10);}
share|improve this answer
add comment

D: 144 Characters

bool f(S)(S s){int t(C)(C c){return to!int(c)-'0';}int n,v;foreach(i,c;array(retro(s))){v=i&1?t(c)*2:t(c);n+=v>=10?v%10+v/10:v;}return n%10==0;}

More Legibly:

bool f(S)(S s)
{
    int t(C)(C c)
    {
        return to!int(c) - '0';
    }

    int n, v;

    foreach(i, c; array(retro(s)))
    {
        v = i & 1 ? t(c) * 2 : t(c);

        n += v >= 10 ? v % 10 + v / 10 : v;
    }

    return n % 10 == 0;
}
share|improve this answer
add comment

PowerShell 123

filter L($x){$l=$x.Length-1;$l..0|%{$d=$x[$_]-48;if($_%2-eq$l%2){$s+=$d}elseif($d-le4){$s+=$d*2}else{$s+=$d*2-9}};!($s%10)}
share|improve this answer
add comment

Windows PowerShell, 82

filter f{!((''+($_[($_.length)..0]|%{+"$_"*($i++%2+1)})-replace'.','+$&'|iex)%10)}

History:

  • 2011-02-13 03:08 (84) First attempt.
  • 2011-02-13 12:13 (82) I don't need to join, as spaces do not hurt. +1 + +3 can still be evaluated.
share|improve this answer
add comment

Q, 63

{0=mod[(+/)"I"$(,/)($)($)@["I"$'x;1+2*'(!)(_)((#)x)%2;*;2];10]}

usage

q){0=mod[(+/)"I"$(,/)($)($)@["I"$'x;1+2*'(!)(_)((#)x)%2;*;2];10]}"79927398711"
0b
q){0=mod[(+/)"I"$(,/)($)($)@["I"$'x;1+2*'(!)(_)((#)x)%2;*;2];10]}"79927398712"
0b
q){0=mod[(+/)"I"$(,/)($)($)@["I"$'x;1+2*'(!)(_)((#)x)%2;*;2];10]}"79927398713"
1b
share|improve this answer
add comment

Scala: 132

def q(x:Int)=x%10+x/10
def c(i:String)={val s=i.reverse
(s(0)-48)==10-(s.tail.sliding(2,2).map(n=>(q((n(0)-48)*2)+n(1)-48)).sum%10)}

invocation:

c("79927398713")
  • reverse ("79927398713") = 31789372997
  • s(0), s.tail: (3)(1789372997)
  • sliding (2,2) = (17 89 37 29 97)
  • map (q((n(0)-48*2 + n(1)-48)) => q(('1'-'0')*2)+ '7'-'0')=1*2+7
share|improve this answer
add comment

JavaScript 1.8: 106 characters

This is an original solution I came up with before I found this post:

function(n){return!(n.split('').reverse().reduce(function(p,c,i){return(+c&&((c*(1+i%2)%9)||9))+p},0)%10)}

Readable form:

function luhnCheck(ccNum) {
    return !(                                  // True if the result is zero.
             ccNum.split('').
               reverse().                      // Iterate over the string from rtl.
               reduce(function(prev, cur, idx) {
                 return prev +                 // Sum the results of each character.
                        (+cur &&               // If the current digit is 0, move on.
                         ((cur * (1 + idx % 2) // Double cur at even indices.
                           % 9) || 9));        // Sum the digits of the result.
               }, 0)
            % 10);                             // Is the sum evenly divisible by 10?
}
share|improve this answer
1  
ccNum is not used. I think it should be n –  Clyde Lobo Sep 3 '13 at 13:01
add comment

Haskell: 97

For some reason this isn't working for me, so here is my version

l=(\x->(==0)$(`mod`10).sum$zipWith($)(cycle[id,sum.map(read.(:"")).show.(*2)])(map(read.(:""))x))
share|improve this answer
add comment

k4 (35)

{~.*|$+/.:',/$x*1+1{y;~x}\|x:|.:'x}

share|improve this answer
add comment

APL (38)

d←10∘⊥⍣¯1⋄{0=10|+/+/d x×1+~2|⍳⍴x←⌽d ⍵}

expects the number as a number, not a string, but that's only because tryAPL (understandably) doesn't implement

further reducible, i'm sure…

share|improve this answer
add comment

APL, 28

{0=10|+/⍎¨∊⍕¨v×⌽2-2|⍳⍴v←⍎¨⍵}

Exploded view

{                     v←⍎¨⍵}  ⍝ turn the string into a numeric vector of its digits, v
                2-2|⍳⍴v       ⍝ make a vector of the same length, with 2 in every 2nd place
             v×⌽              ⍝ multiply it with v, starting from the right
          ∊⍕¨                 ⍝ turn each component into a string and collect all the digits
      +/⍎¨                    ⍝ turn each digit again into a number and sum them
 0=10|                        ⍝ check whether the sum is a multiple of 10

Examples

      {0=10|+/⍎¨∊⍕¨v×⌽2-2|⍳⍴v←⍎¨⍵} '79927398713'
1
      {0=10|+/⍎¨∊⍕¨v×⌽2-2|⍳⍴v←⍎¨⍵} '123456789'
0
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.