The Weekly Challenge - 250 (January 1st 2024)
Task #1: Smallest Index
You are given an array of integers, @ints. Write a script to find the smallest index i such that i mod 10 == $ints[i] otherwise return -1.
Example 1
Input: @ints = (0, 1, 2) Output: 0
i=0: 0 mod 10 = 0 == $ints[0].i=1: 1 mod 10 = 1 == $ints[1].i=2: 2 mod 10 = 2 == $ints[2].
All indices have i mod 10 == $ints[i], so we return the smallest index 0.
Example 2
Input: @ints = (4, 3, 2, 1) Output: 2
i=0: 0 mod 10 = 0 != $ints[0].i=1: 1 mod 10 = 1 != $ints[1].i=2: 2 mod 10 = 2 == $ints[2].i=3: 3 mod 10 = 3 != $ints[3]..
2 is the only index which has i mod 10 == $ints[i].
Example 3
Input: @ints = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] Output: -1
No index satisfies i mod 10 == $ints[i].
Solution(s)
The solution is to loop through the numbers and comparing index to value (mod 10).
If they match we return the index o/w we return -1.
In the first example – we use “vanilla perl”… and the && trick to embed and if inside a postfix for loop.
In the second we use first from the package List::Util. We wrap this in parentheses and use // to convert the undef value returned if there is no match to a -1.
250-smallest-index.pl - perl
use List::Util qw(first);
sub smallest_index {
($_%10 == $_[$_]) && (return $_) for 0..$#_;
-1
}
sub smallest_index_first {
( first { $_%10 == $_[$_] } 0..$#_ )//-1
}
Performance
Having run a few tests the performance of the first solution is approx 15% faster on the examples provided.
txt
Rate si2 si1
si2 51974/s -- -15%
si1 61264/s 18% --
Timings include additional examples.
Key: si1 (smallest_index) and si2 (smallest_index_first).
Task #2: Alphanumeric String Value
You are given an array of alphanumeric strings. Write a script to return the maximum value of alphanumeric string in the given array.
The value of alphanumeric string can be defined as the numeric representation of the string in base 10 if it is made up of digits only OR the length of the string.
Example 1
Input: @alphanumstr = ("perl", "2", "000", "python", "r4ku")
Output: 6
- “perl” consists of letters only so the value is 4.
- “2” is digits only so the value is 2.
- “000” is digits only so the value is 0.
- “python” consits of letters so the value is 6.
- “r4ku” consists of letters and digits so the value is 4 (length not 4).
Example 2
Input: @alphanumstr = ("001", "1", "000", "0001")
Output: 1
3 values all evaluate to 1.
Solution(s)
We are again going to look at solutions both use “vanilla perl” and List::Util‘s function max.
This is again a simple loop through the values finding the maximum. I present 5 versions which have basically the same logic (look at one of the two longform solutions to see what that is). But we try:
- Long form (with the inner loop tmp variable declared inside the loop)
- Long form (with the inner loop tmp variable declared outside the loop)
- Using map to get the value of each value and then obtaining the maximum (with max)
- Using map to get the value of each value and then obtaining the maximum with pure perl
- Using a nasty compound statement with a for loop, using “
,” and “&&” to replace;andif
250-alphanumeric-string-value.pl - perl
sub alphanumeric_string_value {
my( $z,$t )=0;
( $t=/\D/ ? length : 0+$_ ), ( $t>$z ) && ( $z=$t ) for @_;
$z
}
sub alphanumeric_string_value_map {
my $z = 0;
( $_>$z ) && ( $z=$_ ) for map { /\D/ ? length : 0 + $_ } @_;
$z
}
sub alphanumeric_string_value_max {
max map { /\D/ ? length $_ : 0 + $_ } @_
}
sub alphanumeric_string_value_longform_my {
my $z = 0;
for(@_) {
my $t = /\D/ ? length$_ : 0+$_;
$z=$t if $z<$t;
}
$z
}
sub alphanumeric_string_value_longform {
my($z,$t) = 0;
for(@_) {
$t = /\D/ ? length$_ : 0+$_;
$z=$t if $z<$t;
}
$z
}
Performance
Again we test performance. Again the most naïve solution comes out on top. The map solution is worst – this is probably because perl creates a new copy of the array and doesn’t optimize the code and not just chain the value into the comparison. The max solution almost certainly suffers from the same problem.
For completeness I’ve included a long form of the first version using a for loop with a separate if, rather than the “compound” statement – I include two versions one with the my $t within the loop and one without. First we notice that the one without is faster than the one within.
We note both are more performant than the map version, the faster one is on par with the max solution, but not as fast as the compound statement solution.
txt
Rate asv2 asv4 asv3 asv5 asv1
asv2 18181/s -- -7% -13% -16% -16%
asv4 19460/s 7% -- -7% -10% -10%
asv3 20859/s 15% 7% -- -3% -4%
asv5 21607/s 19% 11% 4% -- -0%
asv1 21707/s 19% 12% 4% 0% --
Timings include additional examples.
Key:
- asv1(alphanumeric_string_value),
- asv2(alphanumeric_string_value_map),
- asv3(alphanumeric_string_value_max),
- asv4(alphanumeric_string_value_longform_my),
- asv5(alphanumeric_string_value_longform).
About The Weekly Challenge
The weekly challenge was set up Mohammad Anwar approximately 5 years ago - each Monday two problems are set for the "team" to solve.
These are posted at: