'''
P.I. WORKS Technical Assignment 
Simay Yazicioglu

This script finds maximum sum of the numbser in a  orthogonal triangle input 
according to the given rules below:
1. You will start from the top and move downwards to an adjacent number as in below.
2. You are only allowed to walk downwards and diagonally.
3. You can only walk over NON PRIME NUMBERS.
4. You have to reach at the end of the pyramid as much as possible.
5. You have to treat your input as pyramid.

This file can also be imported as a module and contains the following
functions:
    * fill_array - returns a 2D array based on the triangle input in the file
    * is_prime - given a number returns if the number is prime or not
    * solve -uses dynamic programming to find maximum sum in the 2D array
    * main- main function of the script
'''
def fill_array(file_name):
    """reads the file, gets the triangular input, 
    and fills the 2D array based on the input data

    Parameters
    ----------
    file_name : string
        The name of the file that contains the triangle input
    
    Returns
    -------
    array
        2D array that represents the data in the triangle input
    """
    with open(file_name, 'r') as file_obj:
        count = 0
        array =  []#2D array
        for line in file_obj:
            count+=1
            line_lst = line.strip().split(" ")
            array_row = []
            for num in line_lst:
                if is_prime(int(num)):
                    array_row.append(float('-inf'))
                else:
                    array_row.append(int(num))
            array.append(array_row)
        #fill the rest of the array_row with 0
        for row  in range(count):
            for col in range(count-row-1, 0, -1):
                array[row].append(0)
        return array

def is_prime(n):
    """checks if the number is prime

    Parameters
    ----------
    n : int
        The number we want to check
    
    Returns
    -------
    boolean
        True if number is prime, false otherwise
    """
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True

def solve(arr): 
    """uses dynamic programming to find maximum sum in the 2D array

    Parameters
    ----------
    arr : list
        The 2D array that represents the triangle input values
    
    Returns
    -------
    float
        returns the max sum, or if that's not possible  returns negative infinity
    """
    row = len(arr)
    for r in range(row-1-1, -1,-1):
        for c in range(0,r+2-1):
            elem1 = arr[r+1][c]
            elem2 =  arr[r+1][c+1]
            #if either of the elems are -inf, then dont check prime
            if elem1 == float('-inf') and elem2==float('-inf'):
                continue
            elif  not (elem1 == float('-inf')) and not (elem2==float('-inf')):
                    m = max(arr[r+1][c+1] , arr[r+1][c])
                    arr[r][c] += m  # current arr[r][c]
            elif elem1 == float('-inf'): #only elem1 negative infinity
                arr[r][c] += elem2  # current arr[r][c]
            else: #only elem2 negative infinity
                arr[r][c] += elem1  # current arr[r][c]
    return arr[0][0]
    
def main():
    '''
    Main function for the script.
    Given a file name, main function calls the function to fill the array with the triangle input given in the file
    and calls the function to find the max sum.
    Then prints the maximum sum if found, else prints 'No possible path' 
    '''
    arr = fill_array('triangle.txt')
    path_sum = solve(arr)
    if path_sum == float('-inf'):
        print('No posssible path')
    else:
        print(path_sum)

if __name__ == "__main__":
    main()