in reply to Re^3: IBM Cloud Challenge.
in thread IBM Cloud Challenge.

You can't just subtract the biggest remaining coin. doesn't always give you the best answer.

Replies are listed 'Best First'.
Re^5: IBM Cloud Challenge.
by trippledubs (Deacon) on Aug 31, 2015 at 00:12 UTC

    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>

    [download]
[reply]
[d/l]
[select]

In Section Meditations