/***************************************************
**  Jeffrey Absher  CSC491 Fall 2001 DePaul       **
**  algs1.c to take an input file and determine   **
**  optimal solution to make change from an       **
**  infinite set of coins of given denominations  **
**  This should take appox (n * m ) iters if      **
**  given a value = n and quantity m denminations **
**  of coins.                                     **
***************************************************/


#include <stdio.h>
#define INFINITY 65536
#define MAXARRAY 128
struct ll
{
	int data;
	struct ll *next;
};

struct bestchange
{
	int totalc;
	int addcoin;
	struct bestchange *next;
};


struct ll *push( int x, struct ll *inll )
{
	struct ll *retval;
        retval = ( struct ll * ) malloc( sizeof( struct ll ));
	retval->data = x;
	retval->next = inll;
	return( retval );
}


void freelist( struct ll *inll )
{
	if( inll == NULL )
	{ 
		return;
	}
	else
	{
		freelist( inll->next );
		free( inll );
		return ;
	}
}

struct ll *listrev( struct ll *inlist, struct ll *outlist )
{
	if( !inlist ) 
	{
		return( outlist );
	}
	else
	{
		return( listrev( inlist->next, push( inlist->data, outlist )));
	}
}

int makechange( int amount, struct ll *coinlist) ;

int main( int argc, char *argv[] )
{
	FILE *infile;
	struct ll *coinlist = NULL;
	struct ll *valuelist = NULL;
	struct ll *vlwalker = NULL;
	struct ll *clwalker = NULL;
	struct ll *trash = NULL;
	int numcoins = 0;
        if( argc != 2)
        {
                printf("\nSyntax:\n%s inputfile\n", argv[0]);
                exit( 0 );
        }
	printf("\nReading input file %s", argv[1]);
	infile= fopen( argv[1], "r" );
	fscanf( infile, "%d", &numcoins );
	while( numcoins-- > 0)
	{
		int temp;
		fscanf( infile, "%d", &temp );
		coinlist = push( temp, coinlist );
		printf(".");
	}
	while( !feof(infile) )
	{
		int temp;
		fscanf( infile, "%d", &temp );
		valuelist = push( temp, valuelist );
	}
	trash = valuelist;
	valuelist = valuelist->next;
	trash->next = NULL;
	freelist( trash );
	trash = NULL;
	trash = listrev( valuelist, NULL );
	freelist( valuelist );
	valuelist = trash;
	trash = NULL;
	trash = listrev( coinlist , NULL);
	freelist( coinlist );
	coinlist = trash;
	trash= NULL;
	vlwalker = valuelist;
	clwalker = coinlist;
	printf("\ncoinlist: ");
	while( clwalker )
	{
		printf("%d ",clwalker->data );
		clwalker = clwalker->next;
	}
	printf("\nvaluelist: ");
	while( vlwalker )
	{
		printf("%d ", vlwalker->data );
		vlwalker = vlwalker->next;
	}
	printf("\n");
	vlwalker = valuelist;
	clwalker = coinlist;
	while(vlwalker )
	{
		makechange( vlwalker->data, clwalker )  ;
		vlwalker = vlwalker->next;
	}
	freelist( coinlist );
	freelist( valuelist ); 
	fclose( infile );
	printf("\nEnd Run");
	exit(0);
}

int makechange( int amount, struct ll *coinlist)
{
	int i = 0;
	int iters = 0;
	struct ll *clwalker = coinlist;
	struct bestchange array[MAXARRAY]; 
	struct bestchange *arraywalker = NULL;
	for(i=1; i <= amount; i++ )
	{
		array[i].totalc=INFINITY;
		array[i].addcoin = NULL;
		array[i].next = NULL;
	}
	while( clwalker )
	{
		array[clwalker->data].totalc = 1;
		array[clwalker->data].addcoin = clwalker->data;
		clwalker = clwalker->next;
	}
	clwalker = coinlist;
	for(i = 1; i <= amount; i++ )
	{
		if( array[i].totalc >= INFINITY )
		{
			clwalker = coinlist; 
			while( clwalker )
			{
			iters++;
				if( i - clwalker->data >= 1 && array[(i - clwalker->data)].totalc + 1 < array[i].totalc )
				{
					array[i].totalc = array[i - clwalker->data].totalc + 1;
					array[i].addcoin = clwalker->data;
					array[i].next = &(array[i - clwalker->data]);
				}
				clwalker = clwalker->next;
			}
		}
	}
	arraywalker = &(array[amount]);
	printf("\n%d iters to determine qty(%d) coins for %d change:\n", iters, arraywalker->totalc, amount);
	while( arraywalker )
	{
		printf("%d ",arraywalker->addcoin);;
		arraywalker = arraywalker->next;
	}
	printf(".\n\n");
	return(1);
}