# RogerBW's Blog

Perl Weekly Challenge 78: Leaders and Rotation 16 September 2020

I’ve been doing the Perl Weekly Challenges. The latest involved searching array values and rotating lists.

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.

Since the rightmost element is always greater than all the elements to its right, the special case may safely be ignored. The algorithm becomes apparent: taking the array in reverse order, see if the current element is larger than the working maximum (or the working maximum hasn't yet been defined). If so, give the working maximum the value of the current element, and prepend it to the output list. (Or, in fact, reverse the output list once it's been filled, though I did that for convenience in the Python conversion.)

I decided to write this ab initio in Raku rather than, as I have been so far, starting in Perl and then converting.

``````sub leader(@a) {
my @t=reverse @a;
my \$m;
my @o;
for @t -> \$c {
if (!defined \$m or \$c > \$m) {
\$m=\$c;
push @o,\$m;
}
}
@o=reverse @o;
return @o.flat;
}
``````

Mind you, the only thing that's significantly different from the Perl version is the "flat" on the end, so that the test harness' `is-deeply` is returned a list rather than a listref. (Yeah, the major part of my ongoing struggle with Raku, and one day I'll understand it.)

Python is a little more fiddly because it distinguishes between `list.reverse()` (which reverses a list in place) and `reversed(list)` which returns a new iterator based on the old iterator (which is thus not testable for equality with another list). I ended up using both.

Also, where Perl/Raku have `undef`, Python has `None` with a more straightforward syntax.

``````import unittest

m=int()
o=list()
for c in (reversed(a)):
if (m==None or c > m):
m=c;
o.append(m)
o.reverse()
return o
``````

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

This is clarified further in the examples, but in short, "for each entry `\$B` in `@B`, return a copy of `@A` rotated such that it starts at the `\$B`-th index".

Now obviously I could rotate the actual array repeatedly, but there's a better way: each of these three languages has lightweight array slicing. So if I append a copy of `@A` to itself, I just need to index into it to get the sequence I want.

I started this one in Python. It shares with Raku what seems to me a needless complexity of syntax; if I want to append `(1,2,3)` to `(1,2,3)` to make `(1,2,3,1,2,3)` rather than `(1,2,3,(1,2,3))` it shouldn't be difficult. (`map` seems not to be widely used in Python, but it seemed appropriate here.)

``````def leftrot(a,b):
l=len(a)
t=list()
map(t.append,a)
map(t.append,a)
o=list()
for c in (b):
o.append(list((t[c:c+l])))
return o
``````

Perl is the same algorithm expressed slightly differently:

``````sub leftrot {
my \$a=shift;
my \$b=shift;
my \$l=scalar(@{\$a})-1;
my @t=(@{\$a},@{\$a});
my @o;
foreach my \$c (@{\$b}) {
push @o,[@t[\$c..\$c+\$l]];
}
return \@o;
}
``````

And Raku too:

``````sub leftrot(@a,@b) {
my \$l=@a.end;
my @t=(@a,@a).flat;
my @o;
for @b -> \$c {
push @o,[@t[\$c..\$c+\$l]];
}
return @o;
}
``````

Full code on github.

1. Posted by RogerBW at 03:23pm on 21 September 2020

For part 1, several people decided to compare one element in the array with everything that came after it (Raku's `all()`) makes this particularly tempting). But that makes the problem something like O(N²) rather than O(N).

For part 2, Raku has a `rotate()` method on lists ("return a rotated copy") which makes this trivial and which I'd have used if I'd noticed it. In Perl this might look like `my @shifted = @array[\$idx..\$end, 0..\$idx-1];` – thanks to Colin Crain for the concise example, though as he points out it needs a special case where `\$idx` is zero so as to avoid a reference to index -1, and my array-doubling doesn't.