CS50x Credit

From problem set 1

Photo by Ryan Born on Unsplash

Credit is the point where things start to get complicated. We need to work with a lot of big numbers and not only do mathematics with then but learn how to travel trough the number to access specific digits in its composition. We learn a little about the cryptography behind each card number and how to use it to check if the card is valid and from which provider it comes.

As always we begin preparing our directory. Assuming you already have the pset1 directory, let’s type on our terminal:

~/ $ cd pset1
~/pset1/ $ mkdir credit
~/pset1/ $ cd credit
~/pset1/credit/ $ touch credit.c
~/pset1/credit/ $ open credit.c

The expected behavior of our program should be like:

$ ./credit
Number: 4003-6000-0000-0014
Number: foo
Number: 4003600000000014
VISA

Or in case of an invalid card number:

$ ./credit
Number: 6176292929
INVALID

To achieve that, we’ll need to use something called Luhn’s Algorithm, more about that further. Also, we need to think of how we’re going to check the card for its provider. Luckily, the problem explained that to us, it takes the first digits and the card number’s length, we just need to design an algorithm to do the work. It’s a good thing to write a pseudocode for the steps we need to take.

// Prompt user for a card number to validate. Store it.
// Validate the card through Luhn's Algorithm.
// Check for card lenght and starting digits.
// Print provider or invalid.

Right now I can already see some functions we’re gonna need. Let’s build the base of our code with the headers and what we expect main will look like.

#include <stdio.h>
#include <cs50.h>
#include <math.h>
bool luhnCheck(long cardNumber);
int getCardLen(long cardNumber);
void getCardProv(long cardNumber);
int main(void)
{
    long cardNumber = get_long_long("Card Number to Validate: ");
    if (luhnCheck(cardNumber) == true)
    {
        getCardProv(cardNumber);
    }
    else
    {
        printf("INVALID\n");
    }
}

There’s no need to create a function for get_long_long this time as we don’t have to run any check at that step (CS50 already does all that we need). Our getCardProv only runs if the card number is considered valid by luhnCheck, otherwise it returns INVALID immediately. The getCardLen is going to run inside getCardProv, that's why you don’t see it in main. We’re storing cardNumber as a long because it’s gonna be a looooong number.

NOTE: we have a bool function without the stdbool header. That’s because CS50 library handles that too. MAN, those training wheels…

Luhn’s Algorithm

Directly from the problem set explanation!

Most cards use an algorithm invented by Hans Peter Luhn of IBM. According to Luhn’s algorithm, you can determine if a credit card number is (syntactically) valid as follows:

1. Multiply every other digit by 2, starting with the number’s second-to-last digit, and then add those products’ digits together.
2. Add the sum to the sum of the digits that weren’t multiplied by 2.
3. If the total’s last digit is 0 (or, put more formally, if the total modulo 10 is congruent to 0), the number is valid!

That’s kind of confusing, so let’s try an example with David’s Visa: 4003600000000014.

For the sake of discussion, let’s first bold every other digit, starting with the number’s second-to-last digit:

4003600000000014

Okay, let’s multiply each of the bold digits by 2:

1•2 + 0•2 + 0•2 + 0•2 + 0•2 + 6•2 + 0•2 + 4•2

That gives us:

2 + 0 + 0 + 0 + 0 + 12 + 0 + 8

Now let’s add those products’ digits (i.e., not the products themselves) together:

2 + 0 + 0 + 0 + 0 + 1 + 2 + 0 + 8 = 13

Now let’s add that sum (13) to the sum of the digits that weren’t (bold) multiplied by 2 (starting from the end):

13 + 4 + 0 + 0 + 0 + 0 + 0 + 3 + 0 = 20

Yup, the last digit in that sum (20) is a 0, so David’s card is legit!

Seems easier by hand than it’s in a week 1 coder’s head… and yeah, that’s completely true. Take a look at our Luhn’s Algorithm code.

bool luhnCheck(long cardNumber)
{
    int checkSum = 0;
    long tmp = cardNumber;
    
    for (int pos = 0; tmp > 0; pos++)
    {
        if (pos % 2 == 0)
        {
            checkSum += tmp % 10;
            tmp /= 10;
        }
        else
        {
            int odd = (tmp % 10) * 2;
            checkSum += (odd / 10 + odd% 10);
            tmp /= 10;
        }
    }
    return (checkSum % 10) == 0;
}

We first initialized some local variables to use inside our loop. We copy the card number to another variable called tmp so we can mess with it without worrying about the complete number prompted by the user.

Our loop works as follow: pos (short for position) keeps track of which digit from the card we are accessing. Then, if the POSITION of that digit is even (i.e has modulo = 0) we need only to add it to the sum. The modulo operator is %, thus tmp % 10 = last number of the card. Finally, we overwrite the card number by itself divided by ten (tmp /= 10). As tmp is an integer, it ignores all numbers after the “.”, so 123 divided by 10 equals “12" and not “12.3”. In practice, we just excluded from the card the number we added to the sum.

Else, if our position is odd, remember that we have to multiply the digit by two before adding it to the sum. More exactly, we need to make sure that after multiplying, if the number exceeds 1 single digit we need to add each digit and not the total product of the multiplication. E.g. digit is 6, times 2, it’s now 12. We add 1 and then 2, totalizing 3 and not 12. The code line which fixes this issue uses the same principle based on integers we used to exclude the last card number. We first store the product of our digit in an integer variable we called odd, then to make sure we add each digit, instead of simple adding odd to sum, we do the following: (odd / 10) + (odd % 10). Some examples to make it clearer:

odd = 12
(12/10)+(12%10)
   1   +   2    =  3
odd = 4
(4/10) + (4%10)
   0       4    =  4

This happens because when we assign 4/10 (obviously 0.4) to and integer it doesn’t even look beyond the “.” and gets only the 0. Same with 1.2, it gets only 1. The modulo operator is the exact opposite, it only looks after the “.”, at the remainder of the division.

Finally, don’t forget to exclude the number we used from the card using tmp/=10, and then at the end of the function we return true if the remainder of checkSum is 0 and false otherwise. We do it in one simple line as you saw: return (checkSum % 10) == 0;

From here we can start testing our code to make sure it’s working. First add to our main the following temporary line inside the luhnCheck block on main:

printf("VALID\n");

Next prepare the skeletons for our other functions:

int getCardLen(long cardNumber)
{
    return false;
}
void getCardProv(long cardNumber)
{
}

Integer functions need a return otherwise our code won’t compile, let’s leave it as false meanwhile.

OK, testing time. Grab some card numbers from here and run your code typing ./credit on the terminal. It should look like this:

~/pset1/credit/ $ ./credit
Card Number to Validate: 4003600000000014
VALID
~/pset1/credit/ $ ./credit
Card Number to Validate: 378282246310005
VALID
~/pset1/credit/ $ ./credit
Card Number to Validate: 6011111111111117
INVALID
~/pset1/credit/ $ ./credit
Card Number to Validate: 6176292929
INVALID

That’s just the first testing layer for our card numbers. Remove the temporary printf code so we can proceed to our next function. Getting the card number’s length.

int getCardLen(long cardNumber)
{
    int len = log10(cardNumber);
    return len + 1;
}

I know what you’re thinking! WHY did I skip all those math classes? I ask myself the same buddy, don’t worry. It’s simple, log10 is a function from the math library. Explaining it in a manner that may get me killed by a mathematician, this function counts how many times the card number can be divided by 10 before it reaches a single digit. So if the card has 15 digits, log10 will return 14. We take care of this last digit by adding 1 to length before returning.

NEEEEXT PLEASE!!!

We now need to discover the company that provides the card. We can do that by characteristics of the card number, as explained in the problem set:

American Express uses 15-digit numbers, starting with 34 or 37;

MasterCard uses 16-digit numbers, starting from 51 to 55;

Visa uses 13- and 16-digit numbers, starting with 4;

The problems asks that we build a code to return the provider name. To do that, first I’m starting two variable inside my getCardProv function:

int len = getCardLen(cardNumber);
int prov;

To store the card number length: len. And prov is initialized but empty, we’re using it shortly. First we tackle the two providers that have the same card number len inside the same block, that is going to save us some space:

if (len == 16)   
    {
        prov = (cardNumber / 1e14);
        if (prov >= 51 && prov <= 55)
        {
            printf("MASTERCARD\n");
        }
        else if (prov >= 40 && prov <= 49)
        {
            printf("VISA\n");
        }
        else
        {
            printf("INVALID\n");
        }
    }

If our card number length equals 16, our code will divide it by a huge number so we get the first two digits. I used scientific notation for that, 1e14 is the same as 1*10¹⁴. So as you can see, we’re dividing the card number by 1,000,000,000,000, and prov is a integer so we get no remainder. Being prov any number between 51 and 55, inclusive, the function prints MASTERCARD. On the other hand, if prov is somewhere between 40 and 49, it prints VISA. Remember that the problem specified that VISAS’ cards begin with 4, but never said about the second number, so we may assume it’s anything from 0 to 9. Else, if none of these conditions met for a 16 digits cards, it must be INVALID.

The same principles were applied on the following blocks:

if (len == 13)
    {
        prov = (cardNumber / 1e12);
        if (prov == 4)
        {
            printf("VISA\n");
        }
        else
        {
            printf("INVALID\n");
        }
    }
    
    if (len == 15)
    {
        prov = (cardNumber / 1e13);
        if (prov == 34 || prov == 37)
        {
            printf("AMEX\n");
        }
        else
        {
            printf("INVALID\n");
        }
    }

Note that we hardcoded our scientific notation to match the length of each card number.

And now, to finish this function we must deal with any other length that’s not used by the given providers.

else if (len <= 12 || len >= 17 || len == 14)
{
    printf("INVALID\n");
}

This will return INVALID for any other length. Make sure to add each of these blocks one after the other, none of them is nested.

Now that our code looks complete, we can rerun some of the tests from the beginning before passing it to the staff checks. I’m not adding it here but moving straight to showing you the staff checks results and the complete code with comments.

Results generated by style50 v2.7.4
Looks good!
Results for cs50/problems/2020/x/credit generated by check50 v3.1.2
:) credit.c exists
:) credit.c compiles
:) identifies 378282246310005 as AMEX
:) identifies 371449635398431 as AMEX
:) identifies 5555555555554444 as MASTERCARD
:) identifies 5105105105105100 as MASTERCARD
:) identifies 4111111111111111 as VISA
:) identifies 4012888888881881 as VISA
:) identifies 4222222222222 as VISA
:) identifies 1234567890 as INVALID
:) identifies 369421438430814 as INVALID
:) identifies 4062901840 as INVALID
:) identifies 5673598276138003 as INVALID
:) identifies 4111111111111113 as INVALID
:) identifies 4222222222223 as INVALID