- 20th Jan 2022
- 06:03 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))))