RabbitFarm
2022-09-18
Deepest Common Index
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1
You are given a list of integers. Write a script to find the index of the first biggest number in the list.
Solution
use v5.36;
use strict;
use warnings;
sub index_biggest{
my(@numbers) = @_;
my @sorted = sort {$b <=> $a} @numbers;
map { return $_ if $numbers[$_] == $sorted[0] } 0 .. @numbers - 1;
}
MAIN:{
my @n;
@n = (5, 2, 9, 1, 7, 6);
print index_biggest(@n) . "\n";
@n = (4, 2, 3, 1, 5, 0);
print index_biggest(@n) . "\n";
}
Sample Run
$ perl perl/ch-1.pl
2
4
Notes
Essentially this solution is two lines, and could even have been a one liner. All that is
required is to sort
the array of numbers and then determine the index of the first
occurrence of the largest value from the original list. Finding the index of the first
occurrence can be done using a map
with a return
to short circuit the search as soon
as the value is found.
Part 2
Given a list of absolute Linux file paths, determine the deepest path to the directory that contains all of them.
Solution
use v5.36;
use strict;
use warnings;
sub deepest_path{
my(@paths) = @_;
my @sub_paths = map { [split(/\//, $_)] } @paths;
my @path_lengths_sorted = sort { $a <=> $b } map { 0 + @{$_} } @sub_paths;
my $deepest_path = q//;
for my $i (0 .. $path_lengths_sorted[0] - 1){
my @column = map { $_->[$i] } @sub_paths;
my %h;
map { $h{$_} = undef } @column;
$deepest_path .= (keys %h)[0] . q#/# if 1 == keys %h;
}
chop $deepest_path;
return $deepest_path;
}
MAIN:{
my $data = do{
local $/;
<DATA>;
};
my @paths = split(/\n/, $data);
print deepest_path(@paths) . "\n";
}
__DATA__
/a/b/c/1/x.pl
/a/b/c/d/e/2/x.pl
/a/b/c/d/3/x.pl
/a/b/c/4/x.pl
/a/b/c/d/5/x.pl
Sample Run
$ perl perl/ch-2.pl
/a/b/c
Notes
The approach here is fairly straightforward but I will admit that it may look more complex than it truly is if you simply glance at the code.
To summarize what is going on here:
- We read in the file paths, one path (string) per line.
- The paths are sent to
deepest_path()
where we create a 2d array. Each array element is an array reference of file sub paths. For example here$sub_paths[0]
is[a, b, c, 1, x.pl]
. - We sort the lengths of all the sub path array references to know how far we must search. We need only look as far as the shortest path after all.
- At each iteration we take column wise slices.
- For each column wise slice we check if all the sub paths are equal. We do this but putting all the sub path values into a hash as keys. If we have only one key value when done we know all the values are equal.
- As long as tall the sub paths are equal we accumulate it in
$deepest_path
. $deepest_path
is returned when we are doing examining all sub paths. (Wechop
the trailing/
). Done!
References
posted at: 20:17 by: Adam Russell | path: /perl | permanent link to this entry