Perl Weekly Challenge: Week 71
Challenge 1:
Peak Element
You are given positive integer
$N(>1).Write a script to create an array of size
$Nwith random unique elements between1and50.In the end it should print
peak elementsin the array, if found.An array element is called peak if it is bigger than it’s neighbour.
Example 1
Array: [ 18, 45, 38, 25, 10, 7, 21, 6, 28, 48 ]
Peak: [ 48, 45, 21 ]
Example 2
Array: [ 47, 11, 32, 8, 1, 9, 39, 14, 36, 23 ]
Peak: [ 47, 32, 39, 36 ]
.pick() is a nice and useful Raku method to select one element from an array without
duplicates (unless $N > 50 when it will start repeating.). I use it to populate an array of $N elements.
my @arr = (1 .. 50).pick($N);
my @peak;
Then we just loop through the @arr checking the neighbors of each element. There are two edge cases; the
first element has no left neighbor and the last element has no right neighbor. Rather than deal with each
case separately, I just used // to make any undefined neighbor 0 which will always be less than any real elements
value.
for 0 ..^ @arr.elems -> $i {
if @arr[$i] > (@arr[$i - 1] // 0) && @arr[$i] > (@arr[$i + 1] // 0) {
@peak.push(@arr[$i]);
}
}
Perl doesn't have a .pick() method of its own but I had written a clone in challenge 38 which I reused here.
my @arr = pick([1 .. 50], $N);
my @peak;
for my $i (0 .. (scalar @arr - 1)) {
if ($arr[$i] > ($arr[$i - 1] // 0) && $arr[$i] > ($arr[$i + 1] // 0)) {
push @peak, $arr[$i];
}
}
Challenge 2:
Trim Linked List
You are given a singly linked list and a positive integer
$N(>0).Write a script to remove the
$Nthnode from the end of the linked list and print the linked list.If
$Nis greater than the size of the linked list then remove the first node of the list.NOTE: Please use pure linked list implementation.
Example
Given Linked List: 1 -> 2 -> 3 -> 4 -> 5
when $N = 1
Output: 1 -> 2 -> 3 -> 4
when $N = 2
Output: 1 -> 2 -> 3 -> 5
when $N = 3
Output: 1 -> 2 -> 4 -> 5
when $N = 4
Output: 1 -> 3 -> 4 -> 5
when $N = 5
Output: 2 -> 3 -> 4 -> 5
when $N = 6
Output: 2 -> 3 -> 4 -> 5
I already had experience with creating a linked list in challenge 68 but it was not the most well thought out code I must admit. So this time I tried to do a better job.
This time there is a class LinkedList which has all the list operations as its' methods and maintains the Nodes internally.
The Node class has the same structure as in challenge 68. $!head is the Node which is the beginning of the list. It will initially be undefined. There is another member called $.count which is the number of nodes in the linked list. In hindsight,
$.length would have been a better name. Note the different "twigils" in each member. They control how Raku will create accessor methods for the data. . means create a getter and setter. Actually because $.count is defined as is readonly only the getter will be created. ! means don't create anything at all. This is for strictly private data which will never be exposed outside the
class.
class LinkedList {
class Node {
has $.value is rw;
has Node $.next is rw;
submethod BUILD( :$value) {
$!value = $value;
$!next = Nil;
}
}
has Node $!head;
has Int $.count is readonly;
The BUILD submethod constructs an empty LinkedList. (I need to read up on what is the difference
between a method and a submethod.)
submethod BUILD() {
$!head = Nil;
$!count = 0;
}
If $!head is undefined, the add() method makes it into a new Node. Otherwise it
starts at $!head and traverses the .nexts until it reaches the end of the list and
creates a new Node there. In either case, $.count is incremented.
method add($newval) {
my $v = $!head;
if ($v) {
while $v.next {
$v = $v.next;
}
$v.next = Node.new(value => $newval);
} else {
$!head = Node.new(value => $newval);
}
$!count++;
}
The print() method works the same as Nodes similiarly named one in challenge 68.
method print() {
my $v = $!head;
while $v {
print $v.value // q{}, q{ };
$v = $v.next;
}
print "\n";
}
The trim() method was a little tricky to get right.
method trim(Int $n) {
Which element to we want to remove? It will be the $nth one from the
end or $.count - $n if $n is less than the length of the list. If it is
equal to or greater than the length, it will be the first element.
my $i = $n > $.count ?? 0 !! $.count - $n;
This is what we do if $!head is defined and we are trying to remove the first element (i.e. $!head itself,)
if ($!head && $i == 0) {
my $temp = $!head;
$!head = $!head.next;
$temp = Nil;
Notice the three step process? This is to ensure the removed node is no longer referenced so it can be properly garbage-collected and its memory reclaimed. Actually I'm not a 100% sure this is necessary or if Raku is smart enough to deal with it but it seemed prudent anyway.
If $!head doesn't exist or we want an element other than the first...
} else {
my $v = $!head;
my $c = 0;
If $!head was undefined, this whole loop gets skipped and the method returns.
Otherwise we traverse the array. Because $c was initialized to 0, we stop when we reach
the node before the one we want to remove. Now again we have two choices. If this node
is not the last one in the list (i.e. its' next is not Nil) we set its next to the next nodes
next. (phew!) If this node is the last node, we simply set it to Nil. I didn't do the three-step
temp thing when removing these nodes. In this case I don't think it is necessary.
while $v {
$c++;
if $c == $i {
if $v.next {
$v.next = $v.next.next;
} else {
$v = Nil;
}
last;
}
$v = $v.next;
}
}
}
}
This is the Perl equivalent. The only notable thing here is the use of a scoped package
declaration in order to properly nest LinkedList::Node.
package LinkedList {
use Moo;
use namespace::autoclean;
package LinkedList::Node {
use Moo;
use namespace::autoclean;
has _value => (
is => 'rw',
);
has _next => (
is => 'rw',
isa => sub { return ref eq 'LinkedList::Node'; },
);
sub BUILDARGS {
my ($orig, $class, @args) = @_;
return { _value => $args[0], _next => undef };
}
}
has _head => (
is => 'ro',
isa => sub { return ref eq 'LinkedList::Node'; },
);
has _count => (
is => 'ro',
);
sub BUILDARGS {
my ($orig, $class, @args) = @_;
return { _head => undef, _count => 0 };
}
sub add {
my ($self, $newval) = @_;
my $v = $self->{_head};
if ($v) {
while ($v->{_next}) {
$v = $v->{_next};
}
$v->{_next} = LinkedList::Node->new(value => $newval);
} else {
$self->{_head} = LinkedList::Node->new(value => $newval);
}
$self->{_count}++;
}
sub print {
my ($self) = @_;
my $v = $self->{_head};
while ($v) {
print $v->{_value} // q{}, q{ };
$v = $v->{_next};
}
print "\n";
}
sub trim {
my ($self, $n) = @_;
my $i = $n > $self->{_count} ? 0 : $self->{_count} - $n;
if ($self->{_head} && $i == 0) {
$self->{_head} = $self->{_head}->{_next};
} else {
my $v = $self->{_head};
my $c = 0;
while ($v) {
$c++;
if ($c == $i) {
if ($v->{_next}) {
$v->{_next} = $v->{_next}->{_next};
} else {
$v = undef;
}
last;
}
$v = $v->{_next};
}
}
}
}