Merge pull request #9084 from jo-37/contrib

Solutions to challenge 243

5 files changed, 265 insertions, 44 deletions

diff --git a/challenge-243/jo-37/Blog.md b/challenge-243/jo-37/Blog.md
deleted file mode 100644
index f3ae3e7b96..0000000000
--- a/challenge-243/jo-37/Blog.md
+++ /dev/null
@@ -1,44 +0,0 @@
-# Missing Reversed Inversions
-## Task 1: Missing Members
-> You are given two arrays of integers.
-> Write a script to find out the missing members in each other arrays.
-
-In set theory, given two sets A and B, this task asks for the difference sets A \ B and B \ A.
-
-There are many approches to solve this with Perl.
-The most basic way would be to use hashes as representations of sets.
-Hash slices come *very* handy when an array shall be convertet to as set:
-```
-my @a = (...);
-my %ha;
-@ha{@a} = ();
-```
-Now `%h` is a hash with all members of `@a` as keys.
-Taking the set difference A \ B to a second array `@b` is as easy as:
-```
-@b = (...);
-delete @ha{@b};
-```
-However, I prefer a more functional approach.
-Using PDL ndarrays of unique sorted numbers as set representations.
-Then we may use PDL set operation in a natural way to solve the task:
-```
-$m1 = long(...)->uniq;
-```
-makes `$m1` a 1-d ndarray representing a set and
-```
-setdiff_sorted($m1, $m2);
-```
-gives M1 \ M2.
-Same result, but better readable.
-## Task 2: Flip Matrix
-> You are given `n x n` binary matrix. 
-> Write a script to flip the given matrix as below.
- 
-Again, with PDL this task is almost trivial.
-Using `PDL::NiceSlice` we may reverse a dimension using the notation `(-1:0)`.
-Reverting a value is done with the unary negation operator `!`.
-Performing the "flip matrix" operation on a 2-d ndarray `$m` thus is as easy as:
-```
-!$m->(-1:0)
-```
\ No newline at end of file
diff --git a/challenge-243/jo-37/blog.txt b/challenge-243/jo-37/blog.txt
new file mode 100644
index 0000000000..81846d2cb9
--- /dev/null
+++ b/challenge-243/jo-37/blog.txt
@@ -0,0 +1 @@
+https://github.com/manwar/perlweeklychallenge-club/blob/master/challenge-243/jo-37/blog/Blog.md
diff --git a/challenge-243/jo-37/blog/Blog.md b/challenge-243/jo-37/blog/Blog.md
new file mode 100644
index 0000000000..ce6ce1aec2
--- /dev/null
+++ b/challenge-243/jo-37/blog/Blog.md
@@ -0,0 +1,143 @@
+# Count the Pairs on the Floor
+
+## Task 1: Reverse Pairs
+**Submitted by: Mohammad S Anwar**
+
+---
+
+You are given an array of integers.
+
+Write a script to return the number of reverse pairs in the given array.
+
+A reverse pair is a pair `(i, j)` where:
+a) `0 <= i < j < nums.length` and
+b) `nums[i] > 2 * nums[j]`.
+
+### Example 1
+```
+Input: @nums = (1, 3, 2, 3, 1)
+Output: 2
+
+(1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1
+(3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1
+```
+### Example 2
+```
+Input: @nums = (2, 4, 3, 5, 1)
+Output: 3
+
+(1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1
+(2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1
+(3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1
+```
+---
+### Solution
+Using the Perl Data Language to solve this task.
+
+First we create a 1-d long ndarray from the given numbers.
+```
+$nums = long 1, 3, 2, 3, 1;
+```
+Then we create a sequence in the same shape as `$nums`, i.e. a 1-d ndarray holding the column indices of `$nums` and a second sequence as a single column holding the row indices.
+When combining these index ndarrays, according to PDL's broadcasting rules both will be extended by replicating along a dimension to fit each other.
+For visualization, these replications may be performed explicitly:
+
+A) Add a dummy dimension 1 to the row and replicate it five times.
+```
+say sequence(5)->dup(1, 5);
+[
+ [0 1 2 3 4]
+ [0 1 2 3 4]
+ [0 1 2 3 4]
+ [0 1 2 3 4]
+ [0 1 2 3 4]
+]
+```
+B) Replicate dimension 0 of the column five times.
+```
+say sequence(1, 5)->dup(0, 5);
+[
+ [0 0 0 0 0]
+ [1 1 1 1 1]
+ [2 2 2 2 2]
+ [3 3 3 3 3]
+ [4 4 4 4 4]
+]
+```
+Hence we get an upper right triangular matrix of ones when comparing the indices:
+```
+say sequence($nums) > sequence(1, $nums->dim(0));
+[
+ [0 1 1 1 1]
+ [0 0 1 1 1]
+ [0 0 0 1 1]
+ [0 0 0 0 1]
+ [0 0 0 0 0]
+]
+```
+In the same manner we can compare `$nums` as a column with itself as a doubled row:
+```
+say $nums->dummy(0) > 2 * $nums
+[
+ [0 0 0 0 0]
+ [1 0 0 0 1]
+ [0 0 0 0 0]
+ [1 0 0 0 1]
+ [0 0 0 0 0]
+]
+```
+The "bit and" of both matrices literally follows the definition of reverse pairs.
+The sum over the and'ed matrices yields the total number of reverse pairs:
+```
+((sequence($nums) > sequence(1, $nums->dim(0)))
+    & ($nums->dummy(0) > 2 * $nums))->sum;
+```
+## Task 2: Floor Sum
+**Submitted by: Mohammad S Anwar**
+
+---
+You are given an array of positive integers (`>=1`).
+
+Write a script to return the sum of `floor(nums[i] / nums[j])` where `0 <= i,j < nums.length`. The `floor()` function returns the integer part of the division.
+### Example 1
+```
+Input: @nums = (2, 5, 9)
+Output: 10
+
+floor(2 / 5) = 0
+floor(2 / 9) = 0
+floor(5 / 9) = 0
+floor(2 / 2) = 1
+floor(5 / 5) = 1
+floor(9 / 9) = 1
+floor(5 / 2) = 2
+floor(9 / 2) = 4
+floor(9 / 5) = 1
+```
+### Example 2
+```
+Input: @nums = (7, 7, 7, 7, 7, 7, 7)
+Output: 49
+```
+---
+### Solution
+Again, using PDL.
+
+Creating a 1-d double ndarray from the given numbers:
+```
+$nums = pdl 2, 5, 9;
+```
+Divide `$nums` as row by `$nums` as column in the same manner as in task 1 and apply `floor()`:
+```
+say floor $nums / $nums->dummy(0);
+[
+ [1 2 4]
+ [0 1 1]
+ [0 0 1]
+]
+```
+Finally, sum over this matrix:
+```
+floor($nums / $nums->dummy(0))->sum;
+```
+This works not only for positive integers but for all non-zero integers.
diff --git a/challenge-243/jo-37/perl/ch-1.pl b/challenge-243/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..0dc839cd04
--- /dev/null
+++ b/challenge-243/jo-37/perl/ch-1.pl
@@ -0,0 +1,60 @@
+#!/usr/bin/perl -s
+
+use Test2::V0 '!float';
+use PDL;
+
+our ($tests, $examples);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [--] [N...]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+N...
+    list of integers
+
+EOS
+
+
+### Input and Output
+
+say count_reverse_pairs(@ARGV);
+
+
+### Implementation
+
+# Count element pairs where $j > $i and $nums[$i] > 2 * $nums[$j].
+
+sub count_reverse_pairs {
+	my $nums = long @_;
+
+    ((sequence($nums) > sequence(1, $nums->dim(0)))
+        & ($nums->dummy(0) > 2 * $nums))->sum;
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is count_reverse_pairs(1, 3, 2, 3, 1), 2, 'example 1';
+        is count_reverse_pairs(2, 4, 3, 5, 1), 3, 'example 2';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        is count_reverse_pairs(1, 0, -1), 3, 'zero and negative';
+	}
+
+    done_testing;
+    exit;
+}
diff --git a/challenge-243/jo-37/perl/ch-2.pl b/challenge-243/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..5908f1337f
--- /dev/null
+++ b/challenge-243/jo-37/perl/ch-2.pl
@@ -0,0 +1,61 @@
+#!/usr/bin/perl -s
+
+use Test2::V0 '!float';
+use PDL;
+
+our ($tests, $examples);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [N...]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+N...
+    list of positive integers
+
+EOS
+
+
+### Input and Output
+
+say floor_sum(@ARGV);
+
+
+### Implementation
+
+# Sum over floor($nums[$i] / $nums[$j]).
+
+sub floor_sum {
+    my $nums = pdl @_;
+
+    floor($nums / $nums->dummy(0))->sum;
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is floor_sum(2, 5, 9), 10, 'example 1';
+        is floor_sum(7, 7, 7, 7, 7, 7, 7), 49, 'example 2';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        # floor(3 / (-2)) = -2
+        # floor((-2) / 3) = -1
+        is floor_sum(3, -2), -1, 'negative elements';
+	}
+
+    done_testing;
+    exit;
+}