deliberate-practice2/circularArray.py at main · NGWi/deliberate-practice2 · GitHub

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
85
86
87
def is_positive(num):
  if num < 0:
    return False
  else:
    return True

def move_pointer(index, move, length):
  print("Moving pointer", index, "+", move)
  target = index + move
  while target >= length:
    target -= length
  while target < 0:
    target += length
  print (target)
  return target


def circular_array_loop(nums):
  index = 0
  length = len(nums)
  while index < length:
    slow = index
    med = 0
    fast = move_pointer(index, nums[index], length)
    direction = is_positive(nums[slow])
    print(fast, slow)
    index += 1
    if slow == fast:
      continue
    while True:
        next = move_pointer(slow, nums[slow], length)
        if next == slow or is_positive(nums[slow]) != direction:
          break
        else:
          slow = next

        next =  move_pointer(fast, nums[fast], length)
        if next == fast or is_positive(nums[med]) != direction:
          break
        else:
          med = next

        next = move_pointer(med, nums[med], length)
        if next == med or is_positive(nums[fast]) != direction:
          break
        else:
          fast = next

        if slow == fast:
          return True

  return False

print(circular_array_loop([1,3,-2,-4,1]))
print("*" * 10)
print(circular_array_loop([2,1,-1,-2]))
print("*" * 10)
print(circular_array_loop([5,4,-2,-1,3]))
print("*" * 10)
print(circular_array_loop([1,2,-3,3,4,7,1]))
print("*" * 10)
print(circular_array_loop([3,3,1,-1,2]))
print("*" * 10)
print(circular_array_loop([1,1,1,1,1]))
print("*" * 10)
print(circular_array_loop([1, 2, 3, 4, 5, 6]))
print("*" * 10)
print(circular_array_loop([0]))
print("*" * 10)
print(circular_array_loop([]))

# input = (
#         [-2, -3, -9],
#         [-5, -4, -3, -2, -1],
#         [-1, -2, -3, -4, -5],
#         [2, 1, -1, -2],
#         [-1, -2, -3, -4, -5, 6],
#         [1, 2, -3, 3, 4, 7, 1],
#         [2, 2, 2, 7, 2, -1, 2, -1, -1]
#         )
# num = 1

# for i in input:
#     print(f"{num}.\tCircular array = {i}")
#     print(f"\n\tFound loop = {circular_array_loop(i)}")
#     print("-"*100, "\n")
#     num += 1