currency permutation

/* Copyright (c) 2014  Niklas Rosenstein
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE. */

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>

/* Parses a string and converts it to an integral number with base 10.
 * Any characters after the first number is ignored.
 *
 * @param   c   A pointer to the string.
 * @param  res  A pointer to the memory that will be filled with the
 *              resulting value.
 * @return true if the string could be converted, false if its contents
 *         can not be interpreted as an integral number with base 10. */
bool parse_int(const char* c, int* res) {
    if (!c || !res)
        return false;

    char mul = 1;
    switch (*c) {
        case '-':
            mul = -1;
        case '+':
            c++;
            break;
    }

    *res = 0;
    size_t count = 0;
    while (*c != 0) {
        if (*c < '0' || *c > '9')
            break;

        *res = (*res * 10) + (*c - '0');
        c++;
        count++;
    }

    *res *= mul;
    return count > 0;
}

/* Datastructure that contains the set of available coin values and the
 * value for which the number of permutations is searched for. */
typedef struct coindef {
    size_t n;
    const int* values;
    int max;
} coindef_t;

/* Count the numnber of permutations that are possible with the
 * specified variation of coins. The coin values must be sorted in
 * ascending order. */
int count_permutations(int sum, int start, const coindef_t* coindef) {
    if (sum > coindef->max)
        return 0;
    else if (sum == coindef->max)
        return 1;

    int result = 0;
    for (int i=start; i < coindef->n; i++) {
        result += count_permutations(sum + coindef->values[i], i, coindef);
    }
    return result;
}


int usage() {
    printf("USAGE: max\n");
    return EINVAL;
}

static const int coin_values[] = {1, 2, 5, 10, 20, 50, 100, 200};

int main(int argc, char** argv) {
    if (argc != 2)
        return usage();

    coindef_t coindef;
    coindef.n = 8;

    // Read the first argument (which is coin max number) from the
    // command-line.
    if (!parse_int(argv[1], &coindef.max)) {
        usage();
        printf("max: must be a number.\n");
        return EINVAL;
    }

    coindef.values = coin_values;

    // Compute the number of permuations.
    printf("%d permutations are possible.\n", count_permutations(0, 0, &coindef));
    return 0;
}