12
\$\begingroup\$

I've implemented Luhn's algorithm for checking credit card numbers. My code works, but I wanted to learn about a more efficient and more Pythonic way of doing this.

def validate_credit_card_number(card_number):
    #start writing your code here

    #Step 1a - complete
    temp_list=list(str(card_number))
    my_list=[]
    list1 = temp_list[-2::-2]
    list2=temp_list[::-2]
    list2 = [int (n) for n in list2]
    #print(list2)
    my_list=[int(n) for n in list1]
    #print(my_list)
    list1 = [int(n)*2 for n in list1]
    t_list=list1

    for el in list1:
        sum_res=0

        if el>9:
            idx = list1.index(el)
            t_list.pop(idx)

            while el:
                rem = el%10
                sum_res+=rem
                el = el//10 
            t_list.insert(idx, sum_res)
    #print(t_list)

    #step 1b

    list1_sum=sum(t_list)
    list2_sum = sum(list2)
    #print(b_list)
    final_sum = list1_sum+ list2_sum
    #print(final_sum)

    if final_sum%10==0:
        return True
    return False

card_number= 1456734512345698 #4539869650133101  #1456734512345698 # #5239512608615007

result=validate_credit_card_number(card_number)
if(result):
    print("credit card number is valid")
else:
    print("credit card number is invalid")
\$\endgroup\$
  • \$\begingroup\$ (Welcome to Code Review!) (This question seems to be getting smoother by the edit…) \$\endgroup\$ – greybeard Dec 14 '18 at 21:17
12
\$\begingroup\$

Style

Python has a style guide called PEP 8. It is a good habit to try to follow it.

In your case, that would mean fixing the missing whitespaces, removing parenthesis in if(result).

Also, you could get rid of old commented code and add a proper docstring if you want to describe the behavior of the function.

Tests

It could be a good idea to write tests before trying to improve your code.

I wrote a very simple code but you could get this chance to dive into unit testing frameworks:

TESTS = [
    (1456734512345698, False),
    (4539869650133101, True),
    (1456734512345698, False),
    (5239512608615007, True),
]

for (card_number, expected_valid) in TESTS:
    valid = validate_credit_card_number(card_number)
    assert valid == expected_valid

Useless test

At the end of the function, you can return directly:

return final_sum % 10 == 0

Useless variables

The my_list variable is not required.

Also, we can take this chance to get rid of the variables at the end of the function:

return (sum(t_list) + sum(list2)) % 10 == 0

Conversion of card_number

At the beginning of the function, you could convert the parts of card_number directly to integer so that you do it in a single place. Also, that removed the need to the call of list. We just have:

temp_list = [int(c) for c in str(card_number)]

And we can get rid of the line:

list2 = [int (n) for n in list2]

At this stage, the code looks like:

def validate_credit_card_number(card_number):
    temp_list = [int(c) for c in str(card_number)]

    list1 = temp_list[-2::-2]
    list1 = [2 * n for n in list1]

    list2 = temp_list[::-2]

    t_list = list1

    for el in list1:
        sum_res = 0

        if el > 9:
            idx = list1.index(el)
            t_list.pop(idx)

            while el:
                rem = el % 10
                sum_res += rem
                el = el // 10
            t_list.insert(idx, sum_res)

    return (sum(t_list) + sum(list2)) % 10 == 0

Yet another useless variable

t_list aliases list1 (I am not sure if this is intended if if you were planning to have a copy of list1). Whenever you update the list through one variable, the other is affected as well. I highly recommend Ned Batchelder's talk about names and values.

In your case, we can get rid of t_list completely without changing the behavior of the function.

Simplify list logic

You go through multiple steps to modify list1 (or t_list) : index, pop, index. These steps are more expensive/complicated than required. At the end of the day, you do not care about list1, you just want its final sum. You could keep track of the sum directly:

sum1 = 0
for el in list1:
    if el > 9:
        sum_res = 0
        while el:
            rem = el % 10
            sum_res += rem
            el = el // 10
        sum1 += sum_res
    else:
        sum1 += el

return (sum1 + sum(list2)) % 10 == 0

We can take this chance to perform the multiplication in the loop to remove a list comprehension.

Also, we can initialise the sum with sum(list2) so that we don't have to add them at the end:

def validate_credit_card_number(card_number):
    temp_list = [int(c) for c in str(card_number)]

    list1 = temp_list[-2::-2]
    list2 = temp_list[::-2]

    total_sum = sum(list2)
    for el in list1:
        el *= 2
        if el > 9:
            sum_res = 0
            while el:
                rem = el % 10
                sum_res += rem
                el = el // 10
            total_sum += sum_res
        else:
            total_sum += el

    return total_sum % 10 == 0

Math logic

The code uses 10 (the base used for computations) everywhere except for one 9 which seems unexpected. You could write: el >= 10 instead.

Also, that check is not required because the logic applies exactly the same way for elements smaller than 10:

for el in list1:
    el *= 2
    sum_res = 0
    while el:
        rem = el % 10
        sum_res += rem
        el = el // 10
    total_sum += sum_res

Also, you could use el //= 10 but you can get the best ouf of the Python builtins by using divmod returning both the quotient and the remainder:

    while el:
        el, rem = divmod(el, 10)
        sum_res += rem
    total_sum += sum_res

Then, it becomes clear that the variable sum_res is not really required as we could use total_sum instead:

    while el:
        el, rem = divmod(el, 10)
        total_sum += rem

"Final" code

def validate_credit_card_number(card_number):
    temp_list = [int(c) for c in str(card_number)]

    list1 = temp_list[-2::-2]
    list2 = temp_list[::-2]

    total_sum = sum(list2)
    for el in list1:
        el *= 2
        while el:
            el, rem = divmod(el, 10)
            total_sum += rem

    return total_sum % 10 == 0

TESTS = [
    (1456734512345698, False),
    (4539869650133101, True),
    (1456734512345698, False),
    (5239512608615007, True),
]

for (card_number, expected_valid) in TESTS:
    valid = validate_credit_card_number(card_number)
    assert valid == expected_valid

More simplification

Thinking about it, things can still be simplified a lot. What you are doing with the while loop can be performed using str conversion:

total_sum = sum(list2)
for el in list1:
    total_sum += sum(int(c) for c in str(2 * el))

Going further (too far?), this leads to:

def validate_credit_card_number(card_number):
    temp_list = [int(c) for c in str(card_number)]

    list1 = temp_list[-2::-2]
    list2 = temp_list[::-2]

    total_sum = sum(list2) + sum(sum(int(c) for c in str(2 * el)) for el in list1)
    return total_sum % 10 == 0

Edit:

More simplification

We are using str and int to get the digits of a number... which is known to be smaller than 18 (2 * 9). A trick could be, once again, to use divmod returning the quotient and remainder and use sum on it.

total_sum = sum(list2)
for el in list1:
    total_sum += sum(divmod(2 * el, 10))

or

total_sum = sum(list2) + sum(sum(divmod(2 * el, 10)) for el in list1)

Playing with indices

Instead of splitting the list into 2 lists, we could iterate over the (reversed) list once and handle differently elements at odd positions and elements at even positions.

We'd get something like:

def validate_credit_card_number(card_number):
    temp_list = [int(c) for c in str(card_number)]

    total_sum = 0
    for i, e in enumerate(reversed(temp_list)):
        if i % 2 == 0:
            total_sum += e
        else:
            total_sum += sum(divmod(2 * e, 10))

    return total_sum % 10 == 0

Or the more concise solution taking advantage of the fact that the divmod trick works for both cases:

def validate_credit_card_number(card_number):
    total_sum = 0
    for i, c in enumerate(reversed(str(card_number))):
        e = int(c) * (2 if i % 2 else 1)
        total_sum += sum(divmod(e, 10))
    return total_sum % 10 == 0

or

def validate_credit_card_number(card_number):
    return sum(sum(divmod(int(c) * (2 if i % 2 else 1), 10))
               for i, c in enumerate(reversed(str(card_number)))) % 10 == 0
\$\endgroup\$
  • \$\begingroup\$ @HackersInside actually, I have other ideas that could somehow improve the solution. I'll try to update the answer when I am on a computer \$\endgroup\$ – Josay Dec 14 '18 at 19:55
  • \$\begingroup\$ @HackerInside I've edited my answer. \$\endgroup\$ – Josay Dec 15 '18 at 10:40
  • 2
    \$\begingroup\$ 2 if i % 2 else 1i % 2 + 1 \$\endgroup\$ – Gareth Rees Dec 15 '18 at 10:56
4
\$\begingroup\$

Josay's answer is right on the money in terms of how to start optimizing one's Python code.

Below I go further with the optimization that Josay started. I should warn that the code is at a stage where optimizations begin to really flirt with readability, and so for shared code that must be understood and maintained, we're home safe.

If we desire to get a "one-liner" Python script, for what it's worth, let's look at the difference between list1 and list2. As a side-note about style, more descriptive names of these lists might be evens and odds: hints that would really help the person who has to read your code.

Finding commonality in how the odds even digits are handled

Recall that for our sum, we will be adding up all the numbers in odds. We will, in fact, also be adding up all the digits in evens, except we will also add them up again (doubling). Then we also need to account for the cases when the doubling results in two-digit numbers, but more on that below.

Since both odds and evens adds each digit, we could start off with just adding up all the digits:

def validate_credit_card_number(card_number):     #incomplete code
    temp_list = [int(c) for c in str(card_number)]
    return ( sum(temp_list) + CORRECTIONS ) % 10 == 0

So what are the corrections we need to make? Well, every other digit needs to be added again. Instead of dividing the list up into evens and odds and separating the problems, what if we had some sort of indicator that we are processing an odd or an even digit?

Correcting for the even numbers

One possible answer is to somehow look up the index of the digit we are processing, and seeing if that one is odd or even. The check for whether i is odd is just (i % 2) == 1.

But what's a good way of getting to know both the index of the digit and the digit itself? Python has a nice built-in iterator called enumerate. Formally, enumerate gives you a generator that provides (index,element) pairs from a list. To illustrate, enumerate (["foo","bar",7,"zoo"]) returns a generator for [(0, 'foo'), (1, 'bar'), (2, 7), (3, 'zoo')]. Great! Let's see if we can use that.

def validate_credit_card_number(card_number):     #incomplete code
    temp_list = [int(c) for c in str(card_number)]
    return sum([ x + (x if (i % 2)==0 else 0) for (i,x) in enumerate(temp_list)]) % 10 == 0

Here we use Python's a if <test> else b ternary notation to check if the number is the even number.

Thinking backwards

But wait ... the Luhn specification said we needed to start counting from the right-most digit. So what if that digit happens to have an even index? Our odds and evens would be exactly switched! Here, we would notice that it'd be so much more convenient to just count from the right. All we are doing is adding up numbers, so it wouldn't make any difference if we were to just reverse the list first! We just have to be careful that the rightmost digit in the reverse list (temp_list) is now at index 0, so we must now be correcting the odd numbers.

def validate_credit_card_number(card_number):     #incomplete code
    temp_list = reversed([int(c) for c in str(card_number)])
    return sum([ x + (x if (i % 2)==1 else 0) for (i,x) in enumerate(temp_list)]) % 10 == 0

Fixing the double digit cases

Much better. But, alas, there is still an issue with the double digits. If the digit at the even index is 0, 1, 2, 3, or 4, we actually do the right thing: double the number. But if it's 5, 6, 7, 8, or 9, we are currently adding 10, 12, 14, 16, 18 instead of 1, 3, 5, 7, 9, respectively. But for those numbers, the difference between what we do now and what we should do is always 9! How about adding a check for whether the digit is 5 or more, in which case subtract 9?

def validate_credit_card_number(card_number):
    temp_list = reversed([int(c) for c in str(card_number)])
    return sum([ x + (x + (-9 if x>=5 else 0) if (i % 2)==1 else 0) for (i,x) in enumerate(temp_list)]) % 10 == 0

This code actually works!

Simplifying with modulus tricks

Let's keep going! If we add -9 to a sum that we are reducing modulo 10, that's the same as adding 1 to the sum. Why? Because \$-9 \pmod{10} \equiv 10 + (-9) \pmod{10} \equiv 1 \pmod{10}\$ since the extra 10 doesn't change the modulus. It's a bit like saying that 9 hours ago, the clock hand pointed at the same number as it will do \$(12-9)=3\$ hours from now -- except that clocks work modulo 12.

def validate_credit_card_number(card_number):
    temp_list = reversed([int(c) for c in str(card_number)])
    return sum([ x + (x + (1 if x>=5 else 0) if (i % 2)==1 else 0) for (i,x) in enumerate(temp_list)]) % 10 == 0

Multiplication instead of ternary operator

Also, we can replace the ternary operators (the if business) with simple multiplication. Why? Because there is no difference between 8 + (42 if x%2==1 else 0) and 8 + 42*(x%2). Further, something like 8 + (1 if x%2==1 else 0) could just be simplified to 8 + (x%2).

Using these ideas, we now have:

def validate_credit_card_number(card_number): 
    temp_list = reversed([int(c) for c in str(card_number)])
    return sum([ x + (x+(x>=5))*(i%2) for (i,x) in enumerate(temp_list)]) % 10 == 0

Mapping to a one-liner

Nice. Now, can we squeeze this whole expression into a single line, just because? Here, we may notice that the list comprehension for temp_list is really just applying int to every character in card_number. There is another nice built-in function in Python called map, a descendant from functional programming languages, that takes a function and a list, and applies the function to each element of a list. (From a Pythonic style perspective, bear in mind that generator expressions are usually favorable to map, which almost got removed in Python3).

def validate_credit_card_number(card_number): 
    temp_list = reversed(list (map(int, [c for c in str(card_number)])))
    return sum([ x + (x+(x>=5))*(i%2) for (i,x) in enumerate(temp_list)]) % 10 == 0

One-liner ahoy!

Wait a minute. When we see [c for c in str(card_number)], we should pause and think about what list we are really generating. When you think about it, str(card_number) return a string, and Python strings implement an iterator. So for our purposes, we could just treat str(card_number) as a list of characters! This gives:

def validate_credit_card_number(card_number): 
    temp_list = reversed(list (map(int, str(card_number))))
    return sum([ x + (x+(x>=5))*(i%2) for (i,x) in enumerate(temp_list)]) % 10 == 0

The list bit is ugly. So let's reverse the string earlier and conclude with:

def validate_credit_card_number(card_number): 
    return sum([x + (x+(x>=5))*(i%2) for (i,x) in enumerate(map(int, reversed(str(card_number))))]) % 10 == 0

Shorter still?

There are still opportunities to shorten the expression. For one, we could assume that the input is actually a string already. For another, we can remove the reversal business and just figure out if the doubling should happen for evens or odds by looking at the length of the input string. This gives:

def validate_credit_card_number(card_str): 
    return sum([x + (x+(x>=5))*((len(card_str)-1+i)%2) for (i,x) in enumerate(map(int, card_str))]) % 10 == 0
\$\endgroup\$
  • 2
    \$\begingroup\$ I'm really taken back. Just one line. 😍 \$\endgroup\$ – HackersInside Dec 15 '18 at 5:57
  • 1
    \$\begingroup\$ Welcome here! This is a very nice answer, I'm looking forward to reading more of your contributions in the near future! \$\endgroup\$ – Josay Dec 15 '18 at 21:54
3
\$\begingroup\$

I assume that card_number is an integer. As such, you should not convert it to a str, nor convert it to a list. You should be doing integer operations only, not list operations.

For your learning purposes, I won't rewrite the algorithm for you, but try to rewrite it such that it's represented as a loop over the credit card number, which successively gets divided by 10.

\$\endgroup\$
  • \$\begingroup\$ How am I supposed to iterate over a number, even if I break the number to digits, I will have to store it in a list for further processing. \$\endgroup\$ – HackersInside Dec 14 '18 at 17:06
  • \$\begingroup\$ Nope. Successively divide the number by 10 and work with the modulus. \$\endgroup\$ – Reinderien Dec 14 '18 at 17:07
  • \$\begingroup\$ Ok, I will try that out. However, I was wondering what would be the cons of converting it to a list/str? \$\endgroup\$ – HackersInside Dec 14 '18 at 17:09
  • \$\begingroup\$ It's slower and uses (slightly) more memory. \$\endgroup\$ – Reinderien Dec 14 '18 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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