From c89693c8ba13511dbb0d3bf822746baba001fc0f Mon Sep 17 00:00:00 2001 From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com> Date: Wed, 29 Nov 2023 22:38:57 +0100 Subject: Solution to task 1 --- challenge-245/jo-37/perl/ch-1.pl | 63 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100755 challenge-245/jo-37/perl/ch-1.pl 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 <@[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; +} -- cgit From 3880b0e464098d9540469d6045cfb920af6e0573 Mon Sep 17 00:00:00 2001 From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com> Date: Wed, 29 Nov 2023 22:39:12 +0100 Subject: Solution to task 2 --- challenge-245/jo-37/perl/ch-2.pl | 83 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 83 insertions(+) create mode 100755 challenge-245/jo-37/perl/ch-2.pl 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 <@*, $_ 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; +} -- cgit From a412f0e1138a07b8315da13c12caff0676093efd Mon Sep 17 00:00:00 2001 From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com> Date: Wed, 29 Nov 2023 22:39:53 +0100 Subject: Blog for challenge 245 --- challenge-245/jo-37/blog.txt | 1 + challenge-245/jo-37/blog/Blog.md | 102 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 103 insertions(+) create mode 100644 challenge-245/jo-37/blog.txt create mode 100644 challenge-245/jo-37/blog/Blog.md 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 -- cgit