laurent_r

These are some answers to the Week 228, Task 2, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on August 6, 2023 at 23:59). This blog post offers some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 2: Empty Array

You are given an array of integers in which all elements are unique.

Write a script to perform the following operations until the array is empty and return the total count of operations.

If the first element is the smallest then remove it otherwise move it to the end.

Example 1

Input: @int = (3, 4, 2)
Ouput: 5

Operation 1: move 3 to the end: (4, 2, 3)
Operation 2: move 4 to the end: (2, 3, 4)
Operation 3: remove element 2: (3, 4)
Operation 4: remove element 3: (4)
Operation 5: remove element 4: ()

Example 2

Input: @int = (1, 2, 3)
Ouput: 3

Operation 1: remove element 1: (2, 3)
Operation 2: remove element 2: (3)
Operation 3: remove element 3: ()

First, an important information is that all elements of the input array are unique. This means that there cannot be two items that are equal, or, in other words, that, if the first item is the smallest, then all other items are (strictly) larger.

Empty Array in Raku

We start with an end-less loop (from which we will exit with a last statement once the array is empty). In the loop, we shift the first item of the array (meaning that we remove it from the array and retrieve its value). If its value is not the smallest in the array, we push it back to the end of the array. Otherwise, it is the smallest item in the array, we don't do anything to the array, meaning that the array has now one item less than before. And we use a counter ($count) to record the number of steps. Note that we conveniently use an any junction to check whether the shifted item is the smallest item of the array, that is that it is not larger than any other item.

sub empty-array (@in is copy) {
    my $count = 0;
    loop {
        my $val = shift @in;
        push @in, $val if $val > @in.any;
        $count++;
        last unless @in;
    }
    return $count;
}

for <3 4 2>, <1 2 3>, <3 2 1>, <4 7 2 9 1> -> @test {
    printf "%-10s => ", "@test[]";
    say empty-array @test;
}

This program displays the following output:

$ raku ./empty-array.raku
3 4 2      => 5
1 2 3      => 3
3 2 1      => 6
4 7 2 9 1  => 12

Empty Array in Perl

This is a port to Perl of the above Raku program. Please refer to the above section if you need explanations. The only significant difference is that, since Perl doesn't have junctions, we need to implement an inner loop to find out whether the chosen item is smaller than all other remaining items of the array.

use strict;
use warnings;
use feature 'say';

sub empty_array {
    my @in = @_;
    my $count = 0;
    while (1) {
        my $val = shift @in;
        my $pushback = 0;
        for my $item (@in) {
            $pushback = 1 if $val > $item;
            last if $pushback;
        }
        push @in, $val if $pushback;
        $count++;
        last unless @in;
    }
    return $count;
}

for my $test ( [<3 4 2>], [<1 2 3>], 
               [<3 2 1>], [<4 7 2 9 1>] ) {
  printf "%-10s => ", "@$test";
  say empty_array @$test;
}

This program displays the following output:

$ perl ./empty-array.pl
3 4 2      => 5
1 2 3      => 3
3 2 1      => 6
4 7 2 9 1  => 12

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on August 13, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.