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

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.

The above is the detailed content of My Python Language Solution to Task Nested Array from The Weekly Challenge. For more information, please follow other related articles on the PHP Chinese website!