Merge pull request #9170 from jo-37/contrib

Solutions to challenge 245

4 files changed, 249 insertions, 0 deletions

diff --git a/challenge-245/jo-37/blog.txt b/challenge-245/jo-37/blog.txt
new file mode 100644
index 0000000000..b6a9859f6a
--- /dev/null
+++ b/challenge-245/jo-37/blog.txt
@@ -0,0 +1 @@
+https://github.com/manwar/perlweeklychallenge-club/blob/master/challenge-245/jo-37/blog/Blog.md
diff --git a/challenge-245/jo-37/blog/Blog.md b/challenge-245/jo-37/blog/Blog.md
new file mode 100644
index 0000000000..584d250c3d
--- /dev/null
+++ b/challenge-245/jo-37/blog/Blog.md
@@ -0,0 +1,102 @@
+# The Most Popular of Three
+
+## Task 1: Sort Language
+**Submitted by: Mohammad S Anwar**
+
+---
+You are given two array of languages and its popularity.
+
+Write a script to sort the language based on popularity.
+
+### Example 1
+```
+Input: @lang = ('perl', 'c', 'python')
+       @popularity = (2, 1, 3)
+Output: ('c', 'perl', 'python')
+```
+### Example 2
+```
+Input: @lang = ('c++', 'haskell', 'java')
+       @popularity = (1, 3, 2)
+Output: ('c++', 'java', 'haskell')
+```
+---
+### Solution
+Performing an index sort on the popularity and using the result as slice indices for the languages leads to a one-line solution:
+```
+sub sort_by_popularity ($lang, $p8y) {
+	$lang->@[sort {$p8y->[$a] <=> $p8y->[$b]} 0 .. $p8y->$#*];
+}
+
+```
+
+## Task 2: Largest of Three
+**Submitted by: Mohammad S Anwar**
+
+---
+You are given an array of integers >= 0.
+
+Write a script to return the largest number formed by concatenating some of the given integers in any order which is also multiple of 3. Return -1 if none found.
+
+### Example 1
+```
+Input: @digits = (8, 1, 9)
+Output: 981
+
+981 % 3 == 0
+
+```
+### Example 2
+```
+Input: @digits = (8, 6, 7, 1, 0)
+Output: 8760
+```
+### Example 3
+```
+Input: @digits = (1)
+Output: -1
+```
+---
+
+### Solution
+Some considerations:
+
+  * The largest number that can be formed from given digits has all the digits in descending order
+  * Any number without leading zeroes is larger than any other number that has less digits.
+  * A number is divisible by 3 if and only if the sum of its decimal digits is divisible by 3.
+
+To form the largest number divisible by 3 from the given digits, we primarily must use the maximum number of digits and secondarily the largest digits.
+Suppose we have `p = sum(d[i]) mod 3`.
+
+  * If `p = 0` we may use all the given digits
+  * If there are digits within the given set having `d = p mod 3`, we may drop the smallest of these digits to get the maximum number.
+  * Otherwise there must be two or more digits having `d = -p mod 3`. We may drop the smallest two of these to get the maximum number.
+
+If the remaining set of digits is not empty, the largest number is formed from the digits in descending order.
+Otherwise there is no solution.
+
+This results in the following implementation:
+```
+sub largest_of_three {
+	my (@digits, @ind, $mod) = sort @_;
+    for (0 .. $#digits) {
+        # The digit modulo 3
+        my $digit = $digits[$_] % 3;
+        # Store indices of digits that are not a multiple of 3
+        push $ind[$digit - 1]->@*, $_ if $digit;
+        # Update the digit sum
+        $mod += $digit;
+    }
+    $mod %= 3;
+    # Delete the fewest smallest digits to obtain a digit sum
+    # divisible by 3.
+    delete @digits[
+        !$mod-- ? () : $ind[$mod] ? $ind[$mod][0] : $ind[!$mod]->@[0, 1]
+    ];
+
+    # Build the maximum number from the remaining digits in descending
+    # order or fail.
+    @digits ? 0 + join '', reverse grep defined, @digits : -1;
+}
+
+```
\ No newline at end of file
diff --git a/challenge-245/jo-37/perl/ch-1.pl b/challenge-245/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..9a77fffc6d
--- /dev/null
+++ b/challenge-245/jo-37/perl/ch-1.pl
@@ -0,0 +1,63 @@
+#!/usr/bin/perl -s
+
+use v5.24;
+use Test2::V0;
+use experimental 'signatures';
+
+our ($tests, $examples, $verbose);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [lang,... popularity,...]
+
+-examples
+    run the examples from the challenge
+
+-tests
+    run some tests
+
+-verbose
+    enable trace output
+
+lang,...
+    list of (comma or blank) separated strings
+
+popularity,...
+    list of (comma or blank) separated numeric popularities
+
+EOS
+
+
+### Input and Output
+
+say "(@{[sort_by_popularity(map [split /[ ,]/], @ARGV)]})";
+
+
+### Implementation
+
+sub sort_by_popularity ($lang, $p8y) {
+	$lang->@[sort {$p8y->[$a] <=> $p8y->[$b]} 0 .. $p8y->$#*];
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is [sort_by_popularity(['perl', 'c', 'python'], [2, 1, 3])],
+            ['c', 'perl', 'python'], 'example 1';
+
+        is [sort_by_popularity(['c++', 'haskell', 'java'], [1, 3, 2])],
+            ['c++', 'java', 'haskell'], 'example 2';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+	}
+
+    done_testing;
+    exit;
+}
diff --git a/challenge-245/jo-37/perl/ch-2.pl b/challenge-245/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..ef90057f91
--- /dev/null
+++ b/challenge-245/jo-37/perl/ch-2.pl
@@ -0,0 +1,83 @@
+#!/usr/bin/perl -s
+
+use v5.24;
+use Test2::V0;
+
+our ($tests, $examples, $verbose);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [D...]
+
+-examples
+    run the examples from the challenge
+
+-tests
+    run some tests
+
+D...
+    list of decimal digits
+
+EOS
+
+
+### Input and Output
+
+say largest_of_three(@ARGV);
+
+
+### Implementation
+
+sub largest_of_three {
+	my (@digits, @ind, $mod) = sort @_;
+    for (0 .. $#digits) {
+        # The digit modulo 3
+        my $digit = $digits[$_] % 3;
+        # Store indices of digits that are not a multiple of 3
+        push $ind[$digit - 1]->@*, $_ if $digit;
+        # Update the digit sum
+        $mod += $digit;
+    }
+    $mod %= 3;
+    # Delete the fewest smallest digits to obtain a digit sum divisible
+    # by 3.
+    delete @digits[
+        !$mod-- ? () : $ind[$mod] ? $ind[$mod][0] : $ind[!$mod]->@[0, 1]
+    ];
+
+    # Build the maximum number from the remaining digits in descending
+    # order or fail.
+    @digits ? 0 + join '', reverse grep defined, @digits : -1;
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is largest_of_three(8, 1, 9), 981, 'example 1';;
+        is largest_of_three(8, 6, 7, 1, 0), 8760, 'example 2';
+        is largest_of_three(1), -1, 'example 3';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        is largest_of_three(6, 4, 3), 63, 'single 1 mod 3';
+        is largest_of_three(6, 5, 3), 63, 'single 2 mod 3';
+        is largest_of_three(6, 4, 4, 3), 63, 'double 1 mod 3';
+        is largest_of_three(6, 5, 5, 3), 63, 'double 2 mod 3';
+        is largest_of_three(6, 3), 63, '0 mod 3';
+        is largest_of_three(1, 1), -1, 'double 1';
+        is largest_of_three(2, 2), -1, 'double 2';
+        is largest_of_three(2), -1, 'like example 3';
+        is largest_of_three(0, 0, 0, 1), 0, 'zero';
+        is largest_of_three(6, 2, 2, 2, 7), 6222, 'remove the largest digit';
+	}
+
+    done_testing;
+    exit;
+}