bfs_dynamic.py

#!/usr/bin/env python3
import math
import time


def isPrime(n):
    max_divisor = math.floor(math.sqrt(n))
    for d in range(2, max_divisor+1):
        if n % d == 0:
            return False
    return True

def getNextSmallerPrime(n):
    for i in range(n-1, 0, -1):
        if isPrime(i):
            return i
    return 0
 
def bfs_dynamic(leftOver, currentNumber, dynamicResults, dynamicNextN): # breadth first search
    
    # We solve the same problem over and over again, therefore solve it using
    # references.

    # Get dynamic data of current number
    dynamicDataForCurrentNumber = dynamicResults.get(currentNumber)
    if dynamicDataForCurrentNumber is None:
        dynamicDataForCurrentNumber = dict()
        dynamicResults[currentNumber] = dynamicDataForCurrentNumber

    # If we already computed the result, return it
    dynamicResult = dynamicDataForCurrentNumber.get(leftOver)
    if dynamicResult is not None:
        return dynamicResult

    # Get next smaller prime, also dynamic
    nextN = dynamicNextN.get(currentNumber)
    if nextN is None:
        nextN = getNextSmallerPrime(currentNumber)
        dynamicNextN[currentNumber] = nextN
   
    # Compute all possible results for currentNumber in leftover:
    resultList = []
    numResults = 0
    subLeftOver = leftOver - currentNumber
    
    # If adding one of the current number makes it complete, add it to the results
    if subLeftOver == 0:
        resultList.append([currentNumber])
        numResults += 1
    
    # Otherwise, try with another number of the same type
    elif subLeftOver > 0:
        subResult, numSubResults = bfs_dynamic(subLeftOver,
                                               currentNumber,
                                               dynamicResults,
                                               dynamicNextN)
        resultList.append([currentNumber, subResult])
        numResults += numSubResults

    # Iterate down to next prime
    if nextN != 0:
        subResult, numSolutions = bfs_dynamic(leftOver,
                                              nextN,
                                              dynamicResults,
                                              dynamicNextN)
        nextResult = [subResult]
        resultList.append(nextResult)
        numResults += numSolutions

    # Store result in dynamic array
    dynamicResult = (resultList, numResults)
    dynamicDataForCurrentNumber[leftOver] = dynamicResult

    return dynamicResult
           
def convertDynamicStructureToArrays(results, parentPrefix=[], arrayResults=[]):
    for result in results:
        prefix = []
        hadList = False
        for resultElement in result:
            if isinstance(resultElement, list):
                hadList = True
                convertDynamicStructureToArrays(resultElement,
                                                parentPrefix + prefix,
                                                arrayResults)
            else:
                prefix += [resultElement]
        if not hadList:
            arrayResults.append(parentPrefix + prefix)
    return arrayResults

def main():
    n = 5
    start_time = time.perf_counter()
    dynamicResults = dict()
    dynamicNextN = dict()
    results, numSolutions = bfs_dynamic(n,
                                        getNextSmallerPrime(n+1),
                                        dynamicResults,
                                        dynamicNextN)
    end_time = time.perf_counter()
    
    print("Num Solutions:", numSolutions)

    # Converting the result to actual arrays takes the longest time.
    # If you just need to iterate through the result, you don't need to convert,
    # you can directly work on the dynamic structure.
    # But it's quite complicated.
    arrayResults = convertDynamicStructureToArrays(results)

    for result in arrayResults:
        print(result)
    print("--- %s milliseconds ---" % (1000*(end_time - start_time)))

if __name__ == "__main__":
    main()