From 6da727106e14eb2316008eca15094569bb4033ef Mon Sep 17 00:00:00 2001 From: Matthias Muth Date: Sat, 28 Jun 2025 18:59:32 +0200 Subject: Challenge 327 Task 1 and 2 solutions in Perl by Matthias Muth --- challenge-327/matthias-muth/README.md | 222 +++++++++++++++---------------- challenge-327/matthias-muth/blog.txt | 1 + challenge-327/matthias-muth/perl/ch-1.pl | 27 ++++ challenge-327/matthias-muth/perl/ch-2.pl | 65 +++++++++ 4 files changed, 198 insertions(+), 117 deletions(-) create mode 100644 challenge-327/matthias-muth/blog.txt create mode 100755 challenge-327/matthias-muth/perl/ch-1.pl create mode 100755 challenge-327/matthias-muth/perl/ch-2.pl 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.
-> Write a script to find day number of the year that the given date represent. +> You are given an array of n integers.
+> 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.
+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*.
+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.
-> 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.
+> 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.
-I will compare three different implementations: - -* 'Conventional' :
- Using a C-style `for(;;)` loop to increment the index by 2 for each iteration.
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':
Using `pairmap` to walk through the elements in pairs makes it a very elegant one-liner. -* 'Modern':
Since Perl 5.36 you can use a *list* of lexical variables as loop variables.
- This makes the loop very intuitive to write (and to read and understand).
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.
-And all solutions use the Perl `x` operator to repeat each element the given number of times, like `( ) x `. +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.
-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.
+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.
+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.
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' .
+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).
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.
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)$ .
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 ); }, +}; -- cgit