Merge pull request #4834 from jo-37/contrib

Solutions to challenge 128

2 files changed, 205 insertions, 0 deletions

diff --git a/challenge-128/jo-37/perl/ch-1.pl b/challenge-128/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..b4f6a02792
--- /dev/null
+++ b/challenge-128/jo-37/perl/ch-1.pl
@@ -0,0 +1,126 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use PDL;
+use Test2::V0 '!float';
+use experimental qw(signatures postderef);
+
+our ($tests, $examples);
+$PDL::whichND = 's';
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [row1 ... rowN]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+row1 ... rowN
+    The matrix by rows. Use whitspace separated values for each single
+    row, e.g.
+    $0 '1 0 0' '1 0 0'
+
+EOS
+
+
+### Input and Output
+
+# Generate a zero matrix in the found dimensions.  It's a fake, but one
+# zero matrix is as good any zero matrix - as long as their dimensions
+# agree.
+say zeros(zero_submatrix(byte join ';', @ARGV)->@*);
+
+
+### Implementation
+
+# Loop over all sub matrix dimensions in descending size down from the
+# given matrix' dimensions and stop at the first all-zero sub matrix
+# hit. 
+sub zero_submatrix ($m) {
+    # The loop variable is a 1-d index piddle holding the sub matrix
+    # dimensions.
+    for my $dims (sort {prod($b) <=> prod($a)}
+        (ndcoords(indx, $m)->clump(1, 2) + 1)->dog) {
+            # Build "array ref syntax" slice arguments such that a sub
+            # matrix of the current dimensions having an upper left
+            # element inside the resulting slice fits into the full
+            # matrix, i.e.  a "PDL way" to get [[0, -dim0], [0, -dim1]]
+            # from [dim0, dim1]
+            my $slice = indx(0, 0)->cat(-$dims)->xchg(1, 0)->unpdl;
+            # Select all sub matrices in the current dimensions having a
+            # zero as the upper left element, take the logical "or" over
+            # the values therein and return the current dimensions as an
+            # array ref if there is an all-zero sub matrix.
+            return $dims->unpdl if !all 
+                $m->range(whichND(!$m->slice(@$slice)), $dims)
+                ->reorder(1, 2, 0)->orover->orover;
+    }
+    return [0, 0];
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        # 2x3 and 3x2 are both valid.
+        like zero_submatrix(byte(
+            [1, 0, 0, 0, 1, 0],
+            [1, 1, 0, 0, 0, 1],
+            [1, 0, 0, 0, 0, 0])),
+            bag {item 2; item 3; end;}, 'example 1';
+        is zero_submatrix(byte(
+            [0, 0, 1, 1],
+            [0, 0, 0, 1],
+            [0, 0, 1, 0])), [2, 3], 'example 2';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        like zero_submatrix(byte(
+            [1, 0, 0, 0, 0, 0],
+            [1, 1, 0, 0, 1, 0],
+            [1, 0, 0, 0, 0, 0])),
+            [2, 3], 'like example 1, forced to 2x3';
+        is zero_submatrix(byte(
+            [1, 1],
+            [1, 1])), [0, 0], 'no zero';
+        is zero_submatrix(byte(
+            [1, 0],
+            [1, 1])), [1, 1], 'single zero';
+        is zero_submatrix(byte(
+            [0, 0],
+            [0, 0],
+            [0, 0])), [2, 3], 'full size';
+        is zero_submatrix(byte(
+            [0, 0, 0],
+            [0, 0, 1],
+            [0, 0, 0],
+            [0, 1, 0])), [2, 3], 'upper left';
+        is zero_submatrix(byte(
+            [0, 0, 0],
+            [1, 0, 0],
+            [0, 0, 0],
+            [0, 1, 0])), [2, 3], 'upper right';
+        is zero_submatrix(byte(
+            [0, 1, 0],
+            [0, 0, 0],
+            [0, 0, 1],
+            [0, 0, 0])), [2, 3], 'lower left';
+        is zero_submatrix(byte(
+            [0, 1, 0],
+            [0, 0, 0],
+            [1, 0, 0],
+            [0, 0, 0])), [2, 3], 'lower right';
+	}
+
+    done_testing;
+    exit;
+}
diff --git a/challenge-128/jo-37/perl/ch-2.pl b/challenge-128/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..62f101d10b
--- /dev/null
+++ b/challenge-128/jo-37/perl/ch-2.pl
@@ -0,0 +1,79 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use Test2::V0;
+use List::Util 'reduce';
+use experimental 'signatures';
+
+our ($tests, $examples);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [arrivals departures]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+arrivals
+    comma and/or space separated list of arrivals, e.g.
+    '11:20, 14:30'
+
+departures
+    comma and/or space separated list of departures, e.g.
+    '11:50, 15:00'
+
+EOS
+
+
+### Input and Output
+
+say platforms(map [split /[,\s]\s*/, $_], @ARGV);
+
+
+### Implementation
+
+# Unwinding from behind and outwards:
+# - Convert the arrival and departure arrays to AoAs holding the time
+#   and train delta (arrivals: +1, departures: -1).
+# - Remove the colon from [H]H:MM to gain numeric comparability.
+# - Sort/merge the arrival/departure lists by time and event.  Presuming
+#   arrivals to occur before simultaneous departures and thus forbidding
+#   the usage of the same platform for such.
+# - Count the current and maximum number of present trains at each
+#   event.
+# - The first element of the reduce result is the maximum number of
+#   simultaneously present trains and therefore the requested minimum
+#   number of required platforms.
+sub platforms ($arrivals, $departures) {
+    (reduce {[$a->[($a->[1] += $b->[1]) > $a->[0]], $a->[1]]}
+        ['-inf', 0], sort {$a->[0] <=> $b->[0] || $b->[1] <=> $a->[1]}
+        map {$_->[0] =~ tr/://d; $_}
+        map([$_, 1], @$arrivals), map([$_, -1], @$departures))->[0];
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+        is platforms([qw(11:20 14:30)], [qw(11:50 15:00)]), 1, 'example 1';
+        is platforms([qw(10:20 11:00 11:10 12:20 16:20 19:00)],
+            [qw(10:30 13:20 12:40 12:50 20:20 21:20)]), 3, 'example 2';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+        is platforms([qw(9:30 10:00)], [qw(10:15 10:30)]), 2, 'one digit hour';
+        is platforms([qw(09:30 10:00)], [qw(10:15 10:30)]), 2, 'leading zero';
+        is platforms([qw(1:00 1:10)], [qw(1:10 1:20)]), 2,
+            'no simultaneous arrival and departure at the same platform';
+	}
+
+    done_testing;
+    exit;
+}