THE WEEKLY CHALLENGE – PERL & RAKU #58
TASK #1 › Compare Version
Challenge by Ryan Thompson
Compare two given version number strings v1 and v2 such that:
- If v1 > v2 return 1
- If v1 < v2 return -1
- Otherwise, return 0
The version numbers are non-empty strings containing only digits, and the dot (“.”) and underscore (“_”) characters. (“_” denotes an alpha/development version, and has a lower precedence than a dot, “.”). Here are some examples:
v1 v2 Result
------ ------ ------
0.1 < 1.1 -1
2.0 > 1.2 1
1.2 < 1.2_5 -1
1.2.1 > 1.2_1 1
1.2.1 = 1.2.1 0
Version numbers may also contain leading zeros. You may handle these how you wish, as long as it’s consistent.
Method
When asked to compare two version strings, it’s important to qualify that there is no single methodology out in the wild for versioning. So this is really a task to distinguish and rank within a certain versioning system.
This system uses the common scheme of numbers separated by dots, with the added rule that alpha and other pre-release verions are given an underscore separator rather than a dot; these versions are counted as higher than the previous release they superceed, but lower than that same numbering using dot notation.
It’s not defined exactly where this underscore will lie, but for the sake of completeness we should declare before beginning that 1.2_1 == 1_2.1 == 1_2_1, although I’m sure whoever is using this system would have something to say to their developers on using only one correct form. Best to make any such distinction not matter, to be sure. There are no “double alpha code secret special” versions.
Leading zeroes in a given grouping will have no effect on a numeric sort, so 1.0002.001 > 1.2, which is sort of what one might expect. Only the major release need be defined, to give us something to start with. Leaving the 0 off of 0.9 is a no-no, as writing release .9 leaves way too much room for misreading; this pratice shouldn’t be tolerated by decent, civilized people. Trailing dots and dashes should reasonably result in much head shaking and tut-tuting but the abomination 1.2_ will parse just fine as a prerelease 1.2.
But not _1.2. No, that’s too far by far. Pretty sure will get you fired, or hurt, or both, which again is as it should be. It’s not a private method. It’s a versioning system, not your personal plaything.
Anyways, the numeric relative equality operator <=> already returns 1, 0 or -1, so we’ll be using that whenever we can.
The numeric components of major, minor and point release can be numerically sorted in that order, falling through in granularity if a given level is equal. A level of granularity if left undefined can be considered 0, so in comparing 1.2 with 1.2.3 we first compare 1 with 1; they are equal so we fall through and compare 2 with 2, equal again. Then we compare an undefined value with 1; the undefned value can be considered 0 for this purpose and the 1 value is greater, so we return -1. In other words, the versions 1.2 and 1.2.0 are to be considered the same. Additional sub-point releases will also be handled just fine if we wish to go there: 1.2.1.1 vs. 1.2.1.1.1, whatever it takes. The sky’s the limit.
Only if no clear greater version is determined by this point do we need to evaluate whether either is an alpha release. To do this we can search for an underscore: if either both or neither contain the character, the versions are still declared equal; if only one does, the other version is the greater.
Perl Solution
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN
my $one = '1.02.1';
my $two = '1.2_1';
print compare_versions($one, $two);
## ## ## ## ## SUBS:
sub compare_versions {
my ($v1str, $v2str) = @_;
## isolate the numeric portions
my @v1 = split /[._]/, $v1str;
my @v2 = split /[._]/, $v2str;
my $index_max = @v2 > @v1 ? @v2-1 : @v1-1;
## iterate through the numerical portions by common index
## if a clear winner emerges, return immediately with the decision
for my $index (0..$index_max) {
my $v1 = $v1[$index] // 0;
my $v2 = $v2[$index] // 0;
return $v1 <=> $v2 if ($v1 <=> $v2) != 0; ## -1 or 1
}
## if we are still equal at this point, evaluate dot vs dash releases:
## neither or both are alpha then they are in fact equal
if ( "$v1str$v2str" !~ /_/ or ("$v1str" =~ /_/ and "$v2str" =~ /_/)) {
return 0;
}
elsif ("$v1str" =~ /_/ ) { ## if 1 is alpha 2 is larger
return -1;
}
return 1; ## then 2 is alpha and 1 is larger
}
Raku Solution
The Raku version closely follows the Perl. The sorting logic is the same, so there are only a few language-specific differences.
Anyways, in raku, the numeric relative equality operator <=> returns Less, Equal and More, but if we cast these as .Num, they translate to 1, 0 or -1. This will still be the basis of our routine.
sub MAIN () {
my $one = '1.2.1.1';
my $two = '1.2';
say compare_versions($one, $two);
}
## ## ## ## ## SUBS:
sub compare_versions ($v1str, $v2str) {
## isolate the numeric portions of the version strings
my @v1 = $v1str.split( /<[._]>/ );
my @v2 = $v2str.split( /<[._]>/ );
my $index_max = (@v2 > @v1 ?? @v2 !! @v1).elems;
## iterate through the numerical portions,
## add default value of 0 for comparisons of different length versions
## if a clear winner emerges, return immediately with the decision
for ^$index_max -> $index {
my $v1 = @v1[$index] // 0;
my $v2 = @v2[$index] // 0;
return ($v1 <=> $v2).Num if ($v1 <=> $v2) != 0 ## -1 or 1
}
## if we are still equal at this point, evaluate dot vs dash releases:
## in cases neither or both are alpha releases then they are equal
return 0 unless ($v1str ~~ /_/) ^? ($v2str ~~ /_/);
## if 1 is alpha then 2 is larger
return -1 if ($v1str ~~ /_/ ) ;
## else 2 is alpha and 1 is larger
return 1;
}TASK #2 › Ordered Lineup
Challenge by Ryan Thompson
Write a script to arrange people in a lineup according to how many taller people are in front of each person in line. You are given two arrays. @H is a list of unique heights, in any order. @T is a list of how many taller people are to be put in front of the corresponding person in @H. The output is the final ordering of people’s heights, or an error if there is no solution.
Here is a small example:
@H = (2, 6, 4, 5, 1, 3) # Heights@T = (1, 0, 2, 0, 1, 2) # Number of taller people in front
The ordering of both arrays lines up, so H[i] and T[i] refer to the same person. For example, there are 2 taller people in front of the person with height 4, and there is 1 person in front of the person with height 1.
Here is a diagram of the input arrays @H and @T:
Finally, here is one possible solution that satisfies @H and @T:
As per the last diagram, your script would then output the ordering (5, 1, 2, 6, 3, 4) in this case. (The leftmost element is the “front” of the array.)
Method
I have to admit this one threw me for a loop for a while. After taking the requisite time just to understand the challenge posed, I at first became convinced the solution lay in some reconfigured sort algorithm. Something involving selectively swapping pairs of people in line and making successive passes over the list until no more rearrangement was required. That sounded… messy.
One thing was clear from the outset, that the first thing to do would be to sort the people by height from tallest to shortest. Since heights are defined to be unique, we can refer to individuals by their height. To preserve synchronization with the parallel array of people in front, it would be necessary to either make matching moves of those indices too, or record the association in a hash for future reference.
Once I had the people sorted by height, it became clear that if the input required more people to be in front of a given person than there were individuals taller than that person, the dataset would not be solvable; that number, the people in front, directly relates to the index of the person in the sorted line. In fact they were the same.
Now we were getting somewhere. If the number of people required to be in front was always less than or equal to the number of people taller than that person, which in turn was that person’s index in the sorted line, then any movement of that person in the line to the sorted position must be toward the front of the line in all cases.
Furthermore, if people are only being moved in one direction, towards the front, then the number of people taller than a person in the line will never change, and the index of a given person remains constant, as long as all rearragement of the line involves people taller than themselves.
Therefore if we rearrange the people in line starting with the tallest, proceding in descending order, upon arrival of a given person’s time to move, all people in front of that person will still be taller, and that person will only need to move forward a number of positions to leave the required number of taller people in front of them. The starting number of people taller is the index of that person, and any given person has a lookup of the required number of taller people, so that person needs to move
index - taller_than_lookup
spaces forward to the correct spot. But as the index of a person does not alter by the rearrangements of any people before their given turn, the final placement index of a person is determined by
index - (index - taller_than_lookup)
which is simply the value of the taller_than lookup.
What started seeming quite complex has turned out to be remarkably simple: After preserving the association between heights and the required number of taller people in front in a lookup, we sort the line from tallest to shortest. Then we proceed down this line starting with the tallest, moving each person in turn to the new index determined by the lookup. That’s it. When we have moved every person we are done.
Perl Solution
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
## @heights elems are unique
my @heights = (
27, 21, 37, 4, 19, 52, 23, 64, 1, 7, 51, 17, 24, 50, 3, 2,
34, 40, 47, 20, 8, 56, 14, 16, 42, 38, 62, 53, 31, 41, 55, 59,
48, 12, 32, 61, 9, 60, 46, 26, 58, 25, 15, 36, 11, 44, 63, 28,
5, 54, 10, 49, 57, 30, 29, 22, 35, 39, 45, 43, 18, 6, 13, 33
);
# Number taller people in front
my @taller_than = (
6, 41, 1, 49, 38, 12, 1, 0, 58, 47, 4, 17, 26, 1, 61, 12,
29, 3, 4, 11, 45, 1, 32, 5, 9, 19, 1, 4, 28, 12, 2, 2,
13, 18, 19, 3, 4, 1, 10, 16, 4, 3, 29, 5, 49, 1, 1, 24,
2, 1, 38, 7, 7, 14, 35, 25, 0, 5, 4, 19, 10, 13, 4, 12
);
my %in_front;
## load the parallel arrays with a hash slice
@in_front{@heights} = @taller_than;
my @ordered_lineup = sort {$b <=> $a} @heights;
## iterate through the indices
for my $idx (0..scalar(@heights) - 1) {
## if the sort requires more people in front than are in fact taller,
## the group cannot be sorted
unless ($in_front{$ordered_lineup[$idx]} <= $idx) {
die "there is no solution to this problem!"
}
## find the position to reinsert the person
my $insert_index = $in_front{$ordered_lineup[$idx]};
next if $idx == $insert_index; ## nop and jump
## remove the person from this index and reinsert at the new index
splice(@ordered_lineup, $insert_index, 0, ( splice(@ordered_lineup, $idx, 1) ) );
}
say join ', ', @ordered_lineup;Raku Solution
For output, Raku provides the rotor() method, which allows us to pretty-print the solution array into a much more digestable 16 columns, evenly formatted and spaced. By applying the same treatment to the provided answer, it is straightforward to compare the two and see that they are the same.
sub MAIN () {
## @heights elems are unique so we can distinguish persons by height
my @heights =
27, 21, 37, 4, 19, 52, 23, 64, 1, 7, 51, 17, 24, 50, 3, 2,
34, 40, 47, 20, 8, 56, 14, 16, 42, 38, 62, 53, 31, 41, 55, 59,
48, 12, 32, 61, 9, 60, 46, 26, 58, 25, 15, 36, 11, 44, 63, 28,
5, 54, 10, 49, 57, 30, 29, 22, 35, 39, 45, 43, 18, 6, 13, 33;
# Number taller people in front
my @taller_than =
6, 41, 1, 49, 38, 12, 1, 0, 58, 47, 4, 17, 26, 1, 61, 12,
29, 3, 4, 11, 45, 1, 32, 5, 9, 19, 1, 4, 28, 12, 2, 2,
13, 18, 19, 3, 4, 1, 10, 16, 4, 3, 29, 5, 49, 1, 1, 24,
2, 1, 38, 7, 7, 14, 35, 25, 0, 5, 4, 19, 10, 13, 4, 12;
my %in_front;
## load the parallel hashes with a hash slice
%in_front{@heights} = @taller_than;
my @ordered_lineup = @heights.sort: {$^b <=> $^a} ;
## iterate through the indices
for ^@heights.elems -> $idx {
## if the sort requires more people in front than are in fact taller, the group cannot be sorted
if %in_front{@ordered_lineup[$idx]} > $idx { die "there is no solution to this problem!"}
## find the position to reinsert the person
my $insert_index = %in_front{@ordered_lineup[$idx]};
next if $idx == $insert_index; ## nop and jump
## remove the person from this index and reinsert at the new index
splice(@ordered_lineup, $insert_index, 0, ( splice(@ordered_lineup, $idx, 1) ) );
}
## pretty print as 16 columns
.fmt("%2d", ", ").say for @ordered_lineup.rotor(16);
my @given_answer =
35, 23, 5, 64, 37, 9, 13, 25, 16, 44, 50, 40, 2, 27, 36, 6,
18, 54, 20, 39, 56, 45, 12, 47, 17, 33, 55, 30, 26, 51, 42, 53,
49, 41, 32, 15, 22, 60, 14, 46, 24, 59, 10, 28, 62, 38, 58, 63,
8, 48, 4, 7, 31, 19, 61, 43, 57, 11, 1, 34, 21, 52, 29, 3;
say "given answer:";
.fmt("%2d", ", ").say for @given_answer.rotor(16);
}
Programming Excursions in Perl and Raku 