Detecting repeated sequence of same elements at the end of a list

Question

I have a list of binary numbers (converted to strings) in a list. I want to detect if the list ends in a cycle or not, i.e if an ongoing repeating sequence of same numbers is detected when the list ends.

For example, the list ["1101", "1001", "1010", "1010", "1010", "0011", "0011", "1111", "1110", "0111", "1101", "1010", "0101", "1101", "1010", "0101", "1101", "1010", "0101", "1101"] ends with a cycle of repeating "1101", "1010", "0101"

Also all of the binary numbers are of the same fixed length (4 here), and the length of the list is also fixed (20 in this case), if that helps. Another catch is that there might be repetitions of the same binary number, which are not considered cycle. I think I should just filter the list before processing so that there is no consecutive same number in the list, but I'm not sure if that'll help.

The code I have tried so far looks like:

def detect_cycle(arr: list) -> bool:
    """Should return True iff there is an ongoing cycle at the end of the list. Cycle here can be defined as a repeated sequence
    that appears in the list in the same order multiple times consecutively.

    :param list arr: The list in which cycle has to be detected.
    :return bool: Returns True iff a cycle is detected at the end of the list, False otherwise.
    """
    res = False
    arr_len = len(arr)
    rev_arr = list(reversed(arr))
    for rev_ix, elem in enumerate(rev_arr):
        if rev_ix == arr_len // 2 + 1 or res:
            break
        for i in range(arr_len // 2):
            if rev_arr[rev_ix : rev_ix + i] == rev_arr[rev_ix + i : rev_ix + 2 * i]:
                res = True
    return res

But this function is returning a lot of False positives. Any way to fix and/ or optimize this?

Thanks in advance.

Answer 1

Your code is setting res to True when just one equality comparison succeeds. Yet it is clear that you need a whole series of comparisons to be equal before you could decide there is a cycle.

You could compare slices like this:

def detect_cycle(arr: list) -> bool:
    return any(arr[-i:] == arr[-2*i:-i] for i in range(2, len(arr) // 2 + 1))

Example

Taking the input from the question:

["1101", "1001", "1010", "1010", "1010", "0011", "0011", "1111", "1110", "0111", "1101", "1010", "0101", "1101", "1010", "0101", "1101", "1010", "0101", "1101"]

This code has i going from 2 to half of the size of the input, and -i and -2*i are used as boundaries for slices.

When i is 2, this compares arr[-2:] with arr[-4:-2], when i is 3, it compares arr[-3:] with arr[-6:-3], ...etc, as in this table:

i	arr[-i:]	arr[-2*i:-i]	equal?
2	["0101", "1101"]	["1101", "1010"]	No
3	["1010", "0101", "1101"]	["1010", "0101", "1101"]	Yes

The any function will stop further iterations when it has found an equality, so in this example the iteration stops and True is returned.

If none of the compared slices are equal then any will return False.