My Python Language Solution to Task 2: Nested Array from The Weekly Challenge 300

1. Introduction

The Weekly Challenge, organized by Mohammad S. Anwar, is a friendly competition in which developers compete by solving a pair of tasks. It encourages participation from developers of all languages and levels through learning, sharing, and having fun.

Task 2: Nested Array from The Weekly Challenge 300 prompts developers to find the longest nested array length.

The Weekly Challenge 300 deadline is Sunday, December 23, 2024 at 23:59 (UK Time). To avoid bias, please consider reading this post after competing.

2. Task 2: Nested Array

You are given an array of integers, @ints of length n containing permutation of the numbers in the range [0, n-1].

Write a script to build a set, set[i] = ints[i], ints[ints[i]], ints[ints[ints[i]]], ... subjected to the following rules:

1. The first element in set[i] starts with the selection of elements ints[i].
2. The next element in set[i] should be ints[ints[i]], and then ints[ints[ints[i]]], and so on.
3. We stop adding right before a duplicate element occurs in set[i].

Return the longest length of a set set[i].

The Weekly Challenge 300, Task 2: Nested Array

Example 1 and Example 2 present the expected outputs for given inputs.

Example 1

Input: @ints = (5, 4, 0, 3, 1, 6, 2)
Output: 4

Here one of the longest sets is set[0]:

set[0] = {ints[0], ints[5], ints[6], ints[2]} = {5, 6, 2, 0}

Example 2

Input: @ints = (0, 1, 2)
Output: 1

3. My solution

def build_set_from_index(ints, starting_index):
    iset = [
            ints[starting_index],
            ]
    for ints_index in range(1, len(ints)):
        pindex = iset[ints_index - 1]
        value = ints[pindex]
        if value in iset:
            break
        iset.append(value)
    return iset

def return_longest_length(ints):
    max_length = 0
    for i in range(0, len(ints)):
        iset = build_set_from_index(ints, i)
        iset_length = len(iset)
        if iset_length > max_length:
            max_length = iset_length
    return max_length

My solution utilizes two functions build_set_from_index and return_longest_length.

build_set_from_index

build_set_from_index returns the set[starting_index] constructed from the parameters ints and starting_index. I used an iterative approach to construct set[].

My approach emerged from an early morning and a subsequent paraphrasing of the set[] construction rules. Initially, these rules seemed complex. But, after re-reviewing Example 1 after a decent breakfast and caffeine, I better understood these rules. I was also able to formulate the following paraphrase.

• set[i] is a set with k elements.
  • Rule 3 bounds the value of k.
  • Rule 3 dictates when to stop adding elements to set[i].
• The value of set[i] at k = 0 is equal to ints[i].
• For k > 0, the k-th element of set[i] is equal to value of ints[] indexed using the (k-1)-th element of set[i].

Using the paraphrased approach, interatively constructing set[0] from @ints, as in Example 1, became even more straightforward!

• At k = 0, the value of set[0] is equal to ints[0] = 5. set[0] contains {5}.
• At k = 1, the value of set[0] is equal to ints[5] = 6. set[0] contains {5, 6}.
• At k = 2, the value of set[0] is equal to ints[6] = 2. set[0] contains {5, 6, 2}.
• At k = 3, the value of set[0] is equal to ints[2] = 0. set[0] contains {5, 6, 2, 0}
• At k = 4, STOP because set[0] contains ints[0] = 2.

return_longest_length

return_longest_length finds the maximum length of all set[] constructed from ints. It utilizes build_set_from_index to generate set[k] for each 0 <= k < len(ints) and then indentifies the set[k] with the longest length.

4. Conclusion

In this post I discussed Task 1: Nested Array and I presented my solution. My solution is straightforward, was largely informed by how I paraphrased the original task, and highlights the importance of a good breakfast.