Perl Weekly Challenge in Raku Week 71 (Part 1)

Sorry I've been away for a while I've actually been plugging away at the Challenges for a while I've just not felt the energy to Blog about then. Partly I've been busy and partly well... 2020 you know how it is.

But I figured I should get back on the horse with Week 71.

Challenge 1

So Challenge 1 asked you to generate a list of length 2 to 50 unique random positive integers. Then print the lists of peaks, a peak being defined as a number in the list higher than the two numbers next to it. Sounds fun, let's dive in.

Firstly we want our list size ($N) that needs to be between 2 and 50. We can put this in a MAIN sub with some documentation so we can run the script from the command line.

#| Generate a list of random numbers then find the peaks
sub MAIN(
    UInt $N 
    where 1 < * <= 50 #= Size of random number list
) {
    ...
}

As usual I'm using the #| and #= comments to add documentation to the function that will auto print if you run it with -? or incorrect input.

$N has a where clause that makes use of a Whatever Star to generate a code block and also operator chaining to easily test that 1 < $N and $N <= 50.

So now we want to make a list of random unique numbers between 1 and 50 up to $N in length. Luckily there's an app for that!

Well a method, pick picks a random number from a list in this in this way it's similar to roll and if you just call list.pick and list.roll you'll get a single random item in the list.

The difference comes when you call then with an integer value. In this case you get a Sequence of items from the list and here is where the two method diverge. list.roll(N) is like rolling a dice N times with all the items in the list on different sides. Each roll is distinct and the same number can come up twice.

list.pick(N) is list picking N cards from a deck. You don't put them back into the deck until you've finished picking... Which makes our code to make (or pick) the random list simple enough.

my @list = (1..50).pick($N);
say "List  : {@list.join(',')}";

This makes a random list of the numbers from 1 to 50 of length $N then prints it out. Ok... now to find the peaks.

First thing to bear in mind, for any given point $i in the list it's a peak if @list[$i-1] < @list[$i] > @list[$i+1] (note we don't need to worry about equality as the numbers are unique).

Another way to look at this is if you have a list of 3 numbers (@l) then the number in the middle of the list is a peak if @l[0] < @l[1] > @l[2]. I can see my old friend grep waving at me. We've come through thick and thin together and they've never let me down, sure they change their name in different places but I know if grep is around my life will be easier.

So I'm already seeing a plan, take the list, make it into a list of list where each is the current value and the numbers to either side. Grep for peaks then map comes in (you rarely find the two far apart) and pulls out the middle value again...

So this leaves us with two questions...

• What about the start and end values?
• How do we split the list up?

Generally when you're doing functional list based manipulation you want to avoid special cases (like how to handle to two ends of the list) as it complicates matters.

Of course we know that every number in the list if greater than 0 for if we put a 0 at each end of the list before dividing it into the lists of lists then we simplify things. Now our first list triplet will be (0, @list[0], @list[1]) and the test (0 < @list[0] > @list[1]) is functionally the same (in this case) as @list[0] > @list[1].

So our list of peaks starts simply enough :

@peaks = ( 0, |@list, 0 ); 

This uses the | operator to "slip" our list into the outer list creator (the brackets). If we don't do that you end up with 3 items in @peaks, one of which is a list...

Great so now we just have to divide this list into overlapping sets of three items.

It's at this point the inexperienced Raku developer will start writing a bunch of nested for loops and all this kind of stuff.

This isn't wrong but I often find that if I have a simple problem in Raku the first thing to do is Read the Docs. In this case we specifically want to look at the rotor method.

Rotor is a new friend of grep and map, Raku has brought a lot of friends to the "Lets play about with lists" party. Which is cool, especially when you realise just how many things count as "lists" for this.

But I digress. What rotor does is divide a list into sublists of a given length so :

(1,2,3,4).rotor(2) == ((1,2),(3,4))

Ok so this is starting to look right of only there was some where to say :

(1,2,3,4).rotor(THING) == ((1,2),(2,3),(3,4)) 

And do it for 3 items... well guess what, you totally can. Rotor has a lot of options on how you call it and I'm going to focus on one for this job.

If you call rotor and pass a Pair then it treat's this as length => offset and it will skip offset many items before making the next sub list.

Which is nice when you find that offset can be a negative, in which case you get overlapping sublists.

Our @peaks now becomes :

my @peaks = ( 0, |@list, |0 )
    .rotor(3 => -2)
    .grep( { $_[0] < $_[1] > $_[2] } )
    .map( { $_[1] } );
say "Peaks : {@peaks.join(',')}";

Get the list, split into sublists, grep for peaks, pull out the middle number. All nice and simple, no special cases and functional. If we wanted (and the list was longer) we could run these steps in parallel.

Nice and easy. Of course I've written a lot of stuff about what ended up being a 4 line bit of code. As the second solution is a bit longer I'll do a second post about it later.

Fingers crossed and 2020 willing.