A program to represent a coin amount using the smallest number of coins

Question

Recently, I was learning about greedy algorithms. One example that was given was an algorithm for exchanging a given money amount using the smallest number of coins. After the lecture, I wrote a C program implementing this:

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>

static int compareDenominations(const void *a, const void *b) {
    return (*((int*) b) - *((int*) a));
}

int main(int argc, char *argv[]) {
    long amount;
    int count;
    long *denominations;
    if (argc > 2) {
        errno = 0;
        amount = strtol(argv[1], NULL, 10);
        if (errno || amount <= 0) {
            puts("The coin amount is either negative, zero, or too big.");
            return EXIT_FAILURE;
        }
        count = argc - 2;
        if (count == 0) {
            puts("Please input at least one coin denomination.");
            return EXIT_FAILURE;
        }
        denominations = malloc(sizeof(*denominations) * count);
        if (denominations == NULL) {
            puts("Insufficient memory.");
            return EXIT_FAILURE;
        }
        int i;
        for (i = 0; i < count; i++) {
            errno = 0;
            denominations[i] = strtol(argv[i + 2], NULL, 10);
            if (errno || denominations[i] <= 0) {
                puts("A denomination amount is either negative, zero, or too big.");
                return EXIT_FAILURE;
            } else {
                int j;
                for (j = 0; j < i; j++) {
                    if (denominations[j] == denominations[i]) {
                        fprintf(stderr, "%ld is a duplicate coin denomination.\n", denominations[j]);
                        return EXIT_FAILURE;
                    }                   
                }
            }
        }
    } else {
        puts("Please enter a coin amount followed by a non-zero number of unique denominations, all separated by spaces.");
        return EXIT_FAILURE;
    }
    heapsort(denominations, count, sizeof(*denominations), compareDenominations);
    printf("Amount: %ld | Denominations: [ ", amount);
    int i;
    for (i = 0; i < count; i++) {
        printf("%ld ", denominations[i]);
    }
    puts("]");
    int denominationCount = 0;
    for (i = 0; i < count; i++) {
        denominationCount = 0;
        while (amount >= denominations[i]) {
            amount -= denominations[i];
            denominationCount++;
        }
        denominations[i] = denominationCount;
    }
    if (amount) {
        puts("The coin amount could not be represented using the given denominations.");
        return EXIT_FAILURE;
    }
    printf("Counts: [ ");
    for (i = 0; i < count; i++) {
        printf("%ld ", denominations[i]);
    }
    puts("]");
    return EXIT_SUCCESS;
}

Because my program can accept arbitrary inputs, this greedy algorithm may not always output the most optimal solution, but I am still interested in the quality of my implementation.

Answer 1

• Don't invent error messages. If strtol sets errno, use perror() to print a precise reason for a failure.

• Flat is better than nested. I recommend to handle argc < 2 at the beginning, to remove one level of indentations of the main algorithm. Along the same line, there is no need to else once if branch does return.

• Testing for duplicated denomination is easier after they are sorted.

• while (amount >= denominations[i]) loop is a long way to say

  denominationCount = amount / denomination[i];
  amount %= denomination[i];
  

• You may want to break the for (i = 0; i < count; i++) early, as soon as amount reaches 0.

• Qudos for sizeof(*denominations).

• The algorithm may fail to find a solution.

Answer 2

I understand that your focus might be on the implementation of the algorithm, however, I'm going to provide some feedback on code quality from things I've learned by reading Clean Code. I find it difficult to read and understand what's going on without looking carefully, which is an immediate smell.

main

Everything is happening in main and it's way too long. Clean Code has this to say:

"The flow of control is easy to follow. The main function builds the objects necessary for the system, then passes them to the application, which simply uses them." (Martin, 155)

• main should be short and simply call setup methods and pass them to run the application.

Functions

• The purpose of your program is to execute a greedy algorithm, right? At minimum this should be contained in a function with a descriptive name that handles the core of this logic - not in main.
• Functions should be small and do one thing. To refactor main, think about the various responsibilities going on and work on splitting them out to functions; a few examples: usage validation, the core algorithm logic, printing.

Usage

It's not immediately clear how to run the program - one has to examine the code to determine acceptable inputs for the usage.

• This should be documented in at the top as a comment and/or output by default, ideally by defining a function like print_usage. Common conventions exist for this - see here. Also note that someone else already pointed out that puts("Please input at least one coin denomination.") is confusing because it seems to imply stdin rather than argv.

Misc

• Clean Code introduces the Newspaper Metaphor which essentially says that code should read like a newspaper, top to bottom in order of increasing detail and order of execution flow. It follows then that main should be before compareDenominations.
• Consider adding some newlines between concepts to improve readabliity. Clean Code mentions Vertical Openness Between Concepts:

  Nearly all code is read left to right and top to bottom. Each line represents an expression or a clause, and each group of lines represents a complete thought. Those thoughts should be separated from each other with blank lines. (Martin, 78)

• Use descriptive names. int count is too vague. Count of what? Descriptive, accurate naming is one of the key factors in writing readable code. I'd even argue that amount and denominations could be better. What specifically are they intended to represent?
• You seem to have mixed styles of defining variables at the beginning of function (old C convention) along with defining immediately before usage in some cases. This makes it a bit confusing when you look and see a new variable (int denominationCount = 0;). It's generally best to stay consistent. This is also compounded by the fact that main is so long.

Answer 3

Since you have placed the declaration int i after a statement (which is only allowed in C99 and later), you can do it correctly by writing for (int i = …, which makes sure you don't accidentally use i outside the loop.

Error messages do not belong to stdout, they should be written to stderr instead.

The Please enter is misleading, since it refers to argv instead of stdin.

Each call to malloc must have a corresponding call to free, to prevent memory leaks. In this small program it may not matter, but in all functions other than main it is mandatory.