diff options
| -rw-r--r-- | challenge-284/matthias-muth/README.md | 136 | ||||
| -rw-r--r-- | challenge-284/matthias-muth/blog.txt | 1 | ||||
| -rwxr-xr-x | challenge-284/matthias-muth/perl/ch-1.pl | 28 | ||||
| -rwxr-xr-x | challenge-284/matthias-muth/perl/ch-2.pl | 30 |
4 files changed, 146 insertions, 49 deletions
diff --git a/challenge-284/matthias-muth/README.md b/challenge-284/matthias-muth/README.md index edfc0dbc11..1c228a6fab 100644 --- a/challenge-284/matthias-muth/README.md +++ b/challenge-284/matthias-muth/README.md @@ -1,82 +1,120 @@ -# Find the function to find the numbers +# Use `frequency` frequently! -**Challenge 283 solutions in Perl by Matthias Muth** +**Challenge 284 solutions in Perl by Matthias Muth** -## Task 1: Unique Number +Making use of `frequency` from `List::MoreUtils` gives us nice and short results for both challenges! -> You are given an array of integers, @ints, where every elements appears more than once except one element.<br/> -> Write a script to find the one element that appears exactly one time.<br/> +## Task 1: Lucky Integer + +> You are given an array of integers, @ints.<br/> +> Write a script to find the lucky integer if found otherwise return -1. If there are more than one then return the largest.<br/> +> A lucky integer is an integer that has a frequency in the array equal to its value.<br/> > <br/> > Example 1<br/> -> Input: @ints = (3, 3, 1)<br/> -> Output: 1<br/> +> Input: @ints = (2, 2, 3, 4)<br/> +> Output: 2<br/> > <br/> > Example 2<br/> -> Input: @ints = (3, 2, 4, 2, 4)<br/> +> Input: @ints = (1, 2, 2, 3, 3, 3)<br/> > Output: 3<br/> > <br/> > Example 3<br/> -> Input: @ints = (1)<br/> -> Output: 1<br/> -> <br/> -> Example 4<br/> -> Input: @ints = (4, 3, 1, 1, 1, 4)<br/> -> Output: 3<br/> - -Once again, we can let `List::MoreUtils` do the work for us. -In this case, we use its `singleton` function, which extracts and returns those elements from a list that exist *exactly once* in that list. So if there actually is 'one element that appears exactly one time', `singleton @ints` will return it as the first (and only!) element of the return values. Perfect! - -The specification says we need to 'to find *the one* element that appears exactly one time'.<br/> -If we don't find *the one* element, we won't return anything. And my interpretation of '*the one*' is that if there is *more than one* such element, we should not return anything either. - -So here we go: +> Input: @ints = (1, 1, 1, 3)<br/> +> Output: -1<br/> + +For comparing the numbers in the `@ints` array to their own frequency in that array, +we need to compute the frequencies first. +Obviously. +`List::MoreUtils` is our friend, once again, because its `frequency` function does exactly that. +It returns a list of $( value, frequency )$ pairs, +which we can simply assign to a hash, and there we are. + +Now we need to find the 'lucky integer', +and if we happen to find more than one we are supposed to return the highest one. +So we put together a chain: + +* `grep` with a 'lucky' condition + (the current number's frequency is the same as the number itself), + applied on all existing numbers.<br/> + We use `keys %freq` for the set of numbers, to make sure to check all numbers, but only once. +* Get the highest number of the result.<br/> + Using `max` from `List::Util` for this. +* If there is no lucky number at all, `max` will return `undef`.<br/> + We use the defined-or operator (`//`) to return a `-1` in that case. + +So we got our solution in two lines of code: ```perl use v5.36; +use List::MoreUtils qw( frequency ); +use List::Util qw( max ); -use List::MoreUtils qw( singleton ); - -sub unique_number( @ints ) { - my @s = singleton( @ints ); - return @s == 1 ? $s[0] : (); +sub lucky_integer( @ints ) { + my %freq = frequency( @ints ); + return max( grep $freq{$_} == $_, keys %freq ) // -1; } ``` -## Task 2: Digit Count Value +## Task 2: Relative Sort -> You are given an array of positive integers, @ints.<br/> -> Write a script to return true if for every index i in the range 0 <= i < size of array, the digit i occurs exactly the \$ints[\$i] times in the given array otherwise return false.<br/> +> You are given two list of integers, @list1 and @list2. The elements in the @list2 are distinct and also in the @list1.<br/> +> Write a script to sort the elements in the @list1 such that the relative order of items in @list1 is same as in the @list2. Elements that is missing in @list2 should be placed at the end of @list1 in ascending order.<br/> > <br/> > Example 1<br/> -> Input: @ints = (1, 2, 1, 0)<br/> -> Ouput: true<br/> -> \$ints[0] = 1, the digit 0 occurs exactly 1 time.<br/> -> \$ints[1] = 2, the digit 1 occurs exactly 2 times.<br/> -> \$ints[2] = 1, the digit 2 occurs exactly 1 time.<br/> -> \$ints[3] = 0, the digit 3 occurs 0 time.<br/> +> Input: @list1 = (2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5)<br/> +> @list2 = (2, 1, 4, 3, 5, 6)<br/> +> Ouput: (2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9)<br/> > <br/> > Example 2<br/> -> Input: @ints = (0, 3, 0)<br/> -> Ouput: false<br/> -> \$ints[0] = 0, the digit 0 occurs 2 times rather than 0 time.<br/> -> \$ints[1] = 3, the digit 1 occurs 0 time rather than 3 times.<br/> -> \$ints[2] = 0, the digit 2 occurs exactly 0 time.<br/> +> Input: @list1 = (3, 3, 4, 6, 2, 4, 2, 1, 3)<br/> +> @list2 = (1, 3, 2)<br/> +> Ouput: (1, 3, 3, 3, 2, 2, 4, 4, 6)<br/> +> <br/> +> Example 3<br/> +> Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1)<br/> +> @list2 = (1, 0, 3, 2)<br/> +> Ouput: (1, 1, 1, 0, 0, 3, 2, 4, 5)<br/> + +Seems that our result set consists of two parts: -We need to count how often every number appears in the array before we can compare those frequencies to the entries in the `@ints` array. I'm making it easy using the `frequency` function, again from `List::MoreUtils`. It returns a list of ( value, frequency ) pairs, which can directly be assigned to a hash. +* first, all numbers from `@list1` that also are in `@list2`, in the order that is given by `@list2`, +* then, the numbers that are *not* in `@list2`, sorted in ascending order, from low to high. -Once we have that frequency hash, we use `List::Util`'s `all` function to check all the needed equalities. Index values that don't appear in the `@int` array should have a frequency of zero. But as they are not seen, and therefore not counted at all, they don't even get an entry in the frequency hash. We take care of these missing values by a 'defined-or' with a zero. +We will put the two parts together in the end, but first we need to find a way to construct each of them. -`all`'s return value then is our result. Easy enough! +For the numbers 'in the order of `@list2`', we actually can *use* `@list2`. That already gives us each number once, and for sure they are in the correct order!<br/> +We only need to *repeat* each number as many times as it appears in `@list1`. + +So we are back to counting numbers again, and again, we use the `frequency` function from `List::MoreUtils` to keep it short.<br/>The first part of our result then simply is each number from `@list2`, repeated by its frequency in `@list1`: ```perl -use v5.36; + my %freq1 = frequency( $list1->@* ); + map( ( $_ ) x $freq1{$_}, $list2->@* ) +``` + +For the second part, we need to use `@list1`, but exclude the numbers from `@list2`, because we already have dealt with those. + +For simplicity, I use `frequency` again to built an 'existence hash' for `@list2`. Knowing that every number there appears only once, all the frequencies will be 1, but that's exactly what I need. + +The second part then is `@list1`, with any element `grep`ped away that exists in `@list2`, then sorted numerically: +```Perl + my %exists2 = frequency( $list2->@* ); + sort { $a <=> $b } grep ! $exists2{$_}, $list1->@* +``` + +Which gives us a solution with a high frequency of `frequency`. :-) + +```perl +use v5.36; use List::MoreUtils qw( frequency ); -use List::Util qw( all ); -sub digit_count_value( @ints ) { - my %f = frequency @ints; - return all { ( $f{$_} // 0 ) == $ints[$_] } 0..$#ints; +sub relative_sort( $list1, $list2 ) { + my %freq1 = frequency( $list1->@* ); + my %exists2 = frequency( $list2->@* ); + return + map( ( $_ ) x $freq1{$_}, $list2->@* ), + sort { $a <=> $b } grep ! $exists2{$_}, $list1->@*; } ``` diff --git a/challenge-284/matthias-muth/blog.txt b/challenge-284/matthias-muth/blog.txt new file mode 100644 index 0000000000..146f7ac482 --- /dev/null +++ b/challenge-284/matthias-muth/blog.txt @@ -0,0 +1 @@ +https://github.com/MatthiasMuth/perlweeklychallenge-club/tree/muthm-284/challenge-284/matthias-muth#readme diff --git a/challenge-284/matthias-muth/perl/ch-1.pl b/challenge-284/matthias-muth/perl/ch-1.pl new file mode 100755 index 0000000000..93074c7b94 --- /dev/null +++ b/challenge-284/matthias-muth/perl/ch-1.pl @@ -0,0 +1,28 @@ +#!/usr/bin/env perl +# +# The Weekly Challenge - Perl & Raku +# (https://theweeklychallenge.org) +# +# Challenge 284 Task 1: Lucky Integer +# +# Perl solution by Matthias Muth. +# + +use v5.36; + +use List::MoreUtils qw( frequency ); +use List::Util qw( max ); + +sub lucky_integer( @ints ) { + my %freq = frequency( @ints ); + return max( grep $freq{$_} == $_, keys %freq ) // -1; +} + +use Test2::V0 qw( -no_srand ); +is lucky_integer( 2, 2, 3, 4 ), 2, + 'Example 1: lucky_integer( 2, 2, 3, 4 ) == 2'; +is lucky_integer( 1, 2, 2, 3, 3, 3 ), 3, + 'Example 2: lucky_integer( 1, 2, 2, 3, 3, 3 ) == 3'; +is lucky_integer( 1, 1, 1, 3 ), -1, + 'Example 3: lucky_integer( 1, 1, 1, 3 ) == -1'; +done_testing; diff --git a/challenge-284/matthias-muth/perl/ch-2.pl b/challenge-284/matthias-muth/perl/ch-2.pl new file mode 100755 index 0000000000..d83046651d --- /dev/null +++ b/challenge-284/matthias-muth/perl/ch-2.pl @@ -0,0 +1,30 @@ +#!/usr/bin/env perl +# +# The Weekly Challenge - Perl & Raku +# (https://theweeklychallenge.org) +# +# Challenge 284 Task 2: Relative Sort +# +# Perl solution by Matthias Muth. +# + +use v5.36; + +use List::MoreUtils qw( frequency ); + +sub relative_sort( $list1, $list2 ) { + my %freq1 = frequency( $list1->@* ); + my %exists2 = frequency( $list2->@* ); + return + map( ( $_ ) x $freq1{$_}, $list2->@* ), + sort { $a <=> $b } grep ! $exists2{$_}, $list1->@*; +} + +use Test2::V0 qw( -no_srand ); +is [ relative_sort( [2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5], [2, 1, 4, 3, 5, 6] ) ], [ 2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9 ], + 'Example 1: relative_sort( [2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5], [2, 1, 4, 3, 5, 6] ) == (2, 2, 1, 4, 3, 3, 5 .. 9)'; +is [ relative_sort( [3, 3, 4, 6, 2, 4, 2, 1, 3], [1, 3, 2] ) ], [ 1, 3, 3, 3, 2, 2, 4, 4, 6 ], + 'Example 2: relative_sort( [3, 3, 4, 6, 2, 4, 2, 1, 3], [1, 3, 2] ) == (1, 3, 3, 3, 2, 2, 4, 4, 6)'; +is [ relative_sort( [3, 0, 5, 0, 2, 1, 4, 1, 1], [1, 0, 3, 2] ) ], [ 1, 1, 1, 0, 0, 3, 2, 4, 5 ], + 'Example 3: relative_sort( [3, 0, 5, 0, 2, 1, 4, 1, 1], [1, 0, 3, 2] ) == (1, 1, 1, 0, 0, 3, 2, 4, 5)'; +done_testing; |