#!/usr/bin/perl
# 
# Application of the Greedy Algorithm.
#
# This program will take coin denominations from a datafile consisting
# of two columns:  name value.  Once the datafile is read in, the user
# may input an integer value of the change they require.  The program
# will output a list of coin denominations and the number of each 
# coin.  The user can input several different amounts of change.  When
# a value of 0 is input, the program quits.  
#
# Order of the datafile does not matter.  The algoritm is implemented
# to not need a sorted datafile.
#
# Algorithm from Fundamentals of Algorithmics by Gilles Brassard and 
# Paul Bratley, page 188.
#
#---------------------------------------------------------------------
#

# get the filename off the commandline
$file = shift(@ARGV);

# check if the commandline was correct
die "Usage: $0 <datfile>\n" unless defined($file);

open(IN,$file) or die "Error opening datfile: $!\n";


%coins = ();	# here's our data structure for the coins

# read in our data to the hash
while (<IN>) {

	($name,$value) = split(/\s+/);
	$coins{$value} = $name;

}

close(IN);

#
# the main program begins here
#

print "Input value: ";
chomp($change = <STDIN>);

while ($change > 0) { 			# loop until a value > 0 is read

	%ans = get_change($change);	# do the algorithm

	if (defined(%ans)) {		# check if we got back a good answer

		# go thru the elements of the associative array
		# sort by smallest to largest denomination of coinage
		foreach $item (sort {$a <=> $b} (keys %ans)) {
			print "$coins{$item} :  $ans{$item}\n";
		}
	}
	else {
		print "No such combination exists, please try again.\n";
	}

	# clean up the answer
	undef %ans unless !defined(%ans);

	print "Input value: ";
	chomp($change = <STDIN>);

}

print "\n";
exit;


# get_change
#
# Performs the Greedy Algorithm for getting change.
#
# Input:  scalar value n
# Output: associative array of values adding up to n or
#         undef if value cannot be done.
#
# Note:  Associative array does not need to be ordered
#
sub get_change($) {

	my $n = shift(@_);	# value we're looking for
	my $s = 0;		# current sum
	my %S = ();		# associative array of coins adding to n

	while ($s != $n) {
		
		my $x = get_largest($s, $n, %coins);

		# value not found in set
		if ($x < 0) {
			return;
		}

		$S{$x} = $S{$x} + 1;
		$s = $s + $x;
	}
		
	return %S;
}

# get_largest
#
# Gets largest value from hash such that
#    s + x <= n
# where x is a key in the hash.
#
# Input:  scalar s, scalar n, hash S
#         where s is the current sum, n is the value looking for, and
#         S is the associative array of elements in the coin set.
# Output: max, value of the largest item in the coin set
#         -1 if no value can be found
#
# Note:  Associative array does not need to be ordered
#
sub get_largest($$%) {

	my ($s,$n,%S) = @_;
	my $max = -1;

	# go thru the assoc array
	foreach $item (keys %S) {
		
		# if the item fits the properties, make it the max
		if ((($s + $item) <= $n) && ($item > $max)) {
			$max = $item;
		}
	}

	return $max;
}