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