RabbitFarm
2022-11-06
To a Greater Degree
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1
You are given an array of characters (a..z) and a target character. Write a script to find out the smallest character in the given array lexicographically greater than the target character.
Solution
use v5.36;
use strict;
use warnings;
sub greatest_character{
my($characters, $target) = @_;
return [sort {$a cmp $b} grep {$_ gt $target} @{$characters}]->[0] || $target;
}
MAIN:{
say greatest_character([qw/e m u g/], q/b/);
say greatest_character([qw/d c e f/], q/a/);
say greatest_character([qw/j a r/], q/o/);
say greatest_character([qw/d c a f/], q/a/);
say greatest_character([qw/t g a l/], q/v/);
}
Sample Run
$ perl perl/ch-1.pl
e
c
r
c
v
Notes
Practically a one liner! Here we use grep
to filter out all the characters greater than
the target. The results are then sorted and we return the first one. If all that yields no
result, say there are no characters greater than the target, the just return the target.
Part 2
You are given an array of 2 or more non-negative integers. Write a script to find out the smallest slice, i.e. contiguous subarray of the original array, having the degree of the given array.
Solution
use v5.36;
use strict;
use warnings;
sub array_degree{
my(@integers) = @_;
my @counts;
map { $counts[$_]++ } @integers;
@counts = grep {defined} @counts;
return [sort {$b <=> $a} @counts]->[0];
}
sub least_slice_degree{
my(@integers) = @_;
my @minimum_length_slice;
my $minimum_length = @integers;
my $array_degree = array_degree(@integers);
for my $i (0 .. @integers - 1){
for my $j ($i + 1 .. @integers - 1){
if(array_degree(@integers[$i .. $j]) == $array_degree && @integers[$i .. $j] < $minimum_length){
@minimum_length_slice = @integers[$i .. $j];
$minimum_length = @minimum_length_slice;
}
}
}
return @minimum_length_slice;
}
MAIN:{
say "(" . join(", ", least_slice_degree(1, 3, 3, 2)) . ")";
say "(" . join(", ", least_slice_degree(1, 2, 1)) . ")";
say "(" . join(", ", least_slice_degree(1, 3, 2, 1, 2)) . ")";
say "(" . join(", ", least_slice_degree(1, 1 ,2 ,3, 2)) . ")";
say "(" . join(", ", least_slice_degree(2, 1, 2, 1, 1)) . ")";
}
Sample Run
$ perl perl/ch-2.pl
(3, 3)
(1, 2, 1)
(2, 1, 2)
(1, 1)
(1, 2, 1, 1)
Notes
I view this problem in two main pieces:
Compute the degree of any given array.
Generate all contiguous slices of the given array and looking for a match on the criteria.
So, with that in mind we perform (1) in sub array_degree
and then think of how we might
best compute all those contiguous slices. Here we use a nested for
loop. Since we also
need to check to see if any of the computed slices have an array degree equal to the
starting array we just do that inside the nested loop as well. This way we don't need to
use any extra storage. Instead we just track the minimum length slice with matching array
degree. Once the loops exit we return that minimum length slice.
References
posted at: 18:58 by: Adam Russell | path: /perl | permanent link to this entry