/*
* File:   main.c
* Author: Joe Churchwell
* Purpose: To Find the smallest positive integer n such that it is not possible 
*          to use exactly n US coins to make exactly one dollar.
* Created: April 21, 2014
* References: http://www-rohan.sdsu.edu/~psalamon/ProblemOfTheFortnight/POF.htm
* Notes: This is a brute force method to find the solution described in the 
 *       purpose above. There are two methods used to solve this problem:
 *       1) Recursively - Great for a more general solution where the coinage
 *          is different with different values assigned to the coinage. This
 *          can be changed using the array 'denoms'. Not as efficient as 
 *          procedural solution.
 *       2) Procedural - Great for speed and requires a lot less iterations.
 *          Not general like the recursive solution.
 * No *.h file so this can distribute better
 * This could be improved using memoization... I am just too "lazy".
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
// function prototype
unsigned char n_coin_dollar_exists(int coin_count);
unsigned char n_coin_dollar_exists_recurse(int, int, double, int);
double droundp(double val, int p);
 
long r_iterations = 0;
 
#define MAX_COINS 6
#define DEFAULT_PRECISION 5

// define statement switch to use the recursive solution
//#define RECURSIVE

// define statement switch to print out the coin solutions
#define PRINT_STATEMENTS
 
// Parts of dollar denominations
unsigned int denoms[MAX_COINS] = {1,2,4,10,20,100}; // Much More efficient
//unsigned int denoms[MAX_COINS] = {100,20,10,4,2,1};
 
// Main function to drive the solution finding
int main(int argc, char** argv)
{
    int coin_count = 1; // Start with 1 coin
   
    #ifdef RECURSIVE
    while(n_coin_dollar_exists_recurse(coin_count, 0, 0, 0) == 1)
    #else
    while(n_coin_dollar_exists(coin_count) == 1)
    #endif //RECURSIVE
    {       
    
        #if defined(PRINT_STATEMENTS) && defined(RECURSIVE)
        printf("\n");
        #endif        
        coin_count++;
    }
   
    // recursive iterations
    #ifdef RECURSIVE
    printf("Recursive Iterations = %i\n", r_iterations);
    #endif //RECURSIVE

    // output the answer
    printf("The first integer that satisfies the problem is %i",coin_count);
 
    return (EXIT_SUCCESS);
}
 
// Brute force method... recursive implementation
unsigned char n_coin_dollar_exists_recurse(
                int coin_count, int curr_sum, double curr_value, int next_idx)
{
    // Loop indexer
    int i;
    double tmp_value;
   
    // Exit condition test
    if(next_idx==MAX_COINS){
        if(curr_sum==coin_count && droundp(curr_value, DEFAULT_PRECISION)==1) 
            return 1;
        return 0;
    }
   
    // Loop through the current denomination
    for(i=0; i<=coin_count; i++){       
        r_iterations++;       
        // check to make sure we don't go over the coin count
        if(curr_sum+i > coin_count) return 0;           
        // Make sure we are not exceeding the $1 value
        tmp_value = ((double)i)/(double)denoms[next_idx];
        if( droundp(curr_value + tmp_value, DEFAULT_PRECISION) > 1) return 0; 
        // Go to the next denomination
        if(n_coin_dollar_exists_recurse(coin_count,
                                curr_sum+i,
                                curr_value+((double)i)/(double)denoms[next_idx],
                                next_idx+1)==1)
        {
            #ifdef PRINT_STATEMENTS
            printf("%i\t",i);
            #endif
            return 1;
        } // ENDIF              
    } // END FOR i           
} // END n_coin_dollar_exists_recurse
 
// Double round with precision - Used in recursive solution
double droundp(double val, int p)
{   
    double tmp;
    double tmpPower = pow(10, p);   
    tmp = val * tmpPower;
    tmp += 0.5;
    tmp = floor(tmp);
    tmp /= tmpPower;   
    return (tmp);       
}
 
// Brute force method
unsigned char n_coin_dollar_exists(int coin_count)
{
    float i,j,k,m,n,p;
   
    int tmp_coin_count;
    float tmp_coin_value;
   
    long iterations = 0;
   
    for(i=0; i<= coin_count; i++){
        for(j=0; j<= coin_count; j++){           
            // check to make sure we don't go over the coin count
            tmp_coin_count = i+j;
            if(tmp_coin_count > coin_count) break;           
            // Make sure we are not exceeding the $1 value
            tmp_coin_value = i + j/2;
            if(tmp_coin_value > 1) break;           
            for(k=0; k<= coin_count; k++){
                // check to make sure we don't go over the coin count
                tmp_coin_count = i+j+k;
                if(tmp_coin_count > coin_count) break;
                // Make sure we are not exceeding the $1 value
                tmp_coin_value = i+j/2+k/4;
                if(tmp_coin_value > 1) break;                   
                for(m=0; m<=coin_count; m++){
                    // check to make sure we don't go over the coin count
                    tmp_coin_count = i+j+k+m;
                    if(tmp_coin_count > coin_count) break;
                    // Make sure we are not exceeding the $1 value
                    tmp_coin_value = i+j/2+k/4+m/10;
                    if(tmp_coin_value > 1) break;                      
                    for(n =0; n<=coin_count; n++){                       
                        // check to make sure we don't go over the coin count
                        tmp_coin_count = i+j+k+m+n;
                        if(tmp_coin_count > coin_count) break;
                        // Make sure we are not exceeding the $1 value
                        tmp_coin_value = i+j/2+k/4+m/10+n/20;
                        if(tmp_coin_value > 1) break;                                                 
                        for(p=0; p<=coin_count; p++){                           
                            iterations++;                           
                            // check to make sure we don't go over the coin count
                            tmp_coin_count = i+j+k+m+n+p;
                            if(tmp_coin_count > coin_count) break;
                            // Make sure we are not exceeding the $1 value
                            tmp_coin_value=i+j/2+k/4+m/10+n/20+p/100;
                            if(tmp_coin_value > 1) break;                                                                                                   
                            if(tmp_coin_count==coin_count){
                                if(tmp_coin_value == 1){
                                    #ifdef PRINT_STATEMENTS
                                    printf("%i: %i,%i,%i,%i,%i,%i\n",
                                     coin_count,
                                     (int)p,(int)n,(int)m,(int)k,(int)j,(int)i);
                                    #endif  
                                    return 1;
                                } // END if(tmp_coin_value == 1)
                            } // END if(tmp_coin_count==coin_count)                                                   
                        } // END K                                               
                    } // END N                   
                } // END M               
            } // END K           
        } // END J       
    } // END I   
    printf("Iterations Performed = %i\n",iterations);   
    // nothing was found   
    return 0;
}