CodeEval Detecting Cycles

Getting in input a list of integers, we should identify where a cycle starts, and return it.
It's the CodeEval problem #5, and it is easier than it looks, because, even if it is not explicitly said, the passed samples suggest that the numbers are present only once, if their are not in a cycle. Maybe we should think of them as labels in a graph, and the sequence could represent the result of a traversal algorithm that enters in an infinite loop.

I have converted the samples in python tests, I added one more just because I felt bad of risking an exception if the detected cycle was interrupted in the input sequence.
def test_provided_1(self):
    self.assertEqual('6 3 1', solution('2 0 6 3 1 6 3 1 6 3 1'))

def test_provided_2(self):
    self.assertEqual('49', solution('3 4 8 0 11 9 7 2 5 6 10 1 49 49 49 49'))

def test_provided_3(self):
    self.assertEqual('1 2 3', solution('1 2 3 1 2 3 1 2 3'))

def test_tail(self):
    self.assertEqual('1 2', solution('1 2 3 1 2'))
For how the test case look, we simply have to search for the first repetition, and then count how many elements fit in the cycle. I assumed, see the last test, that we should return only the elements in the cycle we are sure are repeated.

The core of my solution is a triple (!) for loop:
for i in range(len(data)-1):
    for j in range(i+1, len(data)):
        if data[i] != data[j]:
            continue

        size = min(j - i, len(data) - j)  # 1
        for k in range(1, size):
            if data[i+k] != data[j+k]:  # 2
                size = k
                break
        return ' '.join(data[i:i+size])
return ''
1. I loop until I find two matching numbers. At this point I ensure that this is really a loop, checking that there is a match between the following numbers on the left and on the right. I added the extra check on the list size to avoid falling off the end.
2. When I complete the check, maybe finding a spurious element, I stop looping and return the found cycle.

Solution accepted, unit test and python script pushed to GitHub.

No comments:

Post a Comment