Monezi - Lab10

/*
 * DONE!
 */

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

#define NEWLINE puts("");

void *ec_malloc(unsigned long size);
void *ec_realloc(void *ptr, unsigned long size);
void cleanup(unsigned int, ...);

#define mem_arr(ptr, size, type) ptr = (type *) ec_malloc(size * sizeof(type))

/* Read array. */
void readarr(int [], unsigned long);

/* Print array. */
void printarr(int [], unsigned long);


#define arrswap(arr, pos_a, pos_b, type) { \
    type aux = arr[pos_b];\
    arr[pos_b] = arr[pos_a];\
    arr[pos_a] = aux;\
}

int isSmaller(void *a, void *b)
{
    int *x = (int *) a;
    int *y = (int *) b;

    if (*x > *y) {
        return *x;
    }
    if (*x < *y) {
        return *x - *y;
    }

    return 0;
}


int get_change(int coin_types[], unsigned int nr_coin_types, int change, int solution[]);

int main()
{
    int nr_coin_types, required_change, nr_coins_for_change;
    int *coin_types, *change;

    printf("Nr. of coin types: ");
    scanf("%d", &nr_coin_types);

    // Allocate memory for the coin types.
    mem_arr(coin_types, nr_coin_types, int);

    // Read and sort the coin types.
    readarr(coin_types, nr_coin_types);
    qsort(coin_types, nr_coin_types, sizeof(int), isSmaller);


    printf("Change: ");
    scanf("%d", &required_change);

    // Allocate memory for the change.
    mem_arr(change, required_change * nr_coin_types, int);

    // Get the change.
    nr_coins_for_change = get_change(coin_types, nr_coin_types, required_change, change);


    // Print the change.
    if (nr_coins_for_change) {
        printf("The minimum number of coins to form the required change: %d\n", nr_coins_for_change);

        printarr(change, nr_coins_for_change);
    }


    // Keep console window open.
    getchar();


    // Free memory.
    cleanup(2, coin_types, change);

    return 0;

}

int get_change(int coin_types[], unsigned int nr_coin_types, int required_change, int change[])
{
    int current_change = 0, current_coin_type = nr_coin_types - 1, nth_coin = 0;

    /* Loop until current_change == change.*/
    while (current_change < required_change && current_coin_type >= 0) {

        /* Add current type of coin to current change, if possible. */
        while (current_change + coin_types[current_coin_type] <= required_change) {
            current_change += coin_types[current_coin_type];

            change[nth_coin++] = coin_types[current_coin_type];
        }

        /* If not try using the next type of coin. */
        current_coin_type--;
    }

    if (current_change < required_change) {
        printf("The required change %d, cannot be formed with the given coin types: ", required_change);
        printarr(coin_types, nr_coin_types);
        return 0;
    }

    return nth_coin;
}


void readarr(int arr[], unsigned long n)
{
    for (unsigned long i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
}

void printarr(int arr[], unsigned long n)
{
    for (unsigned long i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    NEWLINE;
}


void *ec_realloc(void *ptr, unsigned long size)
{
    void *new_ptr;

    new_ptr = realloc(ptr, size);

    if (new_ptr == NULL) {
        puts("[Error] ec_realloc(): realloc() returned NULL.");
    }

    return new_ptr;
}
void *ec_malloc(unsigned long size)
{
    return ec_realloc(NULL, size);
}

void cleanup(unsigned int argc, ...)
{
    va_list args;

    va_start(args, argc);

    for (unsigned int nth_arg = 0; nth_arg < argc; ++nth_arg) {
        free(va_arg(args, void*));
    }

    va_end(args);
}