## Python Assignment Solution on Alien Invasion

• 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))))

```