You can't just subtract the biggest remaining coin. doesn't always give you the best answer. | [reply] |
ahh thank you for pointing that out. So with the input 15,11,5,2:22 you should only get two 11's, not a 15+5+2 as it is less coins. Okay try 2
#!/usr/bin/env perl
use Mojolicious::Lite;
use Data::Dump;
use feature 'refaliasing';
sub makeChange {
my $line = shift;
my @available = split /[,:]/,$line;
my $changeNeeded = pop @available;
my @currentTry = sort { $b <=> $a } @available;
my %coins;
while ($changeNeeded > 0 && @currentTry > 0 ) {
my $denom = shift @currentTry;
if ($denom <= $changeNeeded) {
$changeNeeded -= $denom;
$coins{$denom}++;
unshift @currentTry,$denom;
}
}
warn "Could not make change correctly: $line" if ($changeNeede
+d != 0);
return %coins;
}
sub bestSolution {
my @input = split /[,:]/,shift;
my @solutions;
while (scalar @input > 1) {
push @solutions, { makeChange(join ',',@input)};
shift @input;
}
my $lowestNumberOfCoins = 1e7;
my $bestSolution;
for \my %solved (@solutions) {
my $sumOfCoins;
for my $coin (keys %solved) {
$sumOfCoins += $solved{$coin};
}
if ($sumOfCoins < $lowestNumberOfCoins) {
$lowestNumberOfCoins = $sumOfCoins;
$bestSolution = \%solved;
}
}
return $bestSolution;
}
get '/' => sub {
my $c = shift;
$c->render(template => 'index');
};
post '/make/change' => sub {
my $c = shift;
my $changeToMake = $c->param('data');
my @lines = split /\r?\n/, $changeToMake;
my @answer = map { bestSolution($_) } @lines;
my @formattedAnswers;
for my $coin (sort { $b <=> $a } @answer) {
my @formatted;
for (sort { $b <=> $a } keys %{$coin}) {
push @formatted, "$_". 'x' . "$coin->{$_}";
}
unshift @formattedAnswers, [ @formatted ];
}
$c->render(
answer => \@answer,
formatted=>\@formattedAnswers,
template => 'makeChange'
);
};
app->start;
__DATA__
@@ index.html.ep
% layout 'default';
% title 'Welcome';
<h2>Question 2 Data Input</h2>
<form action="/make/change" method="post" >
<textarea rows=30 cols=80 name="data" id="comment" value="" required >
</textarea>
<input type="submit" value="Run"></input>
</form>
@@ makeChange.html.ep
<h2>Question 2 Results</h2>
% for my $answer (@{$formatted}) {
%== join ',',@{$answer}
<br>
% }
@@ layouts/default.html.ep
<!DOCTYPE html>
<html>
<head><title><%= title %></title></head>
<body><%= content %></body>
</html>
| [reply]
[d/l]
[select] |