From 85575a59583647688246d2d690bf66d3a14325cd Mon Sep 17 00:00:00 2001 From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com> Date: Mon, 13 Nov 2023 10:31:57 +0100 Subject: Solution to task 1 --- challenge-243/jo-37/perl/ch-1.pl | 60 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100755 challenge-243/jo-37/perl/ch-1.pl 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 < $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; +} -- cgit From e8808258396d8d451f4a25960091c928f90e0ee1 Mon Sep 17 00:00:00 2001 From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com> Date: Mon, 13 Nov 2023 10:32:09 +0100 Subject: Solution to task 2 --- challenge-243/jo-37/perl/ch-2.pl | 61 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 61 insertions(+) create mode 100755 challenge-243/jo-37/perl/ch-2.pl 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 <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; +} -- cgit From f92f87ee3da721680c6d097f1b7e7677e5329386 Mon Sep 17 00:00:00 2001 From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com> Date: Mon, 13 Nov 2023 10:31:33 +0100 Subject: Blog for challenge 243 --- challenge-243/jo-37/Blog.md | 44 ------------ challenge-243/jo-37/blog.txt | 1 + challenge-243/jo-37/blog/Blog.md | 142 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 143 insertions(+), 44 deletions(-) delete mode 100644 challenge-243/jo-37/Blog.md create mode 100644 challenge-243/jo-37/blog.txt create mode 100644 challenge-243/jo-37/blog/Blog.md 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..dd75639527 --- /dev/null +++ b/challenge-243/jo-37/blog/Blog.md @@ -0,0 +1,142 @@ +#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. \ No newline at end of file -- cgit From 479ffe0ca464f86c2334abb2d6f947486742309c Mon Sep 17 00:00:00 2001 From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com> Date: Fri, 17 Nov 2023 16:21:46 +0100 Subject: Fix markdown --- challenge-243/jo-37/blog/Blog.md | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) diff --git a/challenge-243/jo-37/blog/Blog.md b/challenge-243/jo-37/blog/Blog.md index dd75639527..ce6ce1aec2 100644 --- a/challenge-243/jo-37/blog/Blog.md +++ b/challenge-243/jo-37/blog/Blog.md @@ -1,5 +1,6 @@ -#Count the Pairs on the Floor -##Task 1: Reverse Pairs +# Count the Pairs on the Floor + +## Task 1: Reverse Pairs **Submitted by: Mohammad S Anwar** --- @@ -12,7 +13,7 @@ A reverse pair is a pair `(i, j)` where: a) `0 <= i < j < nums.length` and b) `nums[i] > 2 * nums[j]`. -###Example 1 +### Example 1 ``` Input: @nums = (1, 3, 2, 3, 1) Output: 2 @@ -20,7 +21,7 @@ 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 +### Example 2 ``` Input: @nums = (2, 4, 3, 5, 1) Output: 3 @@ -30,7 +31,7 @@ Output: 3 (3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1 ``` --- -###Solution +### Solution Using the Perl Data Language to solve this task. First we create a 1-d long ndarray from the given numbers. @@ -91,14 +92,14 @@ 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 +## 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 +### Example 1 ``` Input: @nums = (2, 5, 9) Output: 10 @@ -113,13 +114,13 @@ floor(5 / 2) = 2 floor(9 / 2) = 4 floor(9 / 5) = 1 ``` -###Example 2 +### Example 2 ``` Input: @nums = (7, 7, 7, 7, 7, 7, 7) Output: 49 ``` --- -###Solution +### Solution Again, using PDL. Creating a 1-d double ndarray from the given numbers: @@ -139,4 +140,4 @@ Finally, sum over this matrix: ``` floor($nums / $nums->dummy(0))->sum; ``` -This works not only for positive integers but for all non-zero integers. \ No newline at end of file +This works not only for positive integers but for all non-zero integers. -- cgit