Solution for challenge 75, Task #1

2 files changed, 39 insertions, 17 deletions

diff --git a/challenge-075/bob-lied/perl/ch-1.pl b/challenge-075/bob-lied/perl/ch-1.pl
index 42b51a19f3..c0e4a6bc8d 100644
--- a/challenge-075/bob-lied/perl/ch-1.pl
+++ b/challenge-075/bob-lied/perl/ch-1.pl
@@ -32,6 +32,8 @@ use strict;
 use warnings;
 use feature qw(say);
 
+use Data::Dumper;
+
 use lib "lib";
 use CoinSum qw(coinSum);
 
@@ -43,7 +45,7 @@ my @C = @ARGV;
 die Usage() unless $S;
 die Usage() unless @C;
 
-# Sort denominations so largest is first.
-@C = sort { $a < $b } @C;
 
-coinSum($S, @C);
+my $result = coinSum($S, @C);
+
+say "[ @$_ ]" foreach @$result;
diff --git a/challenge-075/bob-lied/perl/lib/CoinSum.pm b/challenge-075/bob-lied/perl/lib/CoinSum.pm
index a5a7f818a5..e95500aa60 100644
--- a/challenge-075/bob-lied/perl/lib/CoinSum.pm
+++ b/challenge-075/bob-lied/perl/lib/CoinSum.pm
@@ -24,35 +24,55 @@ our @EXPORT = qw(coinSum);
 our @EXPORT_OK = qw();
 
 
-my @Combo;
+my @ComboList;
 
 sub _coinSum
 {
-    my ($target, $denomList, $currentSum, $currentDenom, $comboNum = @_;
+    my ($depth, $target, $coinList, $coin, $combo) = @_;
 
-    return 0 if ( $currentSum > $target );
+    my $diff = $target - $coin;
+    # say " depth=$depth, target = $target, coin = $coin, diff = $diff, list = [ @$coinList ], combo = [ @$combo ]";
 
-    return 1 if ( $currentSum == $target );
 
-    my $count = 0;
-    for my $denom ( @$denomList )
+    if ( $diff == 0 )
     {
-        push @{$Combo[$comboNum]]  $denom;
-        if ( $denom >= $currentDenom )
-        {
-            $comboNum += _coinSum($target, $denomList, $currentSum + $currentDenom, $denom, $comboNum);
-        }
+        push @ComboList, [ @$combo ];
+        # say "FOUND [ @$combo ]";
+        return 0;
     }
-    return $0;
+
+    if ( $diff < 0 )
+    {
+        pop @$combo;
+        # say "TOO FAR";
+        return $diff;
+    }
+
+    my @remainingCoin = sort { $a < $b } grep { $_ <= $diff } @$coinList;
+    for my $denom ( @remainingCoin )
+    {
+        push @$combo, $denom;
+        _coinSum( $depth+1, $diff, \@remainingCoin, $denom, $combo );
+        pop @$combo;
+    }
+
 }
 
 sub coinSum
 {
     my ($sum, @coins) = @_;
+ 
+    # Sort denominations so largest is first.
+    @coins = sort { $a < $b } @coins;
 
-    _coinSum($sum, \@coins, 0, $coins[0], 0);
+    while ( @coins )
+    {
+        # say "TOP: coin = $coins[0]";
+        _coinSum(1, $sum, \@coins, $coins[0], [ $coins[0] ] );
+        shift @coins;
+    }
 
-    return 0;
+    return \@ComboList;
 }
 
 1;