- 20th Jan 2022
- 00:12 am
This module will contain all functions that you must implement. It will serve as the main file to be created during testing.
Usage:
- Contains functions that will be implemented to stop the Alien Invasion!
"""
import random
class AlienInvasion:
"""
Alien Invasion Class
Contains three functions to be implemented:
1. `is_sorted(A)` - returns whether the array is sorted.
2. `count_markers(A, c)` - returns the number of indices `i` such that
| A[i] - i | <= c.
3. `break_control(A, c)` - returns a "random" index that satisfies
|A[i] - i | <= c.
"""
@staticmethod
def is_sorted(A: list) -> bool:
"""
Checks whether the given list of genetic code is sorted in
increasing order.
If the array (A) is None, return None.
:param A: A list of indices.
:return: True if sorted, else False.
"""
if A is None:
return None
elif len(A) == 0:
return None
elif (A == sorted(A)):
return True
elif (A != sorted(A)):
return False
else :
return None
def helper(self, A, c):
low = 0
high = len(A) - 1
if A[0] >= 0 :
while low <= high:
mid = (low + high) // 2
if low == high and (c == (A[mid]-mid)):
return mid + 1
elif low == high and (c > (A[mid]-mid)):
return mid + 1
elif low == high and (c < (A[mid]-mid)):
return mid
elif low == high:
return 0
if c < (A[mid]-mid):
high = mid - 1
else:
low = mid + 1
return low
else :
while low <= high:
mid = (low + high) // 2
if low == high and (c == abs(A[mid]-mid)):
return len(A[mid:])
elif low == high and (c > abs(A[mid]-mid)):
return len(A[mid:])
elif low == high and (c < abs> return len(A[mid+1:])
elif low == high:
return 0
if c < abs> low = mid + 1
else:
high = mid - 1
return len(A)
def count_markers(self, A: list, c: int) -> int:
"""
Counts the number of elements in A such that | A[i] - i | <= c
If there are no numbers that satisfy the condition, return 0.
If the array is None, return None.
Example:
A = [1, 2, 4, 8, 16, 32, 64]
c = 4
A[0] = | 1 - 0 | = 1.
A[1] = | 2 - 1 | = 1.
A[2] = | 4 - 2 | = 2.
A[3] = | 8 - 3 | = 5.
A[4] = | 16 - 4 | = 12.
A[5] = | 32 - 5 | = 27.
A[6] = | 64 - 6 | = 58.
AlienInvasion.count_markers(A, c) -> 3
:param A: A **SORTED** array of integers in increasing order.
:param c: The integer threshold
:return: The number of elements that satisfy the condition.
"""
if A is None:
return None
elif len(A) == 0:
return 0
else:
return self.helper(A, c)
def break_control(self, A: list, c: int) -> int:
"""
Returns a **random** index such that A[i] satisfies:
| A[i] - i | <= c
If there are no numbers/indices that satisfy the conditions, or if
the array is None, return `None`.
Example:
A = [1, 2, 4, 8, 16, 32, 64]---------
c = 4
A[0] = | 1 - 0 | = 1.
A[1] = | 2 - 1 | = 1.
A[2] = | 4 - 2 | = 2.
A[3] = | 8 - 3 | = 5.
A[4] = | 16 - 4 | = 12.
A[5] = | 32 - 5 | = 27.
A[6] = | 64 - 6 | = 58.
AlienInvasion.break_control(A, c)
Will return either: 0, 1 or 2.
` :param A: A **SORTED** list of integers in increasing order.
:param c: The integer threshold.
:return: The **INDEX** of an element that satisfies the condition.
"""
if A is None:
return None
elif len(A) == 0:
return None
else:
num = self.helper(A, c)
if num == 0:
return None
else:
if A[0] >= 0:
return random.choice(list(range(num-1)))
else:
return random.choice(list(range((len(A)-num), len(A))))
