Week 148, part 2: Update AWK, bc and Perl solutions

3 files changed, 82 insertions, 66 deletions

diff --git a/challenge-148/abigail/awk/ch-2.awk b/challenge-148/abigail/awk/ch-2.awk
index 58753e2615..7bbedf00a9 100644
--- a/challenge-148/abigail/awk/ch-2.awk
+++ b/challenge-148/abigail/awk/ch-2.awk
@@ -25,8 +25,7 @@ BEGIN {
 
     max_index = 1  # Index of largest sum
 
-    k = 0
-    while (3 * k + 2 <= out [max_index, 4]) {
+    for (k = 0; 3 * k + 2 <= out [max_index, 4]; k ++) {
         a  = 3 * k + 2
         f1 =     k + 1
         f2 = 8 * k + 5
@@ -66,19 +65,29 @@ BEGIN {
             }
         }
 
-        delete seen
-
         for (i = 1; i <= d1c; i ++) {
             for (j = 1; j <= d2c; j ++) {
                 b = d1 [i] * d2 [j]
-                if (!(b in seen)) {
-                    c = f1 * f1 * f2 / (b * b)
-                    if (a + b + c < out [max_index, 4]) {
-                        out [max_index, 1] = a
-                        out [max_index, 2] = b
-                        out [max_index, 3] = c
-                        out [max_index, 4] = a + b + c
+                c = f1 * f1 * f2 / (b * b)
+                if (a + b + c < out [max_index, 4]) {
+                    #
+                    # Skip duplicates
+                    #
+                    seen = 0
+                    for (m = 1; m <= COUNT; m ++) {
+                        if (out [m, 1] == a && out [m, 2] == b) {
+                            seen = 1
+                        }
                     }
+                    if (seen) {
+                        break
+                    }
+
+                    out [max_index, 1] = a
+                    out [max_index, 2] = b
+                    out [max_index, 3] = c
+                    out [max_index, 4] = a + b + c
+                
                     #
                     # Find the new max_index
                     #
@@ -90,11 +99,9 @@ BEGIN {
                             max_index = l
                         }
                     }
-                    seen [b] = 1
                 }
             }
         }
-        k ++
     }
 
     #
@@ -104,5 +111,3 @@ BEGIN {
         printf ("%d %d %d\n", out [i, 1], out [i, 2], out [i, 3])
     }
 }
-
-
diff --git a/challenge-148/abigail/bc/ch-2.bc b/challenge-148/abigail/bc/ch-2.bc
index 787b5ad28d..cb9280ebb2 100644
--- a/challenge-148/abigail/bc/ch-2.bc
+++ b/challenge-148/abigail/bc/ch-2.bc
@@ -18,9 +18,7 @@ for (i = 1; i <= count; i ++) {
 
 max_index = 1
 
-k = 0
-
-while (3 * k + 2 <= out_sum [max_index]) {
+for (k = 0; 3 * k + 2 <= out_sum [max_index]; k ++) {
     a  = 3 * k + 2
     f1 =     k + 1
     f2 = 8 * k + 5
@@ -60,29 +58,25 @@ while (3 * k + 2 <= out_sum [max_index]) {
         }
     }
 
-    seen_c = 0
-
     for (i = 1; i <= d1c; i ++) {
         for (j = 1; j <= d2c; j ++) {
             b = d1 [i] * d2 [j]
-            #
-            # Check if b is in seen
-            #
-            in_seen = 0
-            for (m = 0; m < seen_c; m ++) {
-                if (seen [m] == b) {
-                    in_seen = 1
+            c = f1 * f1 * f2 / (b * b)
+            if (a + b + c < out_sum [max_index]) {
+                seen = 0
+                for (m = 1; m <= count; m ++) {
+                    if (out_a [m] == a && out_b [m] == b) {
+                        seen = 1
+                    }
                 }
-            }
-
-            if (in_seen == 0) {
-                c = f1 * f1 * f2 / (b * b)
-                if (a + b + c < out_sum [max_index]) {
-                    out_a   [max_index] = a
-                    out_b   [max_index] = b
-                    out_c   [max_index] = c
-                    out_sum [max_index] = a + b + c
+                if (seen == 1) {
+                    break
                 }
+
+                out_a   [max_index] = a
+                out_b   [max_index] = b
+                out_c   [max_index] = c
+                out_sum [max_index] = a + b + c
                 #
                 # Find the new max_index
                 #
@@ -94,12 +88,9 @@ while (3 * k + 2 <= out_sum [max_index]) {
                         max_index = l
                     }
                 }
-                seen [seen_c] = 1
-                seen_c = seen_c + 1
             }
         }
     }
-    k = k + 1
 }
 
 #
diff --git a/challenge-148/abigail/perl/ch-2.pl b/challenge-148/abigail/perl/ch-2.pl
index a63742b3a6..00fc86d439 100644
--- a/challenge-148/abigail/perl/ch-2.pl
+++ b/challenge-148/abigail/perl/ch-2.pl
@@ -29,7 +29,8 @@ use experimental 'lexical_subs';
 # Order them on (a1 + b1 + c1) <=> (a2 + b2 + c2)?
 # Order them on  a1 <=> a2 || b1 <=> b2?
 # Order them on  min (a1, b1, c1) <=> min (a2, b2, c2) (with ties
-#     broken on the second smallest number)?
+#     broken on the second smallest number)? (Since for each possible
+#     a, there is a solution with b = 1, this may be boring).
 # Some other order?
 #
 # We will pick the first one.
@@ -81,26 +82,33 @@ use experimental 'lexical_subs';
 #
 
 #
-# So, how many k do we have to try? We start generating triples.
-# As soon as we have 5 of them, we find the sum of the 5th triple.
-# We then continue until 3 * k + 2 exceeds this sum.
+# To know when we can stop generating triples, we keep the 5 best
+# triples so far, updating them each time we find a better triple.
+# Once 3 * k + 2 (= a) exceeds the sum of the fifth triple, we know
+# we cannot find better.
 #
 
 use Math::Prime::Util qw [divisors];
 use List::Util        qw [sum max];
 
-my @out;
-
 my $COUNT = 5;
+my $A     = 0;
+my $B     = 1;
+my $C     = 2;
+my $SUM   = 3;
+my @out;
+foreach my $i (0 .. $COUNT - 1) {
+    $out [$i]        = [(999999) x 3];
+    $out [$i] [$SUM] = sum @{$out [$i]};
+}
 
-my $max;
+my $max_index = 0;
 
-for (my $k = 0; !$max || 3 * $k + 2 <= $max; $k ++) {
-    my $A  = 3 * $k + 2;
+for (my $k = 0; 3 * $k + 2 <= $out [$max_index] [$SUM]; $k ++) {
+    my $a  = 3 * $k + 2;
     my $f1 =     $k + 1;
     my $f2 = 8 * $k + 5; 
 
-    my %seen;
     #
     # Divisors of (k + 1)
     #
@@ -115,28 +123,40 @@ for (my $k = 0; !$max || 3 * $k + 2 <= $max; $k ++) {
     # Calculate all the solutions for b and c (for this k)
     #
     foreach my $d1 (@d1) {
+      D2:
         foreach my $d2 (@d2) {
-            $seen {$d1 * $d2} = ($f1) ** 2 * $f2 / ($d1 * $d1 * $d2 * $d2);
+            my $b = $d1 * $d2;
+            my $c = $f1 * $f1 * $f2 / ($b * $b);
+            if ($a + $b + $c < $out [$max_index] [$SUM]) {
+                #
+                # Avoid duplicate entries
+                #
+                foreach my $info (@out) {
+                    next D2 if $$info [$A] == $a && $$info [$B] == $b;
+                }
+
+                #
+                # Put triple in the output structure
+                #
+                $out [$max_index] = [$a, $b, $c, $a + $b + $c];
+
+                #
+                # Find the index of the new highest value
+                #
+                $max_index = 0;
+                my $max_sum = $out [$max_index] [$SUM];
+                for (my $i = 1; $i < $COUNT; $i ++) {
+                    if ($out [$i] [$SUM] > $max_sum) {
+                        $max_index = $i;
+                        $max_sum   = $out [$i] [$SUM];
+                    }
+                }
+            }
         }
     }
-
-    #
-    # Add solutions to @out
-    #
-    push @out => map {[$A, $_, $seen {$_}]} keys %seen;
-
-    #
-    # Find the stopping requirement.
-    #
-    if (!$max && @out >= $COUNT) {
-        @out = sort {sum (@$a) <=> sum (@$b)} @out;
-        $max = sum @{$out [$COUNT - 1]};
-    }
 }
 
 
-@out = sort {sum (@$a) <=> sum (@$b)} @out;
-
-say "@$_" for @out [0 .. $COUNT - 1];
+say "@$_[$A, $B, $C]" for @out;
 
 __END__