Challenge 327 Task 1 and 2 solutions in Perl by Matthias Muth

4 files changed, 198 insertions, 117 deletions

diff --git a/challenge-327/matthias-muth/README.md b/challenge-327/matthias-muth/README.md
index 9d30f485fe..212a34d1b8 100644
--- a/challenge-327/matthias-muth/README.md
+++ b/challenge-327/matthias-muth/README.md
@@ -1,176 +1,164 @@
-# Modern Perl's Victory
+# Missing and Mad
 
-**Challenge 326 solutions in Perl by Matthias Muth**
+**Challenge 327 solutions in Perl by Matthias Muth**
 
-## Task 1: Day of the Year
+## Task 1: Missing Integers
 
-> You are given a date in the format YYYY-MM-DD.<br/>
-> Write a script to find day number of the year that the given date represent.
+> You are given an array of n integers.<br/>
+> Write a script to find all the missing integers in the range 1..n in the given array.
 >
 > **Example 1**
 >
 > ```text
-> Input: $date = '2025-02-02'
-> Output: 33
->The 2nd Feb, 2025 is the 33rd day of the year.
-> ```
->
-> **Example 2**
+> Input: @ints = (1, 2, 1, 3, 2, 5)
+> Output: (4, 6)
 >
-> ```text
->Input: $date = '2025-04-10'
-> Output: 100
-> ```
+> The given array has 6 elements.
+> So we are looking for integers in the range 1..6 in the given array.
+> The missing integers: (4, 6)
+>```
 > 
->**Example 3**
+>**Example 2**
 > 
 >```text
-> Input: $date = '2025-09-07'
->Output: 250
+> Input: @ints = (1, 1, 1)
+> Output: (2, 3)
+> ```
+>
+> **Example 3**
+>
+> ```text
+>Input: @ints = (2, 2, 1)
+> Output: (3)
 > ```
 
-It's good to have our superb set of on-board tools — the core modules. For this task, `Time::Piece` helps us to create a one-line solution.
+Checking whether an integer is *missing* is the same
+as checking whether it *exists*, but with a negative result.<br/>
+For checking whether an integer *exists*,
+I use an '*existence hash*'. And this is my standard way of creating one:
 
-The dates we receive as input are ISO date strings. The `strptime` function can easily convert that into a `Time::Piece` object using the `'%F'` format. We can then use the `day_of_year` method (or `yday` for short) to return the day of the year. We just need to add 1 because the result is zero-based, and we want the day numbered from 1 for January 1st.
+```perl
+    my %exists = map { ( $_ => 1 ) } @ints;
+```
 
-As simple as this:
+I can now check the numbers from `1` to `@ints`
+(which in scalar context is the number of elements in `@ints`) 
+for having an entry (or, more precisely, having *no* entry)
+in the *existence hash*.<br/>
+Letting `grep` do that work and directly returning the result
+gives us this two-lines-of-code solution: 
 
 ```perl
 use v5.36;
-use Time::Piece;
 
-sub day_of_the_year( $date ) {
-    return Time::Piece->strptime( $date, "%F" )->day_of_year + 1;
+sub missing_integers( @ints ) {
+    my %exists = map { ( $_ => 1 ) } @ints;
+    return grep ! $exists{$_}, 1..@ints;
 }
 ```
 
-## Task 2: Decompressed List
+## Task 2: MAD
 
-> You are given an array of positive integers having even elements.<br/>
-> Write a script to to return the decompress list. To decompress, pick adjacent pair (i, j) and replace it with j, i times.
+> You are given an array of distinct integers.<br/>
+> Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.
 >
 > **Example 1**
 >
 > ```text
-> Input: @ints = (1, 3, 2, 4)
-> Output: (3, 4, 4)
+> Input: @ints = (4, 1, 2, 3)
+> Output: [1,2], [2,3], [3,4]
+>
+> The minimum absolute difference is 1.
+> Pairs with MAD: [1,2], [2,3], [3,4]
+>
+> ```
+>
+> **Example 2**
+>
+> ```text
+> Input: @ints = (1, 3, 7, 11, 15)
+> Output: [1,3]
 >
-> Pair 1: (1, 3) => 3 one time  => (3)
-> Pair 2: (2, 4) => 4 two times => (4, 4)
->```
-> 
->**Example 2**
-> 
->```text
-> Input: @ints = (1, 1, 2, 2)
-> Output: (1, 2, 2)
-> 
->Pair 1: (1, 1) => 1 one time  => (1)
-> Pair 2: (2, 2) => 2 two times => (2, 2)
 > ```
 >
 > **Example 3**
 >
 > ```text
->Input: @ints = (3, 1, 3, 2)
-> Output: (1, 1, 1, 2, 2, 2)
-> 
-> Pair 1: (3, 1) => 1 three times => (1, 1, 1)
->Pair 2: (3, 2) => 2 three times => (2, 2, 2)
+> Input: @ints = (1, 5, 3, 8)
+> Output: [1,3], [3,5]
 > ```
 
-This task is about walking through an array in steps of 2 elements.<br/>
-I will compare three different implementations:
-
-* 'Conventional' :<br/>
-  Using a C-style `for(;;)` loop to increment the index by 2 for each iteration.<br/>A bit old-style, maybe, and for sure a bit cumbersome that we then need to use the index itself *and* (index + 1) for the pair of elements.
-* 'Elegant':<br/>Using `pairmap` to walk through the elements in pairs makes it a very elegant one-liner.
-* 'Modern':<br/>Since Perl 5.36 you can use a *list* of lexical variables as loop variables.<br/>
-  This makes the loop very intuitive to write (and to read and understand).<br/>And wait to see the benchmark results!
-
-All my solutions are based on
-```perl
-use v5.36;
-```
-to get all kinds of good things, like `use strict`,  `use warnings`,  and subroutine signatures, which I love.<br/>
-And all solutions use the Perl `x` operator to repeat each element the given number of  times, like `( <element> ) x <times>`.
+It is very tempting to read '*find all pairs*' and immediately start thinking about combinatorics and how go through 'all pairs'.
 
-##### Conventional (C-style `for` loop)
+But that is not necessary.
 
-This is my solution using the C-style, three-statement `for` loop.<br/>
-As we loop over the index, we need to do the index dereferencing ourselves.
+The 'minimum absolute difference' will always be between two numbers that are next to each other. So let's first sort the numbers:
 
 ```perl
-sub decompressed_list_c_style_for( @ints ) {
-    my @decompressed;
-    for ( my $i = 0; $i <= $#ints; $i += 2 ) {
-        push @decompressed, ( $ints[ $i + 1 ] ) x $ints[ $i ];
-    }
-    return @decompressed;
-}
+    @ints = sort { $a <=> $b } @ints;
 ```
 
-It works, but it's a bit clumsy.
+Now it quite easy to find the 'minimum absolute difference',
+because it has to be one of the differences between two neighboring numbers.<br/>
+So if we now produce the list of all differences
+between any two *neighboring* numbers
+(for all numbers except for the last one),
+the 'MAD' then will be the minimum of those differences.<br/>
+We don't need to use `abs()`, because the numbers are already sorted,
+so the second one is always greater than or equal to the first one,
+and thus the difference is always non-negative.
 
-##### Elegant (`pairmap`)
-
-Using `pairmap`from the `List::Util` core module results in what probably is the shortest and clearest solution:
+I chose to put the differences into a separate array for clearness,
+and also because I will use the them in the next step:
 
 ```perl
-use List::Util qw( pairmap );
-
-sub decompressed_list_pairmap( @ints ) {
-    return pairmap { ( $b ) x $a } @ints;
-}
+    my @diffs = map $ints[ $_ + 1 ] - $ints[$_], 0..( $#ints - 1 );
+    my $min_diff = min( @diffs );    
 ```
 
-It assigns each pair of values to the `$a` and `$b` special variables and calls its code block. It then returns the combined list of all code block results.<br/>Very nice!
+Now that we have the 'MAD' (in `$min_diff`),
+we need to extract all pairs of numbers
+whose difference is equal to that 'MAD' .<br/>
+We can use `grep` on the indexes of the `@diff` array
+to find all entries that fulfill this condition.
 
-##### Modern (multi-value `for` loop)
+As each of the indexes found also corresponds to
+the position of the two numbers in the sorted array,
+we can extract those two numbers
+and put them into an anonymous array (letting `map` do that).
+We can then directly return the resulting list.
 
-A multi-value `for` loop walks through several elements at once, assigning them to a list of lexical variables (doing aliasing, actually).<br/>We can use those variables directly to build the result. As we use the elements themselves, not the indexes, there's no need to do any dereferencing.
+Maybe it's easier to understand just reading the code:
 
 ```perl
-sub decompressed_list_multi_value_for( @ints ) {
-    my @decompressed;
-    for my ( $n, $i ) ( @ints ) {
-        push @decompressed, ( $i ) x $n;
-    }
-    return @decompressed;
-}
+    return
+        map [ @ints[ $_, $_ + 1 ] ],
+            grep $diffs[$_] == $min_diff,
+                keys @diffs;
 ```
 
-Compared to the C-style `for` loop, this saves a lot of writing and can avoid typical typo errors.<br/>And compared to the `pairmap` solution, it does a lot of things efficiently 'under the hood': It avoids the subroutine call with its need to copy parameters, and I guess that error checking and the assignments to the `$a` and `$b` variables are more expensive than aliasing the lexical variables.
-
-Let's see what the benchmark says:
-
-##### Benchmark
-
-I ran a little benchmark:
+This completes my solution:
 
 ```perl
-cmpthese -3, {
-    c_style_for     => sub { decompressed_list_c_style_for( 3, 1, 3, 2 ); },
-    pairmap         => sub { decompressed_list_pairmap( 3, 1, 3, 2 ); },
-    multi_value_for => sub { decompressed_list_multi_value_for( 3, 1, 3, 2 ); },
-};
-```
-
-with results that astonished me:
-
-```text
-                     Rate         pairmap     c_style_for multi_value_for
-pairmap          999261/s              --            -22%            -41%
-c_style_for     1288603/s             29%              --            -23%
-multi_value_for 1679823/s             68%             30%              --
+use v5.36;
+use List::Util qw( min );
+
+sub mad( @ints ) {
+    @ints = sort { $a <=> $b } @ints;
+    my @diffs = map $ints[ $_ + 1 ] - $ints[$_], 0..( $#ints - 1 );
+    my $min_diff = min @diffs;
+    return
+        map [ @ints[ $_, $_ + 1 ] ],
+            grep $diffs[$_] == $min_diff,
+                keys @diffs;
+}
 ```
 
-The 'modern' solution with the multi-value `for` loop beats all the others!
+If we had compared every number to every other, we would have needed $\frac{n  (n+1)}{2}$
+iterations for computing and comparing that number of differences, resulting in an $O(n^2)$ runtime complexity.
 
-The `pairmap` solution may be the most beautiful, but it definitely isn't the best performing one.
-
-And there's no good reason at all to use the more complicated conventional C-style `for` loop.
-
-Lessons learned!
+This solution's runtime complexity is determined by the
+`sort` operation, and there are only $(n-1)$  differences computed and compared, so the runtime complexity is $O(n \log n)$ .<br/>Glad that we can find MAD pairs in really large lists of numbers now...! :wink::smile:
 
 #### **Thank you for the challenge!**
+
diff --git a/challenge-327/matthias-muth/blog.txt b/challenge-327/matthias-muth/blog.txt
new file mode 100644
index 0000000000..ebf1d4ff52
--- /dev/null
+++ b/challenge-327/matthias-muth/blog.txt
@@ -0,0 +1 @@
+https://github.com/MatthiasMuth/perlweeklychallenge-club/tree/muthm-327/challenge-327/matthias-muth#readme
diff --git a/challenge-327/matthias-muth/perl/ch-1.pl b/challenge-327/matthias-muth/perl/ch-1.pl
new file mode 100755
index 0000000000..25b8e32b87
--- /dev/null
+++ b/challenge-327/matthias-muth/perl/ch-1.pl
@@ -0,0 +1,27 @@
+#!/usr/bin/env perl
+#
+#       The Weekly Challenge - Perl & Raku
+#       (https://theweeklychallenge.org)
+#
+#       Challenge 327 Task 1: Missing Integers
+#
+#       Perl solution by Matthias Muth.
+#
+
+use v5.36;
+
+sub missing_integers( @ints ) {
+    my %exists = map { ( $_ => 1 ) } @ints;
+    return grep ! $exists{$_}, 1..@ints;
+}
+
+use Test2::V0 qw( -no_srand );
+
+is [ missing_integers( 1, 2, 1, 3, 2, 5 ) ], [ 4, 6 ],
+    'Example 1: missing_integers( 1, 2, 1, 3, 2, 5 ) == (4, 6)';
+is [ missing_integers( 1, 1, 1 ) ], [ 2, 3 ],
+    'Example 2: missing_integers( 1, 1, 1 ) == (2, 3)';
+is [ missing_integers( 2, 2, 1 ) ], [ 3 ],
+    'Example 3: missing_integers( 2, 2, 1 ) == 3';
+
+done_testing;
diff --git a/challenge-327/matthias-muth/perl/ch-2.pl b/challenge-327/matthias-muth/perl/ch-2.pl
new file mode 100755
index 0000000000..70c74f4275
--- /dev/null
+++ b/challenge-327/matthias-muth/perl/ch-2.pl
@@ -0,0 +1,65 @@
+#!/usr/bin/env perl
+#
+#       The Weekly Challenge - Perl & Raku
+#       (https://theweeklychallenge.org)
+#
+#       Challenge 327 Task 2: MAD
+#
+#       Perl solution by Matthias Muth.
+#
+
+use v5.36;
+
+use List::Util qw( min );
+
+sub mad( @ints ) {
+    @ints = sort { $a <=> $b } @ints;
+    my @diffs = map $ints[ $_ + 1 ] - $ints[$_], 0..( $#ints - 1 );
+    my $min_diff = min @diffs;
+    return
+        map [ @ints[ $_, $_ + 1 ] ],
+            grep $diffs[$_] == $min_diff,
+                keys @diffs;
+}
+
+sub mad_pairs( @ints ) {
+    @ints = sort { $a <=> $b } @ints;
+    my @pairs = map [ @ints[ $_, $_ + 1 ] ], 0 .. $#ints - 1;
+    my @diffs = map $_->[1] - $_->[0], @pairs;
+    my $min_diff = min( @diffs );
+    return map $pairs[$_], grep $diffs[$_] == $min_diff, keys @diffs;
+}
+
+use List::MoreUtils qw( slide );
+
+sub mad_slide( @ints ) {
+    @ints > 1 or return ();
+    my @pairs = slide { [ $a, $b ] } sort { $a <=> $b } @ints;
+    my @diffs = map $_->[1] - $_->[0], @pairs;
+    my $min_diff = min( @diffs );
+    return map $pairs[$_], grep $diffs[$_] == $min_diff, keys @diffs;
+}
+
+use Test2::V0 qw( -no_srand );
+
+is [ mad() ], [],
+    'Test 1: empty list';
+is [ mad( 5 ) ], [],
+    'Test 2: one element only';
+is [ mad( 4, 1, 2, 3 ) ], [ [1, 2], [2, 3], [3, 4] ],
+    'Example 1: mad( 4, 1, 2, 3 ) == ([1, 2], [2, 3], [3, 4])';
+is [ mad( 1, 3, 7, 11, 15 ) ], [ [1, 3] ],
+    'Example 2: mad( 1, 3, 7, 11, 15 ) == [1, 3]';
+is [ mad( 1, 5, 3, 8 ) ], [ [1, 3], [3, 5] ],
+    'Example 3: mad( 1, 5, 3, 8 ) == ([1, 3], [3, 5])';
+
+done_testing;
+
+use Benchmark qw( cmpthese );
+
+my @ints = ( 1, 3, 7, 11, 15 );
+cmpthese -3, {
+    indices => sub { my @results = mad( @ints ); },
+    pairs   => sub { my @results = mad_pairs( @ints ); },
+    slide   => sub { my @results = mad_slide( @ints ); },
+};