CS50 PSet 1: Credit

A guide to the ‘credit’ problem in CS50 Week 1.

Goal: To write a program in C that can validate credit card numbers using the Luhn Algorithm, and return whether a valid card number is Mastercard, Visa or Amex. The program must ask for the number and only accept numeric inputs, devoid of hyphens or other punctuation as per the example below.

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

If the card number fails the checks, the script should return INVALID.

$ ./credit
Number: 6176292929
INVALID

Disclaimer: while there are more efficient ways to do this, my solution only utilises knowledge we have been given in CS50 Week 1, as is intended.

First, we ask for the user to input the card number, using the get_long() function from the cs50 library. The get_long() function will only accept numeric inputs so will continue to ask until it receives one.

We can then determine the length of the number by continuously dividing by 10, effectively knocking a digit off the end each time through the while loop until there are no digits left.

    // Get card number
    long n = get_long("Number: ");
    // Count length
    int i = 0;
    long cc = n;
    while (cc > 0)
    {
        cc = cc / 10;
        i++;
    }

Now, for the purposes of this problem the length can only be 13, 15 or 16 so we can check that first. If the length is invalid we return 0 to end the program.

    // Check if length is valid
    if (i != 13 && i != 15 && i != 16)
    {
        printf("INVALID\n");
        return 0;
    }

If the number passed the length check, the next stage is to calculate the checksum. This is done 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.

So effectively we have 2 separate sums we need to calculate here before adding them at the end to get the total. I have defined these as sum1 and sum2, as well as replicating the card number in x since we will be dividing it up.

The trick to doing this is clever use of the modulus and division operators. Recall that the modulus, or %, operator returns the remainder of a division. This means that modulus of 10 on a number will return the last digit. To knock off the last digit for the next operation we divide by 10 as before.

To calculate sum1 (step 2 in the above description) we simply add the modulus of 10 each time.

Calculating sum2 (step 1) requires a bit more work. Again we find the modulus of 10, but this must then be doubled, and the digits of this product added together. Since we know this product will only have a maximum of 2 digits, we can again use the modulus and division operators to extract these digits and add them to sum2.

Once we have been through all the digits of the card number, the loop ends and we calculate our total by adding sum1 and sum2 together.

    // Calculate checksum
    int sum1 = 0;
    int sum2 = 0;
    long x = n;
    int total = 0;
    int mod1;
    int mod2;
    int d1;
    int d2;
    do
    {
        // Remove last digit and add to sum1
        mod1 = x % 10;
        x = x / 10;
        sum1 = sum1 + mod1;
        // Remove second last digit
        mod2 = x % 10;
        x = x / 10;
        // Double second last digit and add digits to sum2
        mod2 = mod2 * 2;
        d1 = mod2 % 10;
        d2 = mod2 / 10;
        sum2 = sum2 + d1 + d2;
    }
    while (x > 0);
    total = sum1 + sum2;

The check can now be ran on the total to see if the checksum passes the Luhn Algorithm.

    // Next check Luhn Algorithm
    if (total % 10 != 0)
    {
        printf("INVALID\n");
        return 0;
    }

The final check to perform if the number has passed so far is on the starting digits. This will also determine whether the card is Mastercard, Visa or Amex.

We start by finding the first 2 digits, using the same method as previously to knock off end digits until 2 remain.

    // Get starting digits
    long start = n;
    do
    {
        start = start / 10;
    }
    while (start > 100);

Recall that if it is Mastercard the number will start with 51, 52, 53, 54 or 55 so we check that first. Hopefully by now you will be comfortable with the division and modulus operations.

    // Next check starting digits for card type
    if ((start / 10 == 5) && (0 < start % 10 && start % 10 < 6))
    {
        printf("MASTERCARD\n");
    }

Next check for Amex (34 or 37).

    else if ((start / 10 == 3) && (start % 10 == 4 || start % 10 == 7))
    {
        printf("AMEX\n");
    }

And finally check if it is Visa (first digit must be 4).

    else if (start / 10 == 4)
    {
        printf("VISA\n");
    }

If all of those checks fail, we return invalid once again.

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

And that’s credit. A lot more verbose than the Mario problem but excellent practice using basic arithmetic operators.