Wherein we learn to dance in squares and do-si-do our partners, in the manner Dr. John Lilly referred to as the “Dyadic Cyclone“
THE WEEKLY CHALLENGE – PERL & RAKU #77
episode 1
“The Shot Caller”
TASK #1 › Leader Element
Submitted by: Mohammad S Anwar
You are given an array @A containing distinct integers.
Write a script to find all leader elements in the array @A. Print (0) if none found.
An element is leader if it is greater than all the elements to its right side.
Example 1:
Input: @A = (9, 10, 7, 5, 6, 1)
Output: (10, 7, 6, 1)
Example 2:
Input: @A = (3, 4, 5)
Output: (5)
Method
When looking for a leader, the first inclination might be to look to the top. After all, it’s lonely there (see last week’s challenge) and by all rights they should be easy to spot, right? Be that as it may, the qualifications laid for this challenge require knowledge of the followers first, those behind our leaders, and so that is where we will start our search, at the bottom, the end of the array.
Working from the end, the lowliest element at the tail is by definition the leader of none, yet a leader nonetheless. Something, as they say, is always more than nothing. From that point onward, the value of this leader becomes the one to beat. Until, of course, it’s beaten by the next leader. So a running local maximum is established among the elements already seen, and the focus moves one element to the left; if the element to the left is greater than the current maximum, then it too is declared a leader and it becomes the new maximum. In this way we proceed leftwards until we arrive at the first index and are done.
A list of leaders is kept as they are found. This list, because we are working forward from the back, is built in a similar fashion, by appending new elements to the front, rather than the back. Every element output is had been determined to be a leader among elements, but in doing things this way the order of the original list will also be maintained.
The output list will end up sorted, with the largest element to the left. Obviously, according a recursive definition of the criteria, this leftmost value will be King of some sort, the leader amongst leaders. The complete chain of command has been conclusively established, as demonstrated in the sequence of the output list.
Perl Solution
As there’s no pressing reason to keep the input array around after the fact, we can destructively process it by popping elements off the end one-by-one until there’s nothing left.
I’ve quite pleased with the initial output array and maximum value assignment; the parentheses define list context throughout. The variables need to be declared anyway, with $max to negative infinity, so why not assign them starting values and be done with it? Here or there, it’s one less iteration for the loop when done this way.
~/PWC/78_1_follow_the_leader.pl
--------------------------------------------------------------------------------
input: (9, 10, 7, 5, 6, 1)
output: (10, 7, 6, 1)
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
my @input = @ARGV;
@input = (9, 10, 7, 5, 6, 1) if scalar @ARGV == 0;
say "input: (", (join ', ', @input), ")";
my @output = my ($max) = (pop @input);
while (@input) {
my $ele = pop @input;
if ($ele > $max) {
$max = $ele;
unshift @output, $ele;
}
}
say "output: (", (join ', ', @output), ")";
Raku Solution
In Raku we’ll just use a chain of methods to accomplish our goals. We do run into a similar problem as that of the other week with lazy evaluation in the map loops if we chain too far, so we need to break up the reversing into two distinct phases. Chaining another .reverse on the end yields a list of 10s, the highest value, and that’s obviously wrong. It appears manipulating outside data within a map block is a fundamentally messy thing, which is a shame, because it’s so useful. I’m not willing to admit defeat here, and I’ll have to keep working on a better approach so that things always turn out the way I think they should.
~/PWC/78-1-follow-the-leader.raku
--------------------------------------------------------------------------------
input: [9 10 7 5 6 1]
output: [10 7 6 1]
unit sub MAIN (*@input) ;
## in
@input.elems == 0 and @input = 9, 10, 7, 5, 6, 1;
## work
my $max = -Inf;
my @output = @input.reverse
.map( { $_ > $max ?? ($max = $_) !! Nil } )
.grep( *.defined );
@output .= reverse;
## out
say " input: ", @input;
say "output: ", @output;
episode 2
“One is the Loneliest Number”
TASK #2 › Left Rotation
Submitted by: Mohammad S Anwar
You are given array @A containing positive numbers and @B containing one or more indices from the array @A.
Write a script to left rotate @A so that the number at the first index of @B becomes the first element in the array. Similary, left rotate @A again so that the number at the second index of @B becomes the first element in the array.
Example 1:
Input:
@A = (10 20 30 40 50)
@B = (3 4)
Explanation:
a) We left rotate the 3rd index element (40) in the @A to make it 0th index member in the array.
[40 50 10 20 30]
b) We left rotate the 4th index element (50) in the @A to make it 0th index member in the array.
[50 10 20 30 40]
Output:
[40 50 10 20 30]
[50 10 20 30 40]
Example 2:
Input:
@A = (7 4 2 6 3)
@B = (1 3 4)
Explanation:
a) We left rotate the 1st index element (4) in the @A to make it 0th index member in the array.
[4 2 6 3 7]
b) We left rotate the 3rd index element (6) in the @A to make it 0th index member in the array.
[6 3 7 4 2]
c) We left rotate the 4th index element (3) in the @A to make it 0th index member in the array.
[3 7 4 2 6]
Output:
[4 2 6 3 7]
[6 3 7 4 2]
[3 7 4 2 6]Method
I’m not sure “rotate the array” is exactly the right term for what’s being asked for here, as it could be said that what we are being asked to do is to produce the output as though the array had been rotated, rather than actually rotating the array. The distinction is important as we need to retain the integrity of the original array to perform multiple transformations from the base position to output. These transformations are not consecutively applied in a churning fashion, but rather are different individual applications to the starting sequence. Then again, in the end perhaps it’s a distinction without a difference.
The new sequences rearrange the elements such that the the tail of the array, starting at the indicated element, becomes the head, and the head, up to the break, becomes the tail. This can be done easily with array slices.
As removing a singular head element and placing it on the end defines the act of a left rotation, what we are doing here is the same action, only moving a block of elements simultaneously rather than individual elements sequentially. In this sense it satisfies both the function and the spirit of the challenge.
We could, alternately, destructively rotate the array and keep track of the location of the 0 element, then re-rotate according to the terms of modulo arithmetic based around the array length. With a bit of bookkeeping there’s nothing particularly hard about going about things this way. It would, however, necessitate keeping a record of that location between calls to maintain alignment, so if that is the case, why not just keep the original array and process that again? This obviates the need for any complicated arithmetic, so that is the path we have chosen.
Perl Solution
As stated earlier, we can easily do what we need here using array slices, or really a single slice with all of the original indices rearranged. The array indices from the input list serve as separator points between the head and tail sections; the two parts can be reassembled within a single slice:
my @shifted = @array[$idx..$end, 0..$idx-1];
A special case is required for i = 0, because we need the index before the split to calculate the head section, and left to its own devices @array[-1] would reference the last element, which would not do at all. In fact in this case we wish to leave the original array untouched, so that is what is output, unchanged.
~/PWC/78_2_swing_to_the_left.pl
--------------------------------------------------------------------------------
array: (7, 4, 2, 6, 3)
index list: (1, 3, 4)
[4 2 6 3 7]
[6 3 7 4 2]
[3 7 4 2 6]
use warnings;
use strict;
use feature ":5.26";
## ## ## ## ## MAIN:
my @array = (7, 4, 2, 6, 3);
my @idxs = (1, 3, 0, 4);
my @output;
my $end = scalar @array - 1;
for my $idx (@idxs) {
$idx == 0 and do {(push @output, \@array); next};
my @shifted = @array[$idx..$end, 0..$idx-1];
push @output, \@shifted ;
}
say "array: (", (join ', ', @array), ")";
say "index list: (", (join ', ', @idxs ), ")\n";
say "[", (join ' ', $_->@*), "]" for @output;
Raku Solution
In Raku to get our slice indexes in a single list we need to use slip to dereference them out to the same level. As you can see, though, having the extended range notation and the .end method does make the calculation somewhat cleaner.
unit sub MAIN (Str $arraystr = "7,4,2,6,3", Str $idxstr = "1,3,4") ;
## in
my @array = $arraystr.split(',');
my @idxs = $idxstr.split(',');
my @output;
## work
for @idxs -> $idx {
$idx == 0 and do { @output.push: @array; next };
@output.push: @array[|($idx..@array.end), |^$idx];
}
## out
say "array: ", @array;
say "index list: ", @idxs;
say "output:\n";
.say for @output;
Programming Excursions in Perl and Raku 