12
\$\begingroup\$

I started following Harvard's CS50 (Introduction to Computer Science) on edX, and as part of their Hacker edition set 1 was the following assignment:

I am supposed to write a program (in C), that takes as input a long long int from the user and proceeds to check whether the entered number is a valid credit card number. For the purposes of this assignment, I am only interested in Visa, American Express and MasterCard number formats. The validation is done with Luhn's algorithm.

/* This program checks whether an entered number is a valid
 * credit card number (only American Express, Visa and 
 * MasterCard formats are supported).
 */

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

int main(void)
{
    long long int credit_card;
    int digits = 0;
    string bank = "";

    printf("Number: ");
    credit_card = GetLongLong();

    // calculate number of digits
    for (long long int temporary = credit_card; temporary > 0;
                    temporary /= 10, digits++);

    // check if number length corresponds to valid format
    switch (digits)
    {
        case 13:
            if ( (credit_card / (long long int) pow(10, digits - 1) ) == 4)
            {
                bank = "VISA";
                break;
            }

        case 15:
            if ( ( (credit_card / (long long int) pow(10, digits - 2)) == 34 ) || 
                   (credit_card / (long long int) pow(10, digits - 2)) == 37)
            {
                bank = "AMEX";
                break;
            }

        case 16:
            if ( ( (credit_card / (long long int) pow(10, digits - 2)) >= 51) && 
                   (credit_card / (long long int) pow(10, digits - 2)) <= 55)
            {
                bank = "MASTERCARD";
                break;

            }
            else if ( (credit_card / (long long int) pow(10, digits - 1) ) == 4)
            {
                bank = "VISA";
                break;
            }
        // sets bank to invalid if it doesn't satisfy any of the standards.
        default:
            bank = "INVALID";
    }

    if (strcmp(bank, "INVALID") != 0)
    {
        // used for summing up the digits of the credit card number.
        int odd_sum = 0, even_sum = 0, total = 0;

        // looping through all the digits, decreasing credit_card on every iteration
        for (int i = 1; i <= digits; i++, credit_card /= 10)
        {   
            // gets the last digit of credit_card
            int digit = credit_card % 10;

            // performs the necessary tasks on every other digit, starting from the next-to-last one.
            if (i % 2 == 0)
            {
                int prod_dig_sum = 0;

                digit *= 2;
                prod_dig_sum += (digit % 10) + (digit / 10);
                even_sum += prod_dig_sum;
            }

            else
            {
                odd_sum += digit;
            }
        }

        total = odd_sum + even_sum;

        if (total % 10 == 0)
        {
            printf("%s\n", bank);
            return 0;
        }

        else
        {
            printf("INVALID\n");
            return 0;
        }
    }

    printf("INVALID\n");
    return 0;
}

Notes:

  • The cs50.h library is custom-made by the Harvard staff
  • the function GetLongLong() is part of that library, and I currently don't know all the details of how this function works
  • This assignment is fairly early in the course, so we are only supposed to use the most basic tools of C. Basically, only conditions and loops.
  • I focused mainly on code readability, sometimes on expense of exactness

Having said all that, I am wondering if there is maybe a more elegant way to do all the checking involved in my program. The way it is now, I think I may have over-complicated the process a bit.

\$\endgroup\$
  • 1
    \$\begingroup\$ You're consuming credit_card in the for loop. Okay here since you don't need it later, but let's say 1 month from now there's a new criteria they add to credit card numbers that says the sum of the even digits must equal the sum of the odd digits. Your code is less flexible because this variable is gone. If the credit card was passed.by reference, you may have unintentionally mutated a shared variable. \$\endgroup\$ – IceArdor Aug 16 '15 at 12:44
10
\$\begingroup\$

It could be very difficult to give you good hints, because of your restrictions. I would complain that you didn't use functions to encapsulate functionality. Well, but for the future I give you some quotes, why I would use a function in some places.

First of all, you try to determine the number of digits of the credit card number. The way you solved this problem is strait forward, but I think it would be more readable with a log10-aproach. You can read something about log10 or just play a little around. It returns a floating point number which is close to the number of digits. You only need to call ceil for it:

digits = ceil(log10(credit_card));

Here I would use a function called getNumberOfDigits(long long int number), so you don't have to think about your for-loop or my ceil-log10-thing.


Now your switch statement. I prefer if-then-else statements, but I think this is ok here, even though it is very heavy because of all the code in there. I would use functions here to get the body of the switch statement smaller. But we can get is smaller anyway (in a second).

I think it is a bad thing to let the switch statement drop through all cases if, lets say, the credit card number has 13 digits but doesn't fit the next if statement. This leads to bugs! Like in this case. Try this number: 3401234567890. It is 13 digits long, not 15 or 16, so it could be a VISA card, but the results says its an AMEX card.

The if statements inside the switch statement are very long and doing heavy stuff many times (pow and division are expensive operators. Again, you don't have to think about this now, but in future you gonna get in trouble if you have to do your work with big data in nearly no time).

If someone reads your code, he has to think about the expressions twice before he knows what you are doing. You try to get the highest digits to compare them. But wouldn't it be nice if you can do something like this:

if (most_significant_digit == 3 && second_significant_digit == 4) { ...

This simply tells him what you trying to do. Because you have included the stdio and string library I hope you are allowed to convert a number to a string:

string credit_card_digits;
sprintf(credit_card_digits, "%lli", credit_card);

I think the string type you use is a lie. I think it is a char* but your shouldn't have to think about pointers now, you will learn about them later any way, so we use the string type (if you try this and have problems, just replace string with char*).

Ok, why should we do this? Now you can access each character directly (and you can determine the size of the number with strlen, so you don't have to do the ceil-log10-thing). A string is indexed from the left to the right, so the first letter is the most_significant_digit of our new if statement. You get the first letter by calling credit_card_digits[0]. So our if statement looks like this:

if (credit_card_digits[0] == '3' && credit_card_digits[1] == '4') { ...

Not as nice as our first attempt, but you could introduce new variables.

The result of credit_card_digits[0] is of type char but you can handle it like an integer, except you have to put the numbers in single quotes and the numbers are only allowed to have one digit.


The second part of your program: Again, I would encapsulate the Luhn's algorithm.

The first thing I noticed was the credit_card /= 10 inside the for loop header. I think this is strange, because the credit_card is no control variable like i. So I would do this as the first statement in the for loop body.

The second thing were the last few lines. You are doing the same thing three times: print the name of the bank or invalid and return 0. But you could set the name of the bank to invalid if total % 10 is not 0. So you can print the name and return 0 at the end of the main function.

There are people out there, who say a function is only allowed to have one return statement (called Single Entry, Single Exit). In some programing languages like C/C++ it is very useful.


Last of all I want to say: good job. The way to learn how to program is not a short one. I did it without help, and needed more then ten years to get it right (not perfect, but it was ok). But I didn't had internet back then.

I think it is a good idea to ask other people to review your code. You can learn many thinks and you can protect yourself of bad habits.

To learn even more you could read code written by other developers, but you have to search for nice clean code. Not every open source project is suitable to learn good coding ;-)

\$\endgroup\$
  • \$\begingroup\$ Updated the code with some of your suggestions. The function sprintf wasn't covered in the lectures, so I'll leave that out for now. Since I cannot use functions, is the ceil(log10(credit_card)) more readable than my for loop when it comes to calculating the number of digits? \$\endgroup\$ – Stefan Rendevski Aug 16 '15 at 0:18
  • \$\begingroup\$ @StefanRendevski Never change code in question. Ask another question after implementing the improvments \$\endgroup\$ – Caridorc Aug 16 '15 at 8:06
  • 1
    \$\begingroup\$ @Caridorc I meant I updated my file, not the code posted in this question. Sorry for the misunderstanding. \$\endgroup\$ – Stefan Rendevski Aug 16 '15 at 10:54
  • \$\begingroup\$ @StefanRendevski :) thanks for knowing the rules \$\endgroup\$ – Caridorc Aug 16 '15 at 10:59
  • \$\begingroup\$ I'm not a fan on the log10 approach since you'd need to be sure that floating point rounding errors won't lead to an off-by-one error. AFAIK the IEEE guaranteed for transcendental functions are relatively weak and C's guarantees might be even weaker. In addition to that, 16 digits corresponds to 53.15 bits, so you won't even be able to represent some of them exactly as double. \$\endgroup\$ – CodesInChaos Aug 16 '15 at 14:51
11
\$\begingroup\$

Avoid floating point

Actually I would advise the opposite of what @Xean said. I would completely remove all floating point from your program, including any calls to pow and log. I prefer your original loop to compute the number of digits.

The reason I don't like using floating point is that you might mysteriously get erroneous results due to roundoff errors. For example, on my computer, when I do this:

val = pow(9, 17);

I get this result, which is off by one:

16677181699666568 (actual value should be one higher)

For your program, you could either write a simple function to compute the powers of ten you need, or even hardcode the four values you need since you are only using powers 12, 13, 14, and 15.

\$\endgroup\$
  • \$\begingroup\$ You are right in the first place, but you have to know how to handle errors like this. In your example you need to use the ceil function as well. And, for Stefan Rendevski, this error is hidden by the integer division. Well, there are many other ways to count the number of digits, but, for this little program, they are to heavy. I think it is a good idea to try to avoid floating point operations (especially because of performance issues) but sometimes there are really helpful. \$\endgroup\$ – Obenland Aug 16 '15 at 11:21
  • \$\begingroup\$ There are too many problems with floats to use them whenever money or safety is involved. How do you handle the case when 0.4+0.6 isn't exactly 1? You should never write code that checks if two floats are equal, but instead write code that checks if their difference is less than some epsilon. As you calculate more floats from floats, your error term grows, at some point exceeding your epsilon. Also realize that those epsilons are hard-coded errors in your code. Replace everything with arbitrary precision integers, expressing everything in base units (1/1000 of a cent, for example). \$\endgroup\$ – IceArdor Aug 16 '15 at 12:14
6
\$\begingroup\$

I see some things that may help you improve your code.

Don't duplicate important constants

The word "INVALID" is hardcoded in four completely independent places. Better would be to either create a constant or to restructure the code so that it only appears once.

Avoid duplicating work

To count the number of digits, the code does successive divisions. Then when it verifies the checksum, it does those divisions again. Better would be make a single pass and calculate both.

Avoid floating point operations

Floating point math is great for some things, but can be computationally costly on some machines. There are also rounding and other issues (e.g. denormals, NaNs) to consider. This code doesn't need any floating point routines. All it really needs are the first and second digits of the credit card number.

Simplify your calculations

There is no need to store separate odd_sum and even_sum values. Instead, one can simply keep a running total and eliminate much complication.

Don't use printf where it isn't needed

Your code uses printf with a format string of "%s\n" in some places and with a hardcoded string "INVALID\n" in others. The code would be simpler if there was a single call instead of multiple, and if you would use puts() instead of printf.

Putting it all together

Here is an alternative that uses all of these suggestions. It does not use pow or anything else from <math.h> and does not use strcmp or anything else from <string.h> so does not have those #includes. It makes a single pass through the value and efficiently implements the checkdigit verification. Finally, each string appears only once and a card is assumed to be invalid unless otherwise successfully categorized.

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    long long int cc;

    printf("Number: ");
    cc = GetLongLong();

    int sum = 0;
    int len;
    int first = 0;
    int second = 0;
    for (len=0; cc; cc /= 10, ++len) {
        int digit = cc % 10;
        second = first;
        first = digit;
        if (len & 1) {
            digit += digit;
            if (digit > 9) {
                digit -= 9;
            }
        }
        sum += digit;
    }
    sum %= 10;
    char *bank = "INVALID";
    if (sum == 0) {
        switch(first) {
            case 3:
                if (len == 15 && (second == 4 || second == 7)) {
                    bank = "AMEX";
                }
                break;
            case 4:
                if (len == 13 || len == 16) {
                    bank = "VISA";
                }
                break;
            case 5:
                if (len == 16 && second > 0 && second < 6) {
                    bank = "MASTERCARD";
                }
                break;
        }
    }
    puts(bank);
}
\$\endgroup\$
  • \$\begingroup\$ Really nice way to compute the sum of the digits of the product! I don't really understand what does (len & 1) do, though. Wouldn't it be more concise to use len % 2 instead? \$\endgroup\$ – Stefan Rendevski Aug 16 '15 at 18:27
  • \$\begingroup\$ Odd numbers in two's complement always have a 1 as the least significant bit, which is what (len & 1) tests. You could use (len % 2) if that seems to make more sense to you. Any recent compiler will understand either and generate identical code. On this 64-bit AMD-processor Linux box using gcc, the result is a testb $1, %sil assembly language instruction. \$\endgroup\$ – Edward Aug 16 '15 at 19:29
4
\$\begingroup\$

I am wondering if there is maybe a more elegant way to do all the checking involved in my program.

Not necessarily more elegant, but some of your assumptions are incorrect.

Assumption #1: credit card numbers are long int.

While you can reduce a CC to a long int, you cannot assume that it arrives as a long int. Users will enter the number with spaces, multiple spaces, hyphens, leading and/or trailing characters etc. All of them need to be filtered out.

Assumption #2: length of the CC number determines the card type.

case 13: bank = "VISA";

I'm looking at my Visa card right now and it has 16 digits. Yes, you catch this case in the end but it's a lot simpler to do what the banks do: process the first digits. 4 -> Visa, 5-> MC etc.

if ( (credit_card / (long long int) pow(10, digits - 1) ) == 4) bank = "VISA";

try:

if( 4 == substr( credit_card, 0, 1 ) ) bank = "VISA" 

Assuming credit_card is now a string, cleansed of non-digits with a regular expression. Also avoids those nasty floating-point functions.

or more efficiently:

banknum = substr( credit_card, 0, 1 );
switch( banknum ) {
  case '4' : bank = "VISA"; break; 
  case '5' : bank = "MASTERCARD"; break; 
}

From comments:

The function 'GetLongLong()' will reprompt the user if the entered value is not a (long long) int

And that's where we hit the "bad user interface" part. It's your (the programmer's) job to sanitize the input. If the user wants to type "4521-5632-8965-7854" that's their business. Search for "SQL injection" for one of many reasons never to trust what the user types.

\$\endgroup\$
  • \$\begingroup\$ The function 'GetLongLong()' will reprompt the user if the entered value is not a (long long) int, that's why I went with it. But the cs50.h library is meant to be a helper library for the first few weeks, so I guess I should try your method. Regarding the second assumption, do you ever check for the length of the inputted number? If yes, would you do it before or after the switch statement? \$\endgroup\$ – Stefan Rendevski Aug 16 '15 at 11:02
  • \$\begingroup\$ GetLongLong() exists for a good reason. I distinctly remember not liking atoi and cin >> var, having to deal with whitespace/newline characters getting left on stdin, trying to peek/putback values, buffer the characters into a fixed-length array when I started programming. Even though this problem could be solved with string manipulation, you have to remember how limiting your toolset was when you first started out programming. \$\endgroup\$ – IceArdor Aug 16 '15 at 12:00
3
\$\begingroup\$

I find it helps to think in pseudocode/Python before writing C code because it's hard to think at the C level and see the big picture at the same time. I think the Python code below is equivalent to your algorithm.

I reorganized the part the determines the bank, so that VISA only appears once. I also replaced (credit_card / (long long int) pow(10, digits - 1) with first_digit and (credit_card / (long long int) pow(10, digits - 2) with first_two_digits.

I got a bit lost in your for loop with 6 variables, so I implemented what I read from the wikipedia page on Luhn's algorithm. My definition of "odd" versus "even" may be different from yours--rename my odd_digits and even_digits variables if our answers differ. I'm assuming the right-most digit is the check digit.

def is_luhn_valid(credit_card):
    check_digit = credit_card[-1] #last digit
    # every-other digit in reverse order, excluding check digit
    odd_digits = digits[-1::-2]
    # even_digits = [((2*d) % 10 + (2*d) // 10) for d in digits[-2::-2]]
    even_digits = [digit_sum(2*d) for d in digits]
    total = sum(odd_digits) + sum(even_digits) + check_digit
    return total % 10 == 0

def digit_sum(number, recursive=False):
    s = 0
    temp = number
    while temp > 0:
        s += temp % 10
        temp /= 10
    if recursive:
        if s < 10: return s
        else: return digit_sum(s, recursive)
    else:
        return s
        # recursive call needed if number exceeds 11 digits, since 
        # `digit_sum(999999999999) = 108`, while
        # digit_sum(999999999999, True) = 9`. However, for your credit 
        # card usage here, number will be at most 2*9, so
        # `digit_sum(2*digit)` will always be less than 10.

def is_valid_card_number(credit_card : long)
    bank = None
    credit_card = map(int, str(credit_card))
    digits = len(credit_card)
    first_digit = credit_card[0]
    first_two_digits = credit_card[0]*10 + credit_card[1]
    if digits in (13, 16) and first_digit == 4:
        bank = 'VISA'
    elif digits == 15 and first_two_digits in (34, 37):
        bank = 'AMEX'
    elif digits == 16 and 51 <= first_two_digits <= 55:
        bank = 'MASTERCARD'

    if bank is not None:
        if is_luhn_valid(credit_card):
            return bank
    return 'INVALID'

Here's the changes I'd make to your code:

  • Use descriptive variable names for any expression that takes longer than 3 seconds for me to figure out what it's doing. (such as (credit_card / (long long int) pow(10, digits - 2))). This makes your code shorter and easier to read.
  • Replace floating point pow with integer multiplication in a for-loop.
  • Rearrange bank checking code to have one section for VISA.
  • For the checksum code, for-loop over the credit card twice to make your code easier to read. Your for loop did too much to easily understand.
  • Replace the 6 variables in the for-loop section with just the variables you need. I only needed 4.
  • Move variable type declarations outside of for-loops unless they have a reason to be in there. (Feel free to disagree with me here. While it may be better to have variables defined in the scope they are used, I expect everything you need for a for-loop to be set up just before the for-loop, then make the body of the loop as simple as possible.)
  • I got confused by digit *= 2; prod_dig_sum += ...; even_sum += prod_dig_sum; This made me think you were doing a sum of the cumulative sum of the even digits. Then I saw int prod_dig_sum = 0 getting reset each time through the for-loop. Don't use += when you could have just used =.
  • You don't need 3 return statements and 3 printf statements. Multiple return statements are only needed in a function if you want to terminate early--but you're already pretty much at the bottom of the function. If I see multiple return statements at the bottom of a function, I assume that all but the last return statement are there to terminate a for loop or while loop.

And here's the C code, written using the Python code above as a reference.

int digits = 0;
long long int first_digit_divisor = 1;
for (long long int temp = credit_card; temp > 1; temp /= 10) {
    digits++;
    first_digit_divisor *= 10;
}
first_digit_divisor /= 10;
const long long int first_two_digits_divisor = first_digit_divisor / 10;

const int first_digit = credit_card / first_digit_divisor;
const int first_two_digits = credit_card / first_two_digits_divisor;

if ((digits == 13) && (first_digit == 4))
    bank = "VISA";
else if ((digits == 15) && (first_two_digits == 34 || first_two_digits == 37))
    bank = "AMEX";
else if ((digits == 16) && (51 <= first_two_digits && first_two_digits <= 55))
    bank = "MASTERCARD";
else:
    bank = "INVALID";

if (strcmp(bank, "INVALID") != 0) {
    if !is_luhn_valid(credit_card)) {
        bank = "INVALID";
    }
}
printf(bank+"\n");
return 0;

boolean is_luhn_valid(long long int credit_card) {
    const int check_digit = credit_card % 10;
    int odd_digit_sum = 0, even_digit_sum = 0, total = 0;
    long long int temp;
    int digit;
    for (temp = credit_card / 10; temp > 0; temp /= 100)
        digit = temp % 10;
        odd_digit_sum += digit;
    for (temp = credit_card / 100; temp > 0; temp /= 100)
        digit = temp % 10;
        even_digit_sum += ((2*digit) % 10) + ((2*digit) / 10);
    total = odd_digit_sum + even_digit_sum + check_digit;
    return total % 10 == 0;

Because functions are not allowed for your course, move the body of is_luhn_valid into your main code. Hopefully that's the only modification you need.

It may seem like wasted work to write your program twice (once in pseudocode and again in your language), it's a lot harder to write it once in your language and try to tweak it so that it's readable. Especially for beginning programmers, but also for senior programmers, it's difficult to simultaneously think about low level and high level details, so if you are writing low level code while you are thinking about how to solve the high-level detail but haven't planned the entire task at the high-level, your implementation suffers.

Finally, don't let the limitations of your programming language restrict how you plan on solving the task. If your language makes it difficult to do something, write a function to abstract away the complexity. Bonus points: if you're writing code and don't know if a function exists, invent a name of a function that accepts the arguments you need. Write the adapter code later so you don't lose your train of thought. Your code will also read better because you used a function that exactly met your needs, rather than trying to find a function that met most of your needs, requiring some variable type conversions, or a function name that didn't exactly describe what it was doing, or a collection of several lines of code that together perform a bigger task that deserves a name.

\$\endgroup\$
  • \$\begingroup\$ prod_dig_sum is used to get the sum of the products' digits (for example, if I multiply the digit 7 by two, I get 14, so i calculate 1 + 4, instead of summing up the products). Also, I was told that VISA can have 16 digits-long credit cards, that's why I had 2 cases for it. Unfortunately, I don't know Python so I can't use that to simplify the thought process, but I did write down the procedure I implemented both in pseudocode and English. Appreciate the explanation, thought, and I definitely agree about functions and their uses. \$\endgroup\$ – Stefan Rendevski Aug 16 '15 at 12:08
  • \$\begingroup\$ Python is essentially pseudocode. It should be fairly readable as written., except for the map(int.... That's creating a list of ints. It looks like I implemented Luhn's incorrectly, doubling the final sum instead of doubling the digits AND adding the carry. Stupid carry. Otherwise, the math would be the same doubling inside or outside the for-loop. \$\endgroup\$ – IceArdor Aug 16 '15 at 12:18

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.