CS50, Personal Development

CS50x - Problem Set 1 - Credit.

credit cards and checksums

Published September 16th, 2024

Problem to solve

A credit (or debit) card, of course, is a plastic card with which you can pay for goods and services. Printed on that card is a number that’s also stored in a database somewhere, so that when your card is used to buy something, the creditor knows whom to bill. There are a lot of people with credit cards in this world, so those numbers are pretty long: American Express uses 15-digit numbers, MasterCard uses 16-digit numbers, and Visa uses 13- and 16-digit numbers. And those are decimal numbers (0 through 9), not binary, which means, for instance, that American Express could print as many as 10^15 = 1,000,000,000,000,000 unique cards! (That’s, um, a quadrillion.)

Actually, that’s a bit of an exaggeration, because credit card numbers actually have some structure to them. All American Express numbers start with 34 or 37; most MasterCard numbers start with 51, 52, 53, 54, or 55 (they also have some other potential starting numbers which we won’t concern ourselves with for this problem); and all Visa numbers start with 4. But credit card numbers also have a “checksum” built into them, a mathematical relationship between at least one number and others. That checksum enables computers (or humans who like math) to detect typos (e.g., transpositions), if not fraudulent numbers, without having to query a database, which can be slow. Of course, a dishonest mathematician could certainly craft a fake number that nonetheless respects the mathematical constraint, so a database lookup is still necessary for more rigorous checks.

In a file called credit.c in a folder called credit, implement a program in C that checks the validity of a given credit card number.

Luhn's Algorithm

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:

Multiply every other digit by 2, starting with the number’s second-to-last digit, and then add those products’ digits together.
Add the sum to the sum of the digits that weren’t multiplied by 2.
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!

Example: 4 0 0 3 6 0 0 0 0 0 0 0 0 0 1 4

Highlight every other digit, starting with the second-to-last digit:
4 0 0 3 6 0 0 0 0 0 0 0 0 0 1 4

Multiply every other digit by 2, and add the products' digits together (in the example below, 6*2 = 12 = 1 + 2):
1*2 + 0*2 + 0*2 + 0*2 + 0*2 + 6*2 + 0*2 + 4*2

That becomes:
2 + 0 + 0 + 0 + 0 + 1 + 2 + 0 + 8 = 13
Now add the remaining digits:
13 + 4 + 0 + 0 + 0 + 0 + 0 + 3 + 0 = 20
The last digit of 20 is 0, so the number passes the checksum.

Solving the problem

Let's figure out what exactly I need to do. Given a variable size number, I need to count the amount of digits so I know how many times to loop through the number. Then I need to loop through each digit, multiplying every other one by 2, and add everything together. Finally, I need to check the first 1 or 2 digits as well as the total number of digits to see if it's AMEX, VISA, or MASTERCARD.

When I was solving this, I broke the process into 3 separate functions: count_digits( ), checksum( ), and check_provider( ).

Main function

I need to work on my pseudocode. I'm not great at starting with specific pseudocode, so let's practice here:

Prompt user for number
Count the amount of digits in the number:
```
    . . .
```
Perform checksum:
```
    . . .
```

    If checksum is true, check the provider

        . . .

```
    Else print INVALID
```

Here's the code:


            int main(void)

            {

                // Prompt user for credit card number
                long number = get_long("Number: ");


                // Count digits
                int digits = count_digits(number);


                // Perform checksum, check provider if true
                if (checksum(number, digits))
                {
                    printf("%s\n", check_provider(number, digits));
                }
                else
                    {
                            printf("INVALID\n");
                            }
            }

int count_digits(long number)

To count the digits, I need to start a count, then use a while loop to keep dividing the number by 10 (thereby removing the last digit every time) until it hits 0.

Let's put that into pseudocode:

Start a count
While the number is greater than 0:
```
    Divide number by 10
```
```
    Add 1 to count
```
Return count of the digits

And the code:


            int count_digits(long number)

            {

                // Count the number "c" of digits
                    int c = 0;
                        while (number > 0)
                            {
                                    number /= 10;
                                        c++;
                                        }
                                            return c;
            }

bool checsum(long number, int digits)

This one is a bit trickier, we need to multiply every other digit starting at the last one. Let me put it into pseudocode:

Start an empty array to store the digits
Start a sum at 0
Counting backwards, go through each digit one at a time

    if the digit is an even index, multiply it by 2

        if the product is larger than 10, add the digits separately

```
        else add the product to the sum
```
```
    else add digit to sum
```
if last digit of sum is 0, return true
else return false

Now, to do this, I'll be taking advantage of % 10 and / 10 with the base-10 system. Modulo 10 gives me the last digit of a number, and dividing by 10 removes the last digit.

Here's the code:


            bool checksum(long number, int digits)

        {

                // Create an array to manipulate each digits
                int array[digits];



                // Start a sum variable
                int sum = 0;
                for (int i = digits - 1; i >= 0; i--)
                {
                        if ((digits - i) % 2 == 0)
                        {
                                array[i] = (number % 10) * 2;
                                if (array[i] / 10 > 0)
                                {
                                        array[i] = (array[i] % 10) + (array[i] / 10);
                                    }
                                sum += array[i];
                            }
                        else
                        {
                                array[i] = number % 10;
                                sum += array[i];
                            }
                        number /= 10;
                    }
                if (sum % 10 == 0)
                {
                        return true;
                    }
                else
                {
                        return false;
            }
        }

This one's quite a bit more complicated, so let me explain a couple lines:

In the for loop, I initialize i at digits - 1, so I can access the digits in reverse order. I realize now that this is kind of unnecessary, I just need to flip the if statement to be (digits - i) % 2 != 0 to multiply array[1], array[3], etc. by 2. But, this was how my brain made sense of it when writing the program, and either way works (Which is one of the lessons I learned, that there are multiple ways to solve every problem).
We're targeting the even index numbers to multiply by 2 with an if statement. If that's the case, then I'm storing the digit * 2 in array[i]
If the digit * 2 is greater than 10, then the number in the array becomes the (product / 10 - or the first digit) + (product % 10 - or the second digit).
Then I add the product to the sum. All other digits are added to the sum as is.
The last check is just if the last digit of the total sum is 0.

string check_provider(long number, int digits)

Last function, here's the pseudocode:

Get first digit
Get second digit
Combine first and second to get first 2 digits
If first digit is 4 AND total digits are 13 OR 16, print VISA
Else if first digits are 34 OR 37 AND total digits are 15, print AMEX
Else if first digits are 51-55 AND total digits are 16, print MASTERCARD
Else print INVALID

Here's the code:


        string check_provider(long number, int digits)

{

        // Get first digit
        int a = number / (long) pow(10, digits - 1);


        // Get second digit
        int b = (number / (long) pow(10, digits - 2)) % 10;


        // Concatenate first and second digit by casting as strings
        char str_a[2], str_b[2], str_c[2];
        sprintf(str_a, "%i", a);
        sprintf(str_b, "%i", b);
        sprintf(str_c, "%s%s", str_a, str_b);
        int c = atoi(str_c);


        // Check which provider it is
        if (a == 4 && (digits == 13 || digits == 16))
        {
                return "VISA";
            }
        else if ((c == 34 || c == 37) && digits == 15)
        {
                return "AMEX";
            }
        else if ((c == 51 || c == 52 || c == 53 || c == 54 || c == 55) && digits == 16)
        {
                return "MASTERCARD";
            }
        else
        {
                return "INVALID";
    }
}

Here, to get the first and second digits, I'm dividing the number by 10^{digits - 1} and 10^{digits - 2} respectively. Then to get the first two together as a separate integer (so I can use == comparisons), first I needed to cast them as strings, then combine the two strings into a third placeholder, and finally use the atoi( ) function to convert the string into an integer. From there, the if and else if statements are very straightforward.

And there you have it, my credit program works. After reviewing it and writting this all out, I can see a few places where I can simplify the code a little bit, making it easier to read and more logical, which I think is a really good thing, since it shows I'm improving my programming skills.

CS50x - Problem Set 1 - Credit.

credit cards and checksums

Problem to solve

Luhn's Algorithm

Solving the problem

Main function

int count_digits(long number)

bool checsum(long number, int digits)

string check_provider(long number, int digits)

Other Posts.