PIassignment.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 11:51:59 2020

@author: macintosh
"""

def parseInput(filename): 
    """
    Create our pyramid from the txt file.
    """

    pyramid = []

    file = open(filename, "r")
    
    row = 0
    
    for line in file:
        pyramid.append([])  
        columns = line.split()
        
        for col in columns:
            pyramid[row].append(int(col))
        
        row += 1
            
    file.close()
    
    return pyramid


def is_prime(num):
    """
    A generic function to check if a number is prime.
    """
    
    if num > 1:
        for i in range(2, int(num)):
            if (num % i) == 0:
                return False
    else:
        return False
    
    return True

def nextNonPrimes(pyramid, row, column):
    """
    Find the next non-prime numbers downwards and diagonally, and return 
    their indices.
    """
    
    nextStates = []
    
    if(row == len(pyramid)-1):  #we reached the end of pyramid
        return nextStates

    if not is_prime(pyramid[row+1][column]):
        nextStates.append((row+1,column))
    
    if not is_prime(pyramid[row+1][column+1]):
        nextStates.append((row+1,column+1))
        
    return nextStates    

def searchPyramid(pyramid, row=0, column=0):
    """
    Depth-first search of our pyramid to find all solutions and the paths for 
    those solutions.
    """
    
    current_state = pyramid[row][column]
    nextStates = nextNonPrimes(pyramid, row, column)
    
    if(len(nextStates) == 0):
        return [(current_state,[current_state])]
   
    else:
        
        solutions = []
        
        for (row,col) in nextStates:
            for (num,path) in searchPyramid(pyramid, row, col):
                summ = current_state + num
                path.insert(0,current_state)
                solutions.append((summ,path))    
                
        return solutions
    
def applyConditions(solutions):
    """
    Apply the conditions of "having the longest path" and "the greatest sum"
    to give a final solution
    """
    
    final_solution = (0,[])
    solutions = sorted(solutions, reverse = True) #sort #s in desc. order
    
    for solution in solutions: #sort longest path
        if(len(solution[1]) > len(final_solution[1])):
            
            final_solution = solution
    
    return final_solution
    
def Run():     
    
    filename = "example.txt"     
    pyramid = parseInput(filename)
    
    solutions = searchPyramid(pyramid)
    final_solution = applyConditions(solutions)
        
    print(final_solution)  #Print the best answer
    
Run()