Perl Weekly Challenge: Week 397
Challenge 1:
Absent Smallest Positive
You are given an array of integers.
Write a script to return the smallest absent positive integer such that it is strictly greater than the average of all elements in the given array.
Example 1
Input: @arr = (1, 2, 4, 5, 6)
Output: 7
Average: (1 + 2 + 4 + 5 + 6) / 5 = 3.6
We need the smallest positive integer absent from nums that is strictly greater than 3.6.
The positive integers greater than 3.6 are 4, 5, 6, 7, ....
4 is in the given array.
5 is in the given array.
6 is in the given array.
7 is not in.
Example 2
Input: @arr = (-5, -2, -1, 3)
Output: 1
Average: (-5 -2 -1 + 3) / 4 = -1.25
We need the smallest absent positive integer strictly greater than -1.25.
Positive integers are 1, 2, 3, 4, ... (all are strictly greater than -1.25).
1 is positive and absent from the given array.
Example 3
Input: @arr = (1, 2, 3)
Output: 4
Average: (1 + 2 + 3) / 3 = 2.0
We need an integer strictly greater than 2.0.
3 is in the given array.
4 is not in.
Example 4
Input: @arr = (2, 3, 7, 8)
Output: 6
Average: (2 + 3 + 7 + 8) / 4 = 5.0
We need an integer strictly greater than 5.0.
6 is not in the given array.
Example 5
Input: @arr = (1, 1, 1, 10)
Output: 4
Average: (1 + 1 + 1 + 10) / 4 = 3.25
Positive integers strictly greater than 3.25: 4, 5, 6, ...
4 is not in the given array.
One thing that tripped me up when preparing this solution is that the command-line
arguments which is where I get @arr from are of a type called IntStr For the
rest of this script, we will need them to be Ints. The line of code below converts
them.
@arr = @arr».Int;
Finding the $average is straightforward; we just add together all the elements and
divide by the number of elements as we learned in primary school.
my $average = @arr.sum / @arr.elems;
We $start looking for an answer from the first integer after the average.
my $start = ($average.Int + 1);
There is one small issue to consider; we are looking for the smallest absent positive
integer so if $start is less than 1 (as in e.g. example 2,) we set it to 1.
if $start < 1 {
$start = 1;
}
Now we go through the integers potentially up to infinity.
for $start .. ∞ -> $num {
If the current integer we are looking at is not an element of @arr, we output it and
exit the loop.
if $num ∉ @arr {
say $num;
last;
}
}
For Perl we do things slightly differently. For one thing, we don't have to worry about converting the arguments to integers.
We need a replacement sum() function as Perl doesn't have it. Luckily, it's just
a cut and paste away.
my $average = sum(@arr) / scalar @arr;
Instead of a separate start variable we can use $num to both determine the start
and in the loop that follows.
my $num = int($average) + 1;
if ($num < 1) {
$num = 1;
}
Instead of iterating through a range, we use a while-loop to get consecutive integers.
while (true) {
unless (grep { $_ == $num } @arr) {
say $num;
last;
}
$num++;
}
Challenge 2:
Binary Reflection
You are given an array of integer.
Write a script to sort the given array in ascending order based on the binary reflection of each element. If two different numbers have the same binary reflection, the smaller original number should appear first.
Example 1
Input: @arr = (3, 6, 12)
Output: (3, 6, 12)
Decimal 3 = Binary 11 -> reverse is also same 11 = Decimal 3
Decimal 6 = Binary 110 -> reverse 011 = Decimal 3
Decimal 12 = Binary 1100 -> 0011 = Decimal 3
All three elements have the same binary reflection (3).
Since they tie, they are sorted by their original values in ascending order: (3, 6, 12).
Example 2
Input: @arr = (1, 2, 4, 8)
Output: (1, 2, 4, 8)
Decimal 1 = Binary 1 -> reverse is also same 1 = Decimal 1
Decimal 2 = Binary 10 -> reverse is 01 = Decimal 1
Decimal 4 = Binary 100 -> reverse 001 = Decimal 1
Decimal 8 = Binary 1000 -> reverse is 0001 = Decimal 1
All elements reflect to 1. Tie-breaking by original value yields (1, 2, 4, 8).
Example 3
Input: @arr = (7, 8, 9, 10)
Output: (8, 10, 7, 9)
Decimal 8 = Binary 1000 -> reverse 0001 = Decimal 1
Decimal 9 = Binary 1001 -> reverse 1001 = Decimal 9
Decimal 10 = Binary 1010 -> reverse 0101 = Decimal 5
Decimal 7 = Binary 111 -> reverse 111 = Decimal 7
Binary reflections:
8 -> 1
9 -> 9
10 -> 5
7 -> 7
Sorting by reflection values (1, 5, 7, 9) gives original elements (8, 10, 7, 9).
Example 4
Input: @arr = (5, 9, 15, 17)
Output: (5, 9, 15, 17)
Decimal 5 = Binary 101 -> reverse 101 = Decimal 5
Decimal 9 = Binary 1001 -> reverse 1001 = Decimal 9
Decimal 15 = Binary 1111 -> reverse 1111 = Decimal 15
Decimal 17 = Binary 10001 -> reverse 10001 = Decimal 17
All numbers are binary palindromes, so their reflections match their original decimal values (5, 9, 15, 17),
leaving the array order unchanged.
Example 5
Input: @arr = (11, 13, 14, 19)
Output: (14, 13, 11, 19)
Decimal 11 = Binary 1011 -> reverse 1101 = Decimal 13
Decimal 13 = Binary 1101 -> reverse 1011 = Decimal 11
Decimal 14 = Binary 1110 -> reverse 0111 = Decimal 7
Decimal 19 = Binary 10011 -> reverse 11001 = Decimal 25
Reflections:
14 -> 7
13 -> 11
11 -> 13
19 -> 25
Sorted by reflection values (7, 11, 13, 25) yields (14, 13, 11, 19).
Once again our input is an array of integers that we get from the command line.
We create a Hash called %reflections and for every element in @arr, we convert
it to binary with .base(2), reverse it with .flip() and convert it back into
base 10 with .parse-base(2). So far we have been manipulating strings so we
convert it to an integer with .Int. This value is used as a key in %reflecions
and the original element is a value. There may be multiple values associated with
a single key so we use .push() to treat the values as an array.
my %reflections;
for @arr -> $elem {
%reflections{$elem.base(2).flip.parse-base(2).Int}.push($elem.Int);
}
Now we create an array to hold the @sorted values.
my @sorted;
First we sort the keys of %reflections in ascending numeric order...
for %reflections.keys.sort({ $^a <=> $^b }) -> $k {
...and for each key, we sort the values in ascending numeric order and append
them to @sorted. (We have to "flatten" the values so they are added as elements,
not as an array reference hence |.)
@sorted.push(| %reflections{$k}.values.sort({ $^a <=> $^b }) );
}
Then we print @sorted in the format suggested by the spec.
say q{(}, @sorted.join(q{, }), q{)};
The Perl version doesn't require any extra code, it closely (though more awkwardly IMHO) follows the Raku version.
my %reflections;
for my $e (@arr) {
push @{ $reflections{ oct('0b' . reverse sprintf('%b', $e)) } }, $e;
}
my @sorted;
for my $k ( sort { $a <=> $b } keys %reflections ) {
push @sorted, ( sort { $a <=> $b } @{ $reflections{$k} } );
}
say q{(}, (join q{, }, @sorted), q{)};