Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.8 kB
1
Indexable
Never
# This is a program written in Python3

from math import sqrt

def isPrime(number):
    square_root = int(sqrt(number)+1)

    if number == 2: return True

    for i in range(2,square_root+1):
        if number % i == 0:
            return False
    return True

# Script takes the triangle input as a constant in the code
# The below triangle input is just an EXAMPLE and a PLACEHOLDER
# Which means user must replace the below triangle with the actual input
# AS STRUCTURED LIKE BELOW
TRIANGLE="""
1
8 4
2 6 9
8 5 9 3"""

structured_triangle = [[int(num) for num in row.split()] for row in TRIANGLE.split("\n")]

if structured_triangle[0] == []:
    structured_triangle = structured_triangle[1:]

if structured_triangle[-1] == []:
    structured_triangle = structured_triangle[:-1]

sums = [[structured_triangle[0]]]

for i in range(len(structured_triangle)):
    if i == 0: continue
    sums.append([])
    for j in range(len(structured_triangle[i])):

        if isPrime(structured_triangle[i][j]):
            sums[i].append([])
            continue

        if j == 0:
            sums[i].append([num + structured_triangle[i][j] for num in sums[i-1][j]])
        elif j == len(structured_triangle[i]) - 1:
            sums[i].append([num + structured_triangle[i][j] for num in sums[i-1][j-1]])
        else:
            tmp_list = []
            for num in sums[i-1][j]:
                tmp_list.append(num + structured_triangle[i][j])
            for num in sums[i-1][j-1]:
                tmp_list.append(num + structured_triangle[i][j])

            sums[i].append(tmp_list)

final_sums = []

for row in sums[-1]:
    for num in row:
        final_sums.append(num)

print(max(final_sums))