forked from manwar/perlweeklychallenge-club
/
ch-2.pl
86 lines (69 loc) · 1.81 KB
/
ch-2.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#!/usr/bin/env perl
use v5.38;
use Lingua::EN::Inflexion qw( inflect );
sub loopExistsAt {
my %params = @_;
my $ints = $params{ints};
my $start = $params{start};
my $seen = $params{seen};
# bail early if we're in a loop we've seen before
return if exists $seen->{$start};
my @loop;
my $i = $start;
for (;;) {
# keep track of the values in the order we visit them
push @loop, $ints->[$i];
# track where we've already been
# to avoid double-counting loops
$seen->{$i} = 1;
# get the next index
$i = $ints->[$i];
# make sure the index is in bounds
last unless $i >= 0 && $i <= $#{$ints};
# make sure we haven't seen the index before
last if exists $seen->{$i};
}
# if the last element points back to
# the start, it's a loop!
if ($loop[-1] == $start) {
return @loop;
}
# otherwise, return an empty list
return;
}
sub identifyLoops {
my @ints = @_;
my @loops;
my %seen; # keep track of indices we've seen
# to avoid duplicating loops
foreach my $start ( 0 .. $#ints ) {
my @loop = loopExistsAt(
start => $start,
ints => \@ints,
seen => \%seen
);
if (@loop) {
push @loops, \@loop;
}
}
return @loops;
}
sub solution {
my @ints = @_;
say 'Input: @ints = (' . join(',', @ints) . ')';
my @loops = identifyLoops(@ints);
say 'Output: ' . scalar(@loops);
if (@loops) {
my $count = scalar(@loops);
say inflect "\n<#d:$count><N:Loop> <V:is> as below:";
foreach my $loop ( @loops ) {
say '[' . join(' ', @$loop) . ']';
}
}
}
say "Example 1:";
solution(4,6,3,8,15,0,13,18,7,16,14,19,17,5,11,1,12,2,9,10);
say "\nExample 2:";
solution(0,1,13,7,6,8,10,11,2,14,16,4,12,9,17,5,3,18,15,19);
say "\nExample 3:";
solution(9,8,3,11,5,7,13,19,12,4,14,10,18,2,16,1,0,15,6,17);