Task — 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.

Examples

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]

Analysis

Firstly, for this to work, if the array is of length n, it has to comprise the integers 0 .. n - 1, each occurring once only.

So let's loop over the array using for $j (0 .. scalar @ints - 1).

If $ints[$j] is undefined (we'll see later why that might be), we skip to the next $j.

Otherwise, we find the loop that starts (and ends) on $ints[$j] by steadily following the loop, undefining the elements as we go, until we get to an undefined value which must be where we started.

So that's a loop, and all its elements are now undefined so that we don't go round the loop again. Once we've gone through all the values of $j, the whole array will comprise undefined numbers and we can stop.

Try it 

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-09-25
use utf8;     # Week 236 task 2 - Array loops
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

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

# generate bigger example
my ($j, @used, @ints, $count);
while (1) {
    $j = int(rand(100));
    next if $used[$j];
    push(@ints, $j);
    $used[$j] = 1;
    last if ++$count == 100;
}
array_loops(@ints);

sub array_loops {
    
    my (@ints, $j, $k, $m, $loops, $loop, $explain);
    
    # initialise
    @ints = @_;
    $loops = 0;
    
    # loop over next unused number
    for $j (0 .. scalar @ints - 1) {
        next unless defined $ints[$j];
        
        # loop over members of a loop, undefining numbers used
        $k = $j;
        while (1) {
            $m = $ints[$k];
            undef $ints[$k];
            $k = $m;
            last unless defined $k;
            $loop .= qq[$k ];
        }
        
        # details of this loop
        $loops ++;
        $explain .= qq/   [/ . substr($loop, 0, -1) . qq/]\n/;
        $loop = '';
    }
    
    # output results
    say qq[\nInput:  \@ints = (] . join(', ', @_) . ')';
    say qq[Output: $loops\n]  . substr($explain, 0, -1);
}

Output

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

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

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

Input:  @ints = (48, 0, 72, 28, 56, 13, 93, 88, 33, 41, 82, 22, 67, 35, 65, 54, 37, 71, 24, 76, 85, 92, 5, 79, 20, 70, 36, 86, 19, 47, 59, 4, 51, 31, 99, 77, 75, 15, 30, 83, 49, 50, 21, 57, 17, 61, 14, 26, 40, 53, 94, 68, 10, 25, 39, 18, 1, 87, 64, 69, 42, 45, 32, 11, 34, 90, 29, 95, 38, 74, 2, 60, 63, 46, 27, 43, 12, 62, 7, 6, 80, 55, 66, 8, 23, 16, 3, 91, 9, 84, 58, 73, 97, 52, 89, 44, 78, 98, 96, 81)
Output: 3
   [48 40 49 53 25 70 2 72 63 11 22 5 13 35 77 62 32 51 68 38 30 59 69 74 27 86 3 28 19 76 12 67 95 44 17 71 60 42 21 92 97 98 96 78 7 88 9 41 50 94 89 84 23 79 6 93 52 10 82 66 29 47 26 36 75 43 57 87 91 73 46 14 65 90 58 64 34 99 81 55 18 24 20 85 16 37 15 54 39 83 8 33 31 4 56 1 0]
   [61 45]
   [80]