forked from adnanaziz/EPIJudge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
is_list_cyclic.py
63 lines (52 loc) · 1.88 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
import functools
from sys import exit
from test_framework import generic_test, test_utils
from test_framework.test_failure import TestFailure
from test_framework.test_utils import enable_executor_hook
def has_cycle(head):
# Implement this placeholder.
return None
@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.tsv',
has_cycle_wrapper))