Problem Set 1: Credit

Evidence of a 5-point submission

  • Compared to Cash, Credit is considerably more open-ended; 5-point solutions can vary greatly. Some 5-point solutions might make use of many functions, while others will handle the entire problem in the main function; either approach is OK (see the staff solution for solutions using both of these approaches).
  • Efficiency; ideal solutions should only pass through the digits once or twice; if the solution iterates through the card number twice, at least one of the iterations should be relatively lightweight and fast
  • Math; solution clearly expresses the idea of using division and modulo to obtain digits; division by a power of ten to knock off digits from the right, and modulo by ten to knock off digits from the left - that logic should be transparent in the solution
  • Logical; the logical flow of the solution should be extremely easy to understand

Evidence of a 4-point submission

  • Comparable to a 5-point submission but with one or two little mistakes, such as:
    • Bad scoping; ideally, variables should be defined just before they’re needed; if the student dumps a bunch of variables right at the start of their program, it’s an unnecessary strain on the reader
    • Convoluted logic; these especially apply when a student completes this assignment entirely in the main function: if the code gets indented way over to the right due to excessive if-elses, or is hard to follow since the code isn’t blocked out or broken up in any way, there’s room for improvement

Evidence of a 3-point submission

  • Makes several of the above little mistakes, or one or two bigger mistakes, such as:
    • Converts the credit card number to a string or puts it in an array, which is costly in time and space; direct manipulation of a long is preferable
    • Iterates through the credit card number way more times than is necessary
    • Uses too many variables, or uses poorly named variables, or both
    • The train of logic isn’t as concise as it should be: there should just be one if for VISA, one if for MASTERCARD, etc.; if there are multiple ways the program can output VISA, MASTERCARD, etc., the program is more convoluted than it needs to be

Evidence of a 2-point submission

  • Makes several of the bigger mistakes described in the 3-point submission entry

Evidence of a 1-point submission

  • Logic is so convoluted as to be unintelligible, or implementation does not suggest understanding of how a computer helps complete the task at hand (i.e. implementation uses excessive hard-coding of cases, or is significantly overlong)

Example Implementations (Worse vs. Better)

Printing the Answer

Worse Implementation

Notice the multiple forking paths to get to ‘Invalid’, and the overly complex conditionals.

if (count == 13)
{ 
    if (floor(card / (4 * pow(10, 12))) == 1)
    {
        printf("VISA\n");
    }
    else
    {
        printf("INVALID\n");
    }
}
else if (count == 15)
{
    n = floor(card / pow(10, 13));
    if (n == 34 || n == 37)
    {
        printf("AMEX\n");
    }
    else
    {
        printf("INVALID\n");
    }
}
else
{
    n = floor(card / pow(10, 14));
    if (n >= 51 && n <= 55)
    {
        printf("MASTERCARD\n");
    }
    else if (n >= 40 && n <= 49)
    {
        printf("VISA\n");
    }
    else
    {
        printf("INVALID\n");
    }
}

Better Implementation

Notice the relatively cleaner logic, and that there’s only one of VISA, MASTERCARD, and AMEX each:

// perform VISA check (starts with 4, is either 13 or 16 digits)
if (first_digit == 4 && (length == MIN_LENGTH || length == MAX_LENGTH))
{
    printf("VISA\n");
}

// perform MASTERCARD check (starts with 51-55, is 16 digits)
else if (first_digit == 5 && (second_digit >= 1 && second_digit <= 5) && length == MAX_LENGTH)
{
    printf("MASTERCARD\n");
}

// perform AMEX check (starts with 34 or 37, is 15 digits)
else if (first_digit == 3 && (second_digit == 4 || second_digit == 7) && length == AMEX_LENGTH)
{
    printf("AMEX\n");
}

// otherwise must not be any of these
else
{
    printf("INVALID\n");
}

Luhn

Worse Implementation

Loses time and memory performing sprintf, does two loops when one loop is possible

int luhn(long input)
{
    char st[256];
    sprintf(st, "%ld", input);

    int len = strlen(st);
    int sum = 0;

    for (int i = len - 2; i >= 0; i -= 2)
    {
        int x = st[i] - '0';
        sum += sum_of_digits(x * 2);
    }

    for (int i = len - 1; i >= 0; i -= 2)
    {
        sum += st[i] - '0';
    }

    if (sum % 10 == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

Better Implementation

From staff solution; notice clarity of math, single iteration through the digits, well-commented, manipulation of a long rather than loading into a string

// Determines if the card passes the Luhn algorithm
bool luhn(long cc, const int len)
{
    int tally = 0;

    // Iterate len number of times to cover all digits in the credit card number
    for (int i = 0; i < len; i++)
    {
        // Get the rightmost digit
        int digit = cc % 10;

        // If i is even, simply add ith digit of cc to tally
        if (i % 2 == 0)
        {
            tally += digit;
        }

        // Otherwise, do the Luhn math and add to tally
        else
        {
            digit *= 2;
            if (digit > 9)
            {
                tally += digit % 10;
                tally += digit / 10;
            }
            else
            {
                tally += digit;
            }
        }

        // Trim the rightmost digit from the cc number
        cc /= 10;
    }

    // Return true if tally is a multiple of 10
    return !(tally % 10)
}

Again, a student solution might not have a standalone block of code that’s identifiable as the Luhn function—that’s OK! If their logic is still readily comprehensible, there’s nothing wrong with that approach.