## Perl Weekly Challenge 78: Leader Element and Left Rotation

These are some answers to the Week 78 of of the Perl Weekly Challenge organized by Mohammad S. Anwar

Spoiler Alert: This weekly challenge deadline is due in a few days (September 20, 2020). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

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)
``````

Two small comments. First, if we set aside the (very special) case where the input array is empty, we will never have to print 0, since the last item of the array will always be a leader element. Second, I’ll interpret the leader element definition as strictly greater than all its successors.

We only need to read the input array backward and keep track of the maximum element seen so far. Any item strictly greater than all items seen previously is a leader. Here, we do it for the two arrays provided as examples.

``````use v6;

my @in = [9, 10, 7, 5, 6, 1], [3, 4, 5];
for @in -> @a {
my @result = gather {
my \$max = @a[*-1];
take \$max;
for @a.reverse -> \$item {
if \$item > \$max {
take \$item;
\$max = \$item;
}
}
}
say "Input: @a[]; Output: ", @result.reverse;
}
``````

The result is in conformity with what we expected:

``````Input: 9 10 7 5 6 1; Output: (10 7 6 1)
Input: 3 4 5; Output: (5)
``````

Just like in Raku, we read the input array backward and keep track of the maximum element seen so far. Any item strictly greater than all items seen previously is a leader.

``````use strict;
use warnings;
use feature "say";

my @in = ([9, 10, 7, 5, 6, 1], [3, 4, 5]);
for my \$aref (@in) {
my @result;
my \$max = @\$aref[-1];
push @result, \$max;
for my \$item (reverse @\$aref) {
if (\$item > \$max) {
push @result, \$item;
\$max = \$item;
}
}
say "Input: @\$aref; Output: ", join " ", reverse @result;
}
``````

Here again, the result is what we expected:

``````\$ perl leader.pl
Input: 9 10 7 5 6 1; Output: 10 7 6 1
Input: 3 4 5; Output: 5
``````

### Left Rotation

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. Similarly, left rotate `@A` again so that the number at the second index of `@B` becomes the first element in the array.

Example:

``````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]
``````

### Left Rotation in Raku

We can simply use array slices to get what we need. The only slight difficulty is that we need to flatten the two index slices into a single list.

``````use v6;

my @a = 10, 20, 30, 40, 50;
my @indices = 3, 4;

say "Input array: ", @a;
for @indices -> \$i {
my @out = @a[(\$i..@a.end, 0..\$i -1).flat];
say @out;
}
``````

Output:

``````\$ raku left_rotate.raku
Input array: [10 20 30 40 50]
[40 50 10 20 30]
[50 10 20 30 40]
``````

### Left Rotation in Perl

Again, we use array slices. Here, the only slight difficulty is the relatively heavy use of nested array references.

``````use strict;
use warnings;
use feature "say";

my @a = ( [[10, 20, 30, 40, 50],[3, 4]],
[[7, 4, 2, 6, 3], [1, 3, 4]] );
left_rotate(\$_) for @a;

sub left_rotate {
my \$inref = shift;
my (\$in, \$indices) = @\$inref;
say "\nInput array: @\$in - Indices: @\$indices";
for my \$i (@\$indices){
my @out = @\$in[\$i..\$#{\$in}, 0..\$i -1];
say "@out";
}
}
``````

Output:

``````\$ perl left_rotate.pl

Input array: 10 20 30 40 50 - Indices: 3 4
40 50 10 20 30
50 10 20 30 40

Input array: 7 4 2 6 3 - Indices: 1 3 4
4 2 6 3 7
6 3 7 4 2
3 7 4 2 6
``````

## Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, September 27, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.

## 1 Comment

I like to see that you have done the reverse solution for the first one - it is really elegant and the method I used.

Not sure if it is more optimal (don't know perl internals well enough) but to avoid the second reverse you can use "unshift" rather than push to put the entries at the start of the list. I also shortened the code - as this is an example where you can use two "="s in a line to define two variables...

So you could do

`    my @result = my \$max = pop @{\$aref};`

Similarly in the for loop you can do:

`    unshift @result, \$max = \$item;`