CODEWITHSUNDEEP
pythonlistfunctionpython-2.7cycle
Aleish
Aleish

Reputation: 65

function that checks the length of the cycle

Hey guys i have the function, but it gives me error when I test it. Does anyone have any Idea on how to fix it This is my exercise. Please read through.

Write a function cycleLength(array), which returns the number of students that form a loop, given that you start by talking to the left-most one. The input array is a list of non-negative integers, such that array[m] is the number of the student to whom student m redirects. No student redirects to himself. The left-most student is number 0, the next is number 1, and so on. Each element in the list will be in the range [0, n-1] where n is the length of the list. For example, suppose the list was [1, 3, 0, 1]. Then student 0 redirects to student 1, who redirects to student 3, who redirects back to student 1. There is a loop of two students: 1, 3. Thus the answer would be 2. Note that even though you started with student 0, he is not part of the loop. Here is my function:

def cycleLength(m):
    lst = []
    i = 0
    while i not in lst:
        lst.append(i)
        i = int(m[i])

    b = len(lst) - lst.index(i)
    return b

Upvotes: 0

Views: 1757

Answers (2)

Nir Alfasi
Nir Alfasi

Reputation: 53535

def cycleLength(m):
    lst = []
    for x in m:  
        if x in lst:
            return len(lst) - lst.index(x)
        lst.append(x)     

    return -1

Explanation:

  1. you should loop while the element at index i m[i] is not already in lst - what you where doing is looking for the index in the list instead of "the element at index"
  2. Same as previous point, you should append to lst the elements - not the index of the elements - otherwise you won't find any such "duplicate" elements - since the index should just increase.
  3. Regards the last point - the index should keep increasing on each iteration
  4. And last, the length of the cycle is between the first time that an element appears to the next time that you iterate the same element. And it's not necessarily from the beginning of the list.

Correction:

Previous version of the code had bugs, a simpler version of the same idea, and which is also bug-free (I believe), is posted here. -1 represents "no cycles found".

Upvotes: 1

thefourtheye
thefourtheye

Reputation: 239593

You almost got it right.

>>> def cycleLength(students):
...     seen = []
...     current = 0
...     # Run till we have seen all the students
...     while len(seen) != len(students):
...         # If the current index has been seen already
...         if current in seen:
...             return len(seen) - seen.index(current)
...         seen.append(current)
...         current = students[current]
... 
>>> assert(cycleLength([1, 3, 0, 1]) == 2)
>>> assert(cycleLength([1, 3, 0, 2]) is None)

This will take care of the case where there is no loop as well.

Upvotes: 3

Related Questions