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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2022 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript 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 ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge 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