The weekly challenge 236 - Task 2: Array Loops

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-236/#TASK2
 3 #
 4 # Task 2: Array Loops
 5 # ===================
 6 #
 7 # You are given an array of unique integers.
 8 #
 9 # Write a script to determine how many loops are in the given array.
10 #
11 ### To determine a loop: Start at an index and take the number at array[index]
12 ### and then proceed to that index and continue this until you end up at the
13 ### starting index.
14 #
15 ## Example 1
16 ##
17 ## Input: @ints = (4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10)
18 ## Output: 3
19 ##
20 ## To determine the 1st loop, start at index 0, the number at that index is 4,
21 ## proceed to index 4, the number at that index is 15, proceed to index 15 and
22 ## so on until you're back at index 0.
23 ##
24 ## Loops are as below:
25 ## [4 15 1 6 13 5 0]
26 ## [3 8 7 18 9 16 12 17 2]
27 ## [14 11 19 10]
28 #
29 ## Example 2
30 ##
31 ## Input: @ints = (0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19)
32 ## Output: 6
33 ##
34 ## Loops are as below:
35 ## [0]
36 ## [1]
37 ## [13 9 14 17 18 15 5 8 2]
38 ## [7 11 4 6 10 16 3]
39 ## [12]
40 ## [19]
41 #
42 ## Example 3
43 ##
44 ## Input: @ints = (9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17)
45 ## Output: 1
46 ##
47 ## Loop is as below:
48 ## [9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0]
49 #
50 ############################################################
51 ##
52 ## discussion
53 ##
54 ############################################################
55 #
56 # We start at index 0 and walk all the way up to the last index.
57 # Then we just calculate the loop starting at that index in the
58 # array. If by any chance we see an index that is already part
59 # of a loop, we can return.
60 #
61 use strict;
62 use warnings;
63 
64 array_loops(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10);
65 array_loops(0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19);
66 array_loops(9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17);
67 
68 my $seen_index = {};
69 
70 sub array_loops {
71    my @ints = @_;
72    my @loops = ();
73    $seen_index = ();
74    print "Input: (" . join(", ", @ints) . ")\n";
75    foreach my $index (0..$#ints) {
76       next if $seen_index->{$index};
77       my $loop = get_loop($index, @ints);
78       push @loops, $loop if $loop;
79    }
80    print "Output: " . scalar(@loops) . "\n";
81    foreach my $loop (@loops) {
82       print "[" . join(", ", @$loop) . "]\n";
83    }
84 }
85 
86 sub get_loop {
87    my $index = shift;
88    my @ints = @_;
89    my $loop = [];
90    $index = $ints[$index];
91    while(! $seen_index->{$index}) {
92       $seen_index->{$index} = 1;
93       push @$loop, $index;
94       $index = $ints[$index];
95    }
96    return $loop;
97 }
98