WIP

1 files changed, 66 insertions, 47 deletions

diff --git a/challenge-083/abigail/perl/ch-2.pl b/challenge-083/abigail/perl/ch-2.pl
index 6d6d726fcf..c97ecd01db 100644
--- a/challenge-083/abigail/perl/ch-2.pl
+++ b/challenge-083/abigail/perl/ch-2.pl
@@ -30,73 +30,92 @@ use experimental 'lexical_subs';
 # 
 
 #
-# So, we might as well opt for a dumb, inefficient program. We'll
-# loop from 0 to 2^@A - 1. Given a number 0 <= $n < 2^@A - 1, we'll
-# look at the binary representation, and use this to sum the numbers
-# of @A: if bit b of $n is 0, we flip the sign of $A [b]. It's then
-# just a matter of keeping track of the best score (closer to 0
-# beats further away from 0, if the same distance, less flipped
-# signs is better).
+# We are opting for a recursive solution. For each element of the set,
+# we try two possibilities: once where the flip the sign of the current
+# number, and once where we do not.
 #
-
-use List::Util qw [sum];
-
+# Our recursive method takes the following parameters:
 #
-# Read the input, store numbers in @A. $l is the size of @A.
+#     - $set:       A reference to the array of numbers, which is assumed to
+#                   sorted (largest number first). We will not modify the
+#                   array, nor pass different arrays. 
+#     - $index:     The index of the current number, 0 when first called.
+#     - $sum:       The current sum. This is the sum of all numbers, where
+#                   the signs of the numbers with index < $index may have
+#                   been flipped, but none of the signs of the numbers with
+#                   index >= $index. When first called, $sum is the sum of
+#                   all numbers in $set.
+#     - $flips:     This is number of numbers with index < $index which have
+#                   been flipped. When first called, this is 0.
+#     - $last_skip: This is the last value for we did NOT flip a sign.
+#                   If the current number equals $last_skip, we will NOT
+#                   recurse for the case the sign of the number is flipped.
 #
-my @A = <> =~ /[0-9]+/g;
-my $l = @A;
-
+# Recursion stops if any of the following conditions is true:
+#     - $sum < 0.        In that case, no matter which future choices we
+#                        make, we cannot end up with a non-negative sum. So,
+#                        we return undef, signalling a failure.
+#     - $sum == 0.       In this case, if we were to flip any of the signs
+#                        of the future numbers, the sum would become negative.
+#                        So we return the 0, and the number of flips.
+#     - $index >= @$set. We have processed the entire set, and no more
+#                        decisions can be made. So, we return $set and $flips.
 #
-# Keep track of the best sum, and least number of flips (for the
-# cases with the best sum).
+# After recursing twice, we pick the best solution. That is, the one with
+# the least defined sum, and if both cases returns in the same sum, we pick
+# the one with the least amount of flips.
 #
-my $best_sum     = sum @A;
-my $best_flipped =     @A;
 
-#
-# Iterate from 0 to 2^@A - 1
-#
-for (my $n = 0; $n < 2 ** @A; $n ++) {
+use List::Util qw [sum];
+
+sub min_flips;
+sub min_flips ($set, $index     = 0,
+                     $sum       = sum (@$set),
+                     $flips     = 0,
+                     $last_skip = $$set [$index] + 1) {
+
     #
-    # Get the flips corresponding to $n:
-    #    - Get the binary representation of $n, zero-padded
-    #      to the length of @A.
-    #    - Split on characters
-    #    - Multiply by 2, subtract 1: this turns 0 into -1, and keeps 1 as is.
+    # If the sum is less than 0, we don't have a result.
     #
-    my @flips   = map {2 * $_ - 1} split // => sprintf "%0${l}b" => $n;
+    return if $sum < 0;
 
     #
-    # Calculate the sum: add each number, multiplied by -1 or 1
+    # We're done if either the sum = 0, or we have exhausted the set.
     #
-    my $sum     = sum map {$flips [$_] * $A [$_]} keys @A;
+    return ($sum, $flips) if $index >= @$set || $sum == 0;
 
     #
-    # Count how many flips we have.
+    # Recurse twice. Once where we flip the sign of the current number,
+    # and once where we do not.
     #
-    my $flipped = grep {$_ < 0} @flips;
-
+    my ($sum1, $flips1, $sum2, $flips2);
+    ($sum1, $flips1) = min_flips $set, $index + 1,
+                                       $sum - 2 * $$set [$index],
+                                       $flips + 1,
+                                       $last_skip if $$set [$index] != $last_skip;
+    ($sum2, $flips2) = min_flips $set, $index + 1,
+                                       $sum,
+                                       $flips,
+                                       $$set [$index];
     #
-    # Do we have an improvement? For that
-    #    - The sum should be non-negative and
-    #    - Either the sum is less than the best found,
-    #    - Or equal to the best sum found, but we less flips
+    # Return the best result. Note that the first recursion may return undef.
+    # The second will never.
     #
-    if ($sum >= 0 &&
-          ($sum <  $best_sum ||
-           $sum == $best_sum && $flipped < $best_flipped)) {
-        #
-        # Remember the best sum, and best number of flips so far.
-        #
-        $best_sum     = $sum;
-        $best_flipped = $flipped;
+    return if !defined $sum1 && !defined $sum2;
+    if (defined $sum1 && ($sum1 <  $sum2 ||
+                          $sum1 == $sum2 && $flips1 < $flips2)) {
+        return ($sum1, $flips1)
+    }
+    else {
+        return ($sum2, $flips2)
     }
 }
 
 #
-# Print the result
+# Read the input, sort it, call min_flips, and print the result.
 #
-say $best_flipped;
+my $set = [sort {$b <=> $a} <> =~ /[0-9]+/g];
+say +(min_flips $set) [1];
+
 
 __END__