Perl and Python solutions for week 124, part 2

3 files changed, 157 insertions, 6 deletions

diff --git a/challenge-124/abigail/README.md b/challenge-124/abigail/README.md
index 0bd71c5813..c116d92523 100644
--- a/challenge-124/abigail/README.md
+++ b/challenge-124/abigail/README.md
@@ -81,14 +81,8 @@ Input:        Set = (10, -15, 20, 30, -25, 0, 5, 40, -5)
 ~~~~
 
 ### Solutions
-* [AWK](awk/ch-2.awk)
-* [Bash](bash/ch-2.sh)
-* [C](c/ch-2.c)
-* [Lua](lua/ch-2.lua)
-* [Node.js](node/ch-2.js)
 * [Perl](perl/ch-2.pl)
 * [Python](python/ch-2.py)
-* [Ruby](ruby/ch-2.rb)
 
 ### Blog
 [Perl Weekly Challenge 124: Tug of War][blog2]
diff --git a/challenge-124/abigail/perl/ch-2.pl b/challenge-124/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..87b51e1553
--- /dev/null
+++ b/challenge-124/abigail/perl/ch-2.pl
@@ -0,0 +1,108 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+use List::Util qw [sum];
+
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-2.pl < input-file
+#
+
+#
+# This is an NP-hard problem. So, we aren't going to bother with
+# a smart algorithm -- we'll just try every possible partition of
+# the appropriate sizes.
+# (Using dynamic programming would be a better algorithm, but
+# it would still be exponential in the worst case).
+#
+
+#
+# We'll read sets from standard input, expecting a set per line of
+# input, with the numbers separated by whitespace.
+# For each line of output, we write one line of output, with the two
+# sets separated by a semi-colon.
+#
+
+use POSIX      qw [floor ceil];
+use List::Util qw [sum0];
+
+{
+    my $best_diff = ~0;
+    my @best_set1;
+    my @best_set2;
+
+    #
+    # Initialize the bookkeeping.
+    #
+    sub init () {
+        $best_diff = ~0;  # Max int
+    }
+
+    #
+    # Given two sets, find the difference of their sums.
+    # If better than what we have seen so far, record this.
+    #
+    sub check_sets ($set1, $set2) {
+        my $diff = abs (sum (@$set1) - sum (@$set2));
+        if ($diff < $best_diff) {
+            $best_diff = $diff;
+            @best_set1 = @$set1;
+            @best_set2 = @$set2;
+        }
+    }
+
+    #
+    # Print the results
+    #
+    sub report {
+        say "@best_set1; @best_set2";
+    }
+}
+
+
+#
+# Split $set into two sets of (almost) equal size. If either of the
+# two sets has the desired size, add the remaineder of $set to the
+# other, and perform a check for the best result.
+#
+# Else, get the next element from $set, and add it to $set1 and $set2,
+# and recurse.
+#
+sub split_set ($set, $set1, $set2, $callback) {
+    my $n = @$set + @$set1 + @$set2;
+
+    if (@$set1 == floor ($n / 2)) {
+        $callback -> ($set1, [@$set2, @$set]);
+    }
+    elsif (@$set2 == ceil ($n / 2)) {
+        $callback -> ([@$set1, @$set], $set2);
+    }
+    else {
+        my $element = $$set [0];
+        split_set ([@$set [1 .. $#$set]], [@$set1, $element], $set2, $callback);
+        split_set ([@$set [1 .. $#$set]], $set1, [@$set2, $element], $callback);
+    }
+}
+
+#
+# Read input, split, and report the best split.
+#
+while (<>) {
+    init ();
+    split_set ([split], [], [], \&check_sets);
+    report ();
+}
+
+
+__END__
diff --git a/challenge-124/abigail/python/ch-2.py b/challenge-124/abigail/python/ch-2.py
new file mode 100644
index 0000000000..613634f80b
--- /dev/null
+++ b/challenge-124/abigail/python/ch-2.py
@@ -0,0 +1,49 @@
+#!/opt/local/bin/python
+
+#
+# See ../README.md
+#
+
+#
+# Run as: python ch-2.py < input-file
+#
+
+
+def init ():
+    global best_diff
+    best_diff = -1
+
+def check_sets (set1, set2):
+    global best_diff
+    global best_set1
+    global best_set2
+    diff = abs (sum (set1) - sum (set2))
+    if best_diff < 0 or diff < best_diff:
+        best_diff = diff
+        best_set1 = set1
+        best_set2 = set2
+
+def report ():
+    global best_set1
+    global best_set2
+    print (" " . join (map (lambda x: str (x), best_set1)) + "; " +
+           " " . join (map (lambda x: str (x), best_set2)))
+
+
+def split_set (set, set1, set2):
+    n = len (set) + len (set1) + len (set2)
+    if len (set1) == n // 2:
+        check_sets (set1, set2 + set)
+    elif len (set2) == (n + 1) // 2:
+        check_sets (set1 + set, set2)
+    else:
+        split_set (set [1:], set1 + [set [0]], set2)
+        split_set (set [1:], set1, set2 + [set [0]])
+
+import fileinput
+
+for line in fileinput . input ():
+    init ()
+    set = list (map (lambda x: int (x), line . strip () . split ()))
+    split_set (set, [], [])
+    report ()