In this post, the solution for the problem set of the second lecture of CS50 is summarized.

Problem Set

mario

In a file called mario.c in a folder called mario-more, implement a program in C that recreates that pyramid, using hashes (#) for bricks, as in the below: And let’s allow the user to decide just how tall the pyramids should be by first prompting them for a positive int between, say, 1 and 8, inclusive.

   #  #
  ##  ##
 ###  ###
####  ####

Answer

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

void mario(int height);

int main(void){
    int height;
    do {
        height = get_int("height: ");
    }
    while(height < 1 || height > 8);
    mario(height);
}

void mario(int height){
    for (int i = 0; i < height; i++){
        for (int j = 0; j < height - i - 1; j++){
            printf(" ");
        }
        for (int j = 0; j < i + 1; j++){
            printf("#");
        }
        printf("  ");
        for (int j = 0; j < i + 1; j++){
            printf("#");
        }
        printf("\n");
    }
}

credit

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

So what’s the secret formula? Well, 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!

Answer

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

int checkSum(long number);
int digitCnt(long number);
void validChecker(long number);

int main(void){
    unsigned long number = get_long("card number: ");
    validChecker(number);
}

int checkSumCal(long number){
    int digit = digitCnt(number);
    int checkSum = 0;
    for (int i = 1; i <= digit; i++){
        unsigned long num = number % (long) pow(10, i);
        num = num / pow(10, i - 1);
        if (i % 2 == 1){
            checkSum += num;
        }
        else{
            num *= 2;
            if (num < 10){
                checkSum += num;
            }
            else if (num >= 10){
                checkSum += (num % 10 + num / 10);
            }
        }
    }
    return checkSum;
}

int digitCnt(long number){
    int digit = 0;
    while (number >= 1){
        number /= 10;
        digit++;
    }
    return digit;
}

void validChecker(long number){
    int checkSum = checkSumCal(number);
    int digit = digitCnt(number);
    if (checkSum % 10 != 0){
        printf("INVALID\n");
        return;
    }
    else{
        if (digit == 13 || digit == 16){
            if (number / (long) pow(10, digit - 1) == 4){
                printf("VISA\n");
                return;
            }
            else{
                if (digit == 16){
                    if (number / (long) pow(10, 14) >= 51 && number / (long) pow(10, 14) <= 55){
                        printf("MASTERCARD\n");
                    }
                    else{
                        printf("INVALID\n");
                    }
                }
            }
        }
        else if (digit == 15){
            if (number / (long) pow(10, 13) == 34 || number / (long) pow(10, 13) == 37){
                printf("AMEX\n");
            }
            else{
                printf("INVALID\n");
            }
        }
        else{
            printf("INVALID\n");
        }
    }
}