laurent_r

These are some answers to the Week 236, 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 October 1, 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: Array Loops

You are given an array of unique integers.

Write a script to determine how many loops are in the given array.

To determine a loop: Start at an index and take the number at array[index] and then proceed to that index and continue this until you end up at the starting index.

Example 1

Input: @ints = (4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10)
Output: 3

To determine the 1st loop, start at index 0, the number at that index is 4, proceed to index 4, the number at that index is 15, proceed to index 15 and so on until you're back at index 0.

Loops are as below:
[4 15 1 6 13 5 0]
[3 8 7 18 9 16 12 17 2]
[14 11 19 10]

Example 2

Input: @ints = (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19)
Output: 6

Loops are as below:
[0]
[1]
[13 9 14 17 18 15 5 8 2]
[7 11 4 6 10 16 3]
[12]
[19]

Example 3

Input: @ints = (9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17)
Output: 1

Loop is as below:
[9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0]

I may have missed something, but I really don't understand the examples. Let's take example 1:

(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10)

We start with index 0 and obtain, as specified in the example, the following loop:

[4 15 1 6 13 5 0]

But why does the second loop in the example start with 3 (i.e. index 2)? We can start with index 1 (value 6) and obtain the following loop:

(Starting with index 1)
  index   value
    1       6
    6       13
    13      5
    5       0
    0       4
    4       15
    15      1

Similarly, if we start with index 3, we obtain the following loop:

(Starting with index 3)
  index   value
    3       8
    8       7
    7       18
    18      9
    9       16
    16      12
    12      17
    17      2
    2       3

And, with index 4:

(Starting with index 4)
  index   value
    4       15
    15      1
    1       6
    6       13
    13      5
    5       0
    0       4

And so on.

In fact, since values in the given examples seem to be permutations of the input array indexes, starting with any index will lead to a loop, so that with an array of 20 values, we will find 20 possible loops.

So my results will not be the same as those provided with the examples.

Array Loops in Raku

We iterate on every item of the input array as a start value, and for every value, we follow the index until we find a loop. If a loop is found, we increment a counter and, at the end, return the counter to the calling code.

sub find-loops (@in) {
    my $count = 0;
    for 0..@in.end -> $i {
        my $j = $i;
        loop {
            last unless @in[$j].defined;
            # say "\t", $j, "\t", @in[$j];
            ++$count and last if @in[$j] == $i;
            $j = @in[$j];
        }
    }
    return $count;
}

my @tests = 
    (4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10),
    (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19),
    (9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17),
    (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3);

for @tests -> @test {
    say @test;
    say "\tNumber of loops: ", find-loops @test;
}

This program displays the following output:

$ raku ./array-loops.raku
(4 6 3 8 15 0 13 18 7 16 14 19 17 5 11 1 12 2 9 10)
        Number of loops: 20
(0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19)
        Number of loops: 20
(9 8 3 11 5 7 13 19 12 4 14 10 18 2 16 1 0 15 6 17)
        Number of loops: 20
(0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3)
        Number of loops: 10

Array Loops in Perl

This Perl program works exactly as the above Raku program. Please refer to the previous sections if you need explanations.

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

sub find_loops {
    my @in = @_;
    my $count = 0;
    for my $i (0..$#in) {
        my $j = $i;
        # say $i;
        while (1) {
            last unless defined $in[$j];
            # say "\t", $j, "\t", @in[$j];
            ++$count and last if $in[$j] == $i;
            $j = $in[$j];
        }
    }
    return $count;
}

my @tests = (
    [4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10],
    [0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19],
    [9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17],
    [0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3]);

for my $test (@tests) {
    say "@$test";
    say "\tNumber of loops: ", find_loops @$test;
}

This program displays the following output:

$ perl ./array-loops.pl
4 6 3 8 15 0 13 18 7 16 14 19 17 5 11 1 12 2 9 10
        Number of loops: 20
0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3 18 15 19
        Number of loops: 20
9 8 3 11 5 7 13 19 12 4 14 10 18 2 16 1 0 15 6 17
        Number of loops: 20
0 1 13 7 6 8 10 11 2 14 16 4 12 9 17 5 3
        Number of loops: 10

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 October 8, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.