forked from adnanaziz/EPIJudge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
is_list_cyclic.py
84 lines (71 loc) · 2.61 KB
/
is_list_cyclic.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import functools
from test_framework import generic_test
from test_framework.test_failure import TestFailure
from test_framework.test_utils import enable_executor_hook
def has_cycle(head):
def cycle_len(end):
start, step = end, 0
while True:
step += 1
start = start.next
if start is end:
return step
fast = slow = head
while fast and fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
# Finds the start of the cycle.
cycle_len_advanced_iter = head
for _ in range(cycle_len(slow)):
cycle_len_advanced_iter = cycle_len_advanced_iter.next
it = head
# Both iterators advance in tandem.
while it is not cycle_len_advanced_iter:
it = it.next
cycle_len_advanced_iter = cycle_len_advanced_iter.next
return it # iter is the start of cycle.
return None # No cycle.
@enable_executor_hook
def has_cycle_wrapper(executor, head, cycle_idx):
cycle_length = 0
if cycle_idx != -1:
if head is None:
raise RuntimeError("Can't cycle empty list")
cycle_start = None
cursor = head
while cursor.next is not None:
if cursor.data == cycle_idx:
cycle_start = cursor
cursor = cursor.next
cycle_length += 1 if cycle_start is not None else 0
if cursor.data == cycle_idx:
cycle_start = cursor
if cycle_start is None:
raise RuntimeError("Can't find a cycle start")
cursor.next = cycle_start
cycle_length += 1
result = executor.run(functools.partial(has_cycle, head))
if cycle_idx == -1:
if result is not None:
raise TestFailure("Found a non-existing cycle")
else:
if result is None:
raise TestFailure("Existing cycle was not found")
cursor = result
while True:
cursor = cursor.next
cycle_length -= 1
if cursor is None or cycle_length < 0:
raise TestFailure(
"Returned node does not belong to the cycle or is not the closest node to the head"
)
if cursor is result:
break
if cycle_length != 0:
raise TestFailure(
"Returned node does not belong to the cycle or is not the closest node to the head"
)
if __name__ == '__main__':
exit(
generic_test.generic_test_main(
"is_list_cyclic.py", 'is_list_cyclic.tsv', has_cycle_wrapper))