123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143 |
- #define _GNU_SOURCE
- #define MAX_STR_LEN 2048
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include <errno.h>
- #include <string.h>
- #include <igraph/igraph.h>
- #define max(a,b) ({ \
- __typeof__ (a) _a = (a); \
- __typeof__ (b) _b = (b); \
- _a > _b ? _a : _b; \
- })
- void usage(const char *progname, FILE *os) {
- fprintf(os, "Usage: %s <TOTAL> <DENOMINATION> ...\n", progname);
- }
- int cmp_double(const void *a, const void *b) {
- return (*(double*)a > *(double*)b) - (*(double*)a < *(double*)b);
- }
- double parse_arg(const char *a) {
- char *check_ptr;
- errno = 0;
- double val = strtod(a, &check_ptr);
- int e = errno;
- if(e) {
- fprintf(stderr, "Error %s: %s\n", strerrorname_np(e), strerror(e));
- exit(1);
- }
- if(check_ptr == a) {
- fprintf(stderr, "Error: '%s' not parsed as numeric.\n", check_ptr);
- exit(1);
- }
- if(val < 0.0) {
- fprintf(stderr, "Error: Negative input detected\n");
- exit(1);
- }
- if(check_ptr[0] != '\0') {
- fprintf(stderr, "Warning: Discarding non-numeric parts '%s' of '%s'\n", check_ptr, a);
- }
- return val;
- }
- void partitions(char *prefix, const double total, const double *denominations, const int ndenoms) {
- if(strnlen(prefix, MAX_STR_LEN) >= MAX_STR_LEN-1) {
- printf("WARNING: string of results is too long, truncation may be occurring.\n");
- }
- if(cmp_double(&total, &denominations[0]) < 0) {
- // We assume the denominations were pre-processed into sorted & unique order, so if the total is smaller than the smallest, there is no more partitioning to do.
- printf("%s\n", prefix);
- memset(prefix, '\0', MAX_STR_LEN);
- return;
- }
- // There are two things to do: assign a multiple of the biggest denomination to the total space, and recursively calculate what smaller denominations can go in the remaining space.
- int biggest_denom = 0;
- while(cmp_double(&total, &denominations[biggest_denom]) > 0 && biggest_denom < ndenoms) {
- ++biggest_denom;
- }
- // The previous check always goes one step too far, so pull back.
- if(biggest_denom > 0) {
- --biggest_denom;
- }
- int times = (int)floor(total/denominations[biggest_denom]);
- //printf("\nProcessing total = %f, biggest denomination = %f, number of denominations = %d. Current prefix = '%s'\n", total, denominations[biggest_denom], ndenoms, prefix);
- size_t prefix_len = strnlen(prefix, MAX_STR_LEN);
- if(ndenoms == 1) {
- // If there is only one denomination available, greedily fill the available space
- for(int p = 0; p < times; ++p) {
- char buf[MAX_STR_LEN];
- memset(buf, '\0', MAX_STR_LEN);
- strfromd(buf, MAX_STR_LEN, "%f", denominations[biggest_denom]);
- if(prefix_len > 0 || p > 0) {
- strcat(prefix, " ");
- }
- strncat(prefix, buf, 32);
- }
- printf("%s\n", prefix);
- memset(prefix, '\0', MAX_STR_LEN);
- } else if(ndenoms > 1) {
- for(int p_outer = times; p_outer >= 0; --p_outer) {
- char buf_outer[MAX_STR_LEN];
- memset(buf_outer, '\0', MAX_STR_LEN);
- strncpy(buf_outer, prefix, MAX_STR_LEN);
- for(int p_inner = 0; p_inner < p_outer; ++p_inner) {
- char buf_inner[MAX_STR_LEN];
- memset(buf_inner, '\0', MAX_STR_LEN);
- strfromd(buf_inner, MAX_STR_LEN, "%f", denominations[biggest_denom]);
- if(prefix_len > 0 || p_inner > 0) {
- strcat(buf_outer, " ");
- }
- strncat(buf_outer, buf_inner, 32);
- }
- partitions(buf_outer, total - (double)p_outer*denominations[biggest_denom], denominations, ndenoms-1);
- }
- }
- }
- int main(int argc, char **argv) {
- if(argc < 3) {
- usage(argv[0], stderr);
- exit(1);
- }
- double total = parse_arg(argv[1]);
- double *denominations = (double *)malloc((argc-2)*sizeof(double));
- if(denominations == NULL) {
- fprintf(stderr, "Error allocating memory for denominations\n");
- exit(1);
- }
- unsigned int argnum = 2;
- while(argnum < argc) {
- denominations[argnum-2] = parse_arg(argv[argnum]);
- ++argnum;
- }
- int ndenoms = 1;
- if(argc > 3) {
- qsort(denominations, argc-2, sizeof(double), cmp_double);
- // overwrite dups
- int d = 1;
- while(d < argc-2) {
- while(denominations[d] == denominations[d-1] && ++d < argc-2);
- if(d >= argc-2) {
- break;
- }
- ++ndenoms;
- denominations[ndenoms-1] = denominations[d];
- ++d;
- }
- }
- char prefix[MAX_STR_LEN];
- memset(prefix, '\0', MAX_STR_LEN);
- partitions(prefix, total, denominations, ndenoms);
- if(denominations != NULL) {
- free(denominations);
- }
- return 0;
- }
|