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.

TASK #1 › Leader Element

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

def leader(a):
  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.

Add A Comment

Your Name
Your Email
Your Comment

Your submission will be ignored if any field is left blank, but your email address will not be displayed. Comments will be processed through markdown.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1