Merge pull request #2602 from Abigail/abigail/week-083

Abigail/week 083

33 files changed, 361 insertions, 2 deletions

diff --git a/challenge-082/abigail/blog.txt b/challenge-082/abigail/blog.txt
deleted file mode 100644
index 55b2db8670..0000000000
--- a/challenge-082/abigail/blog.txt
+++ /dev/null
@@ -1 +0,0 @@
-https://wp.me/pcsEjt-1t
diff --git a/challenge-082/abigail/blog1.txt b/challenge-082/abigail/blog1.txt
deleted file mode 100644
index 5a9e7458c3..0000000000
--- a/challenge-082/abigail/blog1.txt
+++ /dev/null
@@ -1 +0,0 @@
-https://wp.me/pcsEjt-K
diff --git a/challenge-083/abigail/input-1-1 b/challenge-083/abigail/input-1-1
new file mode 100644
index 0000000000..5529e0dd42
--- /dev/null
+++ b/challenge-083/abigail/input-1-1
@@ -0,0 +1 @@
+The Weekly Challenge
diff --git a/challenge-083/abigail/input-1-2 b/challenge-083/abigail/input-1-2
new file mode 100644
index 0000000000..c37cae9adc
--- /dev/null
+++ b/challenge-083/abigail/input-1-2
@@ -0,0 +1 @@
+The purpose of our lives is to be happy
diff --git a/challenge-083/abigail/input-1-3 b/challenge-083/abigail/input-1-3
new file mode 100644
index 0000000000..e03ee30b37
--- /dev/null
+++ b/challenge-083/abigail/input-1-3
@@ -0,0 +1 @@
+'s Ochtends lopen door Amsterdam-Zuid.
diff --git a/challenge-083/abigail/input-1-4 b/challenge-083/abigail/input-1-4
new file mode 100644
index 0000000000..8291d0473a
--- /dev/null
+++ b/challenge-083/abigail/input-1-4
@@ -0,0 +1 @@
+Markmið lífs okkar er að vera hamingjusöm
diff --git a/challenge-083/abigail/input-1-5 b/challenge-083/abigail/input-1-5
new file mode 100644
index 0000000000..134b092055
--- /dev/null
+++ b/challenge-083/abigail/input-1-5
@@ -0,0 +1 @@
+Fŏ͢o̐ᷜ bar b⃝a⃝z⃝
diff --git a/challenge-083/abigail/input-1-6 b/challenge-083/abigail/input-1-6
new file mode 100644
index 0000000000..43e997122f
--- /dev/null
+++ b/challenge-083/abigail/input-1-6
@@ -0,0 +1 @@
+Ο σκοπός της ζωής μας είναι να είμαστε ευτυχισμένοι
\ No newline at end of file
diff --git a/challenge-083/abigail/input-2-1 b/challenge-083/abigail/input-2-1
new file mode 100644
index 0000000000..4cf880d809
--- /dev/null
+++ b/challenge-083/abigail/input-2-1
@@ -0,0 +1 @@
+3 10 8
diff --git a/challenge-083/abigail/input-2-2 b/challenge-083/abigail/input-2-2
new file mode 100644
index 0000000000..c9b958cd65
--- /dev/null
+++ b/challenge-083/abigail/input-2-2
@@ -0,0 +1 @@
+12 2 10
diff --git a/challenge-083/abigail/input-2-3 b/challenge-083/abigail/input-2-3
new file mode 100644
index 0000000000..1dd62cf6c3
--- /dev/null
+++ b/challenge-083/abigail/input-2-3
@@ -0,0 +1 @@
+3 1 1 2 2 1
diff --git a/challenge-083/abigail/input-2-4 b/challenge-083/abigail/input-2-4
new file mode 100644
index 0000000000..f7ed847e5d
--- /dev/null
+++ b/challenge-083/abigail/input-2-4
@@ -0,0 +1 @@
+4 5 6 7 8
diff --git a/challenge-083/abigail/input-2-5 b/challenge-083/abigail/input-2-5
new file mode 100644
index 0000000000..ae85de5e5e
--- /dev/null
+++ b/challenge-083/abigail/input-2-5
@@ -0,0 +1 @@
+2 2 2 2 2 9
diff --git a/challenge-083/abigail/input-2-6 b/challenge-083/abigail/input-2-6
new file mode 100644
index 0000000000..d419e83dec
--- /dev/null
+++ b/challenge-083/abigail/input-2-6
@@ -0,0 +1 @@
+20 19 18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
diff --git a/challenge-083/abigail/input-2-7 b/challenge-083/abigail/input-2-7
new file mode 100644
index 0000000000..db5114fdef
--- /dev/null
+++ b/challenge-083/abigail/input-2-7
@@ -0,0 +1 @@
+1 2 3 4 5 6 7 8 9 10
diff --git a/challenge-083/abigail/input-2-8 b/challenge-083/abigail/input-2-8
new file mode 100644
index 0000000000..f84f876b83
--- /dev/null
+++ b/challenge-083/abigail/input-2-8
@@ -0,0 +1 @@
+20 20 20 19 18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
diff --git a/challenge-083/abigail/output-1-1.exp b/challenge-083/abigail/output-1-1.exp
new file mode 100644
index 0000000000..23f20f1f2c
--- /dev/null
+++ b/challenge-083/abigail/output-1-1.exp
@@ -0,0 +1,2 @@
+# First example
+6
diff --git a/challenge-083/abigail/output-1-2.exp b/challenge-083/abigail/output-1-2.exp
new file mode 100644
index 0000000000..fd159104fd
--- /dev/null
+++ b/challenge-083/abigail/output-1-2.exp
@@ -0,0 +1,2 @@
+# Second example
+23
diff --git a/challenge-083/abigail/output-1-3.exp b/challenge-083/abigail/output-1-3.exp
new file mode 100644
index 0000000000..d31a46a8d4
--- /dev/null
+++ b/challenge-083/abigail/output-1-3.exp
@@ -0,0 +1,2 @@
+# Using ' and -, and trailing punctuation.
+18
diff --git a/challenge-083/abigail/output-1-4.exp b/challenge-083/abigail/output-1-4.exp
new file mode 100644
index 0000000000..902ff5684f
--- /dev/null
+++ b/challenge-083/abigail/output-1-4.exp
@@ -0,0 +1,2 @@
+# Icelandic, characters outside of ASCII
+17
diff --git a/challenge-083/abigail/output-1-5.exp b/challenge-083/abigail/output-1-5.exp
new file mode 100644
index 0000000000..b4478f3ca3
--- /dev/null
+++ b/challenge-083/abigail/output-1-5.exp
@@ -0,0 +1,2 @@
+# Using combining characters
+3
diff --git a/challenge-083/abigail/output-1-6.exp b/challenge-083/abigail/output-1-6.exp
new file mode 100644
index 0000000000..da3bab9392
--- /dev/null
+++ b/challenge-083/abigail/output-1-6.exp
@@ -0,0 +1,2 @@
+# Letters, but all outside ASCII and Latin-1
+30
diff --git a/challenge-083/abigail/output-2-1.exp b/challenge-083/abigail/output-2-1.exp
new file mode 100644
index 0000000000..f4af63feae
--- /dev/null
+++ b/challenge-083/abigail/output-2-1.exp
@@ -0,0 +1,2 @@
+# First example
+1
diff --git a/challenge-083/abigail/output-2-2.exp b/challenge-083/abigail/output-2-2.exp
new file mode 100644
index 0000000000..d462de75c6
--- /dev/null
+++ b/challenge-083/abigail/output-2-2.exp
@@ -0,0 +1,2 @@
+# Second example
+1
diff --git a/challenge-083/abigail/output-2-3.exp b/challenge-083/abigail/output-2-3.exp
new file mode 100644
index 0000000000..d59db9c143
--- /dev/null
+++ b/challenge-083/abigail/output-2-3.exp
@@ -0,0 +1,2 @@
+# Perfect partition
+2
diff --git a/challenge-083/abigail/output-2-4.exp b/challenge-083/abigail/output-2-4.exp
new file mode 100644
index 0000000000..d59db9c143
--- /dev/null
+++ b/challenge-083/abigail/output-2-4.exp
@@ -0,0 +1,2 @@
+# Perfect partition
+2
diff --git a/challenge-083/abigail/output-2-5.exp b/challenge-083/abigail/output-2-5.exp
new file mode 100644
index 0000000000..d00491fd7e
--- /dev/null
+++ b/challenge-083/abigail/output-2-5.exp
@@ -0,0 +1 @@
+1
diff --git a/challenge-083/abigail/output-2-6.exp b/challenge-083/abigail/output-2-6.exp
new file mode 100644
index 0000000000..0cfbf08886
--- /dev/null
+++ b/challenge-083/abigail/output-2-6.exp
@@ -0,0 +1 @@
+2
diff --git a/challenge-083/abigail/output-2-7.exp b/challenge-083/abigail/output-2-7.exp
new file mode 100644
index 0000000000..00750edc07
--- /dev/null
+++ b/challenge-083/abigail/output-2-7.exp
@@ -0,0 +1 @@
+3
diff --git a/challenge-083/abigail/output-2-8.exp b/challenge-083/abigail/output-2-8.exp
new file mode 100644
index 0000000000..b9678e13ad
--- /dev/null
+++ b/challenge-083/abigail/output-2-8.exp
@@ -0,0 +1,2 @@
+# Bigger set
+3
diff --git a/challenge-083/abigail/perl/ch-1.pl b/challenge-083/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..6d72698d93
--- /dev/null
+++ b/challenge-083/abigail/perl/ch-1.pl
@@ -0,0 +1,86 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# You are given a string $S with 3 or more words.
+#
+# Write a script to find the length of the string except the first
+# and last words ignoring whitespace.
+#
+
+
+#
+# It's not a given the input is in ASCII, so, we're assuming UTF8.
+# We need to tell Perl we're expecting input in UTF8.
+#
+binmode STDIN, ":encoding(UTF-8)" or die "binmode: $!";
+ 
+
+#
+# So, what is a word? \w+ sounds like a good idea, but that doesn't
+# capture words like "O'Reilly", hyphenated words,  or words consisting
+# of letter with combining characters. It also matches things like ___
+# or 123, which perhaps should not be considered words.
+#
+# A letter followed by zero or more combining combining characters is
+# matched by \X, but \X also matches non-word characters. So, for a
+# letter with combining characters, we can match it with:
+#
+#      (?:(?=\pL)\X*)
+#
+# Now, words can start or end with a ', or contain ' or - internally.
+# And while we will allow '- and -' internally, we don't allow double
+# '' or double --, nor any string of more than two of them. 
+#
+# We also require the sub strings consisting of letters (with their
+# combining characters) to be bounded by grapheme cluster boundary.
+#
+# This results in the following pattern for a word:
+#
+#
+
+my $word =
+     qr [(?(DEFINE)
+            (?<LETTERS>   \b{gcb} (?:(?=\pL)\X)+ \b{gcb})
+            (?<SEPARATOR> ['-] | '- | -')
+            (?<START>     '?)
+            (?<END>       '?)
+         )
+          (?&START)
+          (?&LETTERS) (?: (?&SEPARATOR) (?&LETTERS) ) *
+          (?&END)]x;
+
+
+# 
+# Now that we have a pattern for a word, we can remove the first
+# and last words. Removing the first match is easy, as Perl will, by
+# default, pick the left most possible match. 
+#
+# The last word is slightly more tricky. It's important to realize
+# than, by our definition, any word contains at least a letter, and
+# any letter is part of a word. So, if we match a word, followed by
+# a, possibly empty, string of non-letters, followed by the end of 
+# the string, we have the last word.
+#
+# After removing the first and last word, all we're left with is
+# removing whitespace, and getting the length of what is left over.
+#
+
+while (<>) {
+    chomp;
+    s/$word//;
+    s/$word(?=\PL*$)//;
+    s/\s+//g;
+    say length;
+}
+  
+
+__END__
diff --git a/challenge-083/abigail/perl/ch-2.pl b/challenge-083/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..e580d5ac2d
--- /dev/null
+++ b/challenge-083/abigail/perl/ch-2.pl
@@ -0,0 +1,154 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# You are given an array @A of positive numbers.
+#
+# Write a script to flip the sign of some members of the given array
+# so that the sum of the all members is minimum non-negative.
+# 
+# Given an array of positive elements, you have to flip the sign of
+# some of its elements such that the resultant sum of the elements
+# of array should be minimum non-negative(as close to zero as possible).
+# Return the minimum no. of elements whose sign needs to be flipped
+# such that the resultant sum is minimum non-negative.
+#
+
+#
+# This looks like an NP-complete program. 2-partition, where we're
+# asked whether we can partition a set of integers into two sets with
+# equal sums is NP-complete. That means, if you flip the signs of one
+# of the sets, and add all numbers, the result is 0, which is minimal.
+# 
+
+#
+# We solve this by using a stack of states. Each state means we're at
+# some point processing @$set. We're keeping a running sum, by either
+# adding or substracting the current number. We also keep a best score
+# so far (best sum: smallest non-negative sum; best flips: least amount
+# of flips to reach best sum). Each time we have processed the entire
+# set, we see whether we have a better score. If we haven't reached
+# the end of the set, we push two new states on the stack, one where
+# we add to the running sum, and one where we subtract from the running
+# sum. In the latter case, we increment the number of flips.
+#
+# To optimize, if we can early determine we can no longer reach a valid
+# sum (that is, all future choices in this branch lead to negative sums),
+# or if we cannot improve the current best score (that is, all future
+# choices in this branch lead to a sum which is worse than the best sum)
+# we return early, and don't push new states.
+#
+# As a final optimization, we also put the last number whose sign was
+# flipped into the state. We use this to prevent pushing cases on
+# the stack where the we add the current number, and the current number
+# is equal to the last number whose sign was flipped. This makes that
+# we process runs of equal number far more efficiently, reducing the
+# amount of generated cases from exponential to linear.
+#
+
+
+#
+# Read the numbers, and sort them.
+#
+my $set = [<> =~ /[0-9]+/g];
+   $set = [sort {$b <=> $a} @$set];
+
+#
+# Initialize the best sums and best flips, by using a greedy algorithm.
+#
+my $best_sum   = 0;
+my $best_flips = 0;
+
+foreach my $number (@$set) {
+    if ($best_sum -  $number < 0) {
+        $best_sum += $number;
+    }
+    else {
+        $best_sum -= $number;
+        $best_flips ++;
+    }
+}
+
+#
+# Create a list of partial sums:
+#     $$partial_sums [$i[ = sum @$set [$i .. $#$set];
+#
+# That is, each entry in $partial_sums is the sum of the elements in $set
+# starting from the same index, till the end.
+#
+my $partial_sums;
+$$partial_sums [@$set] = 0;
+for (my $i = @$set; $i --;) {
+    $$partial_sums [$i] = $$set [$i] + $$partial_sums [$i + 1];
+}
+
+#
+# @todo will contain 4-tuples [$index, $sum, $flips, $last_flipped],
+# each encoding a state.
+#
+#    - $index:        The current index
+#    - $sum:          Sum of the numbers @$set [0 .. $index - 1], with
+#                     zero of signs flipped.
+#    - $flips:        The number of signs which have been flipped to reach $sum.
+#    - $last_flipped: The last number whose sign we have flipped.
+#
+my @todo = [0, 0, 0, 0];
+while (@todo) {
+    my ($index, $sum, $flips, $last_flipped) = @{pop @todo};
+
+    #
+    # We can't reach a positive sum, so no need to continue this branch.
+    #
+    if ($sum + $$partial_sums [$index] < 0) {
+        next;
+    }
+
+    #
+    # If we can't improve on the current best score, no need to continue.
+    #
+    if ($sum - $$partial_sums [$index] >  $best_sum ||
+        $sum - $$partial_sums [$index] == $best_sum &&
+              $flips + @$set - $index  >= $best_flips) {
+        next;
+    }
+    
+    if ($index >= @$set) {
+        #
+        # We have exhausted the set. Do we have a better result?
+        #
+        if ($sum >= 0 &&
+               ($sum < $best_sum || $sum == $best_sum && $flips < $best_flips)) {
+            #
+            # If so, update the score.
+            #
+            ($best_sum, $best_flips) = ($sum, $flips);
+        }
+        next;
+    }
+
+    #
+    # Push the case where we are subtracting on the stack.
+    #
+    my $number = $$set [$index];
+    push @todo => [$index + 1, $sum - $number, $flips + 1, $number];
+
+    #
+    # Push the case where we are adding on the stack, but
+    # not if the current number equals the last number whose
+    # sign was flipped.
+    #
+    push @todo => [$index + 1, $sum + $number, $flips,     $last_flipped]
+          unless $last_flipped == $number;
+}
+
+say $best_flips;
+
+__END__
diff --git a/challenge-083/abigail/test.pl b/challenge-083/abigail/test.pl
new file mode 100755
index 0000000000..aa84e275d5
--- /dev/null
+++ b/challenge-083/abigail/test.pl
@@ -0,0 +1,82 @@
+#!/opt/perl/bin/perl
+
+#
+# Test the solutions. Either call it with the directory name you
+# want to test in, or call it as "../test.pl" from within the directory.
+#
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+chdir ".." if -f "../test.pl";
+
+use experimental 'signatures';
+
+use Test::More;
+
+
+my %languages = (
+    Perl        =>   {
+        exe     =>   "/opt/perl/bin/perl",
+        ext     =>   "pl",
+    },
+    JavaScript  =>   {
+        exe     =>   "/usr/local/bin/node",
+        ext     =>   "js",
+        dir     =>   "node",
+    },
+    bc          =>   {
+        exe     =>   "/usr/bin/bc",
+        ext     =>   "bc",
+        filter  =>   's/.*/main($&)/',
+    },
+    awk         =>   {
+        exe     =>   "/usr/bin/awk",
+        ext     =>   "awk",
+        args    =>   ["-f"],
+    },
+);
+
+my $perl_exe = $languages {Perl} {exe};
+
+foreach my $challenge (1, 2) {
+    my @inputs = <input-$challenge-*> or next;
+    subtest "Challenge $challenge" => sub {
+        foreach my $language (sort keys %languages) {
+            my $info     =   $languages {$language};
+            my $exe      =   $$info {exe};
+            my $ext      =   $$info {ext};
+            my $dir      =   $$info {dir}    // lc $language;
+            my @args     = @{$$info {args}   // []};
+            my $filter   =   $$info {filter} // '';
+            my $solution =  "$dir/ch-$challenge.$ext";
+            next unless -r $solution;
+
+            subtest $language => sub {
+                foreach my $input (@inputs) {
+                    my $output_exp = ($input =~ s/input/output/r) . ".exp";
+                    my $exp        = `cat $output_exp`;
+
+                    my $name = $input;
+                    if ($exp =~ s/^\s*#\s*(.*)\n//) {
+                        $name = $1;
+                    }
+
+                    my $got = `$perl_exe -ple '$filter' $input |\
+                               $exe @args ./$solution`;
+
+                    s/\h+$//gm for $exp, $got;
+                    is $got, $exp, $name;
+                }
+            }
+        }
+    }
+}
+
+done_testing;
+
+
+__END__