PWC 236 Task 2 The Circle Is Small

The second challenge of week 236 is to find cycles in a list of integers. I am reminded of another minor hit from the past, The Circle Is Small, by Gordon Lightfoot.

The city where we live might be quite large
But the circle is small, so why not tell us all
And then all of us will know

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:

1. [4 15 1 6 13 5 0]
2. [3 8 7 18 9 16 12 17 2]
3. [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:

1. [0]
2. [1]
3. [13 9 14 17 18 15 5 8 2]
4. [7 11 4 6 10 16 3]
5. [12]
6. [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

The only loop is one that includes all the elements:

1. [9 4 5 7 19 17 15 1 8 12 18 6 13 2 3 11 10 14 16 0]

Exegesis

What the text doesn't say, but the examples imply, is that the array consists of a permutation of the indexes. Let's make that assumption. Then it's only logical to conclude a few things about the cycles.

• All the values in an array of size N are between 0 and N-1.
• All the values 0 to N-1 appear in the array exactly once.
• No matter where we start, we will end up in a loop. To see this, imagine that we have jumped around the array without creating a loop and visited every element except one. The next jump will either take us back to somewhere we have visited (loop!), or to the last unvisited element. But that element will then index somewhere into the array, all of which has been visited (loop!).
• Every element in the array will be part of exactly one loop. Once we find a loop, all the elements in that path can't be part of any other loop; because the indexes only occur once, there's no way to branch into a different path. If we then exclude that loop and start from one of the remaining elements, we will end up in a loop again, by the reasoning from the paragraph above.

That eliminates a lot of things that might bother us if the integers were more random. Among other things, it assures that we only need to make one pass through the array -- no depth-first search or anything awful that might make us get out our algorithms book. It also means that there should be no edge cases that have no loops, or that risk infinitely searching for a start point.

We may never pass this way again

The search for loops will remove sets of elements from consideration each time it finds a cycle. The outline looks like:

1. Pick a starting element.
2. Follow the indexes, marking each one that is visited.
3. Once we reach an element that is already marked (and we know we will), we've found a loop; increment a counter.
4. Remove the visited elements from consideration.
5. Proceed to a new starting element from the remaining elements.
6. Once we run out of starting points (and we will, having covered every element and every loop), return the counter.

Now some choices need to be made. How will we mark visited elements while we're searching, and elements that have been removed from consideration? Both are boolean conditions, so a couple of choices spring to mind:

• Two arrays of the same size as the input, holding booleans that indicate visited or not; and indicating under consideration or not.
• Bit vectors, used the same way.
• One array of the same size, using two bits at each index.
• Since we know the range of values in the array is 0 to n-1, we can modify the input array in place with out-of-range values like -1 and -2 to indicate visiting and out-of-consideration, respectively.
• Transform the array into an array of small objects, so that each index holds a 3-tuple: original value, isVisiting, and isInPlay.

I'm feeling very basic at the moment, so let's try the version that uses two arrays of booleans. The array @isInAnyLoop will start out all false, and keep track of elements that are taken out of consideration after a loop is found. The array @visited will be used while following indexes to mark the members of the loop. Although the task doesn't ask us to show the loops, we'll also populate the @loop array so that we can show it if we want.

sub arrayLoops(@ints)
{
    my @isInAnyLoop = (false) x @ints;

    my $loopCount = 0;
    for ( my $start = 0 ; $start <= $#ints ; $start++ )
    {
        next if $isInAnyLoop[$start];

        my @visited = (false) x @ints;
        $visited[$start] = true;
        my @loop = ( $ints[$start] );

        my $next = $ints[$start];
        while ( ! $visited[$next] )
        {
            $isInAnyLoop[$next] = $visited[$next] = true;
            push @loop, $ints[$next] if $Verbose;
            $next = $ints[$next];
        }
        $loopCount++;
        say "LOOP: [@loop]" if $Verbose;
    }
    return $loopCount;
}

It gets mildly confusing because the values are indexes, but after I stopped overthinking about indirect references, it came together quickly.

Your most pedantic code reviewer will flag the drive-by assignment $isInAnyLoop[$next] = $visited[$next] = true but I plead laziness.

In this code is an array initialization -- my @visited = (false) x @ints -- that I remember being confusing to me when I was learning Perl. In my mind, what should happen is that Perl sees array context because of @visited =, and therefore should build a list out of an expression like @x = 0 x 3. But the x replication operator scoffs at your puny attempt to assert array context and replicates a scalar value if it can. If you want to build a list with x, you have to give it a starting list as its left-hand argument.