Maximum path sum with prime number check in python

Question

There is a task similar to project euler 18, but this time you can only walk over non prime numbers. Task is:

You will have a triangle input below and you need to find the maximum sum of the numbers according to 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.

According to above rules what is the maximum sum of below input? It means please take this pyramid as an input (as file or constants directly inside the code) for your implementation and solve by using it.

                              215
                           193 124
                         117 237 442
                       218 935 347 235
                     320 804 522 417 345
                   229 601 723 835 133 124
                 248 202 277 433 207 263 257
               359 464 504 528 516 716 871 182
             461 441 426 656 863 560 380 171 923
           381 348 573 533 447 632 387 176 975 449
         223 711 445 645 245 543 931 532 937 541 444
       330 131 333 928 377 733 017 778 839 168 197 197
    131 171 522 137 217 224 291 413 528 520 227 229 928
  223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233

First, tried to solve it without the 3rd condition(only walk over non prime number):

num="""215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"""

rows=num.split("\n")
array=list()
for row in rows:
    num_list=row.split(" ")
    array.append(num_list)

for i in range(0,len(array)):
    for j in range(0,i+1):
        array[i][j] = int(array[i][j])

for i in range(len(array)-1, -1, -1):
    for j in range(0,i):
        array[i-1][j] += max(array[i][j], array[i][j+1])

print(array[0])

At this point, i dont know how to put the prime number check into this code and find the true solution because above code output is 9022

---edit---

I added the prime number check to print if a number is/is not a prime number:

def isprime(n):
    if n < 2: return False

    for i in range(2, n):
        if n % i == 0:
            print("non prime")
            break
    else:
        print("prime")

for i in range(0,len(array)):
    for j in range(0,i+1):
        print(isprime(array[i][j]))

How should i make it skip the prime numbers and continue with non prime ones?

Karina · Accepted Answer · 2021-08-15 10:44:08Z

I actually tried to solve it with multiple ways, but all other methods that I tried are way way way slower than this one. I'm pretty sure this is not the best method, but it works anyway. To call the function you need solvearray(num) and the num must always have the same format as the one you gave as an example. I took your isprime(n) function but modify the structure a little bit. This is my code:

num="""215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"""

def solvearray(num):
    def get_array(num):
        rows = num.split("\n")
        array = []
        for row in rows:
            num_list=row.split(" ")
            num_list = list(map(int, num_list))
            array.append(num_list)
            print(num_list)
        return array

    print('array: this is the array to be solved')
    array = get_array(num)

    def isprime(n):
        if n < 2: return False

        for i in range(2, n):
            if n % i == 0:
                p = 0 # is prime
                break
        else:
            p = 1 # not prime
        return p

    dim = len(array)

    def get_isprime(array):
        primearray = []
        for row in range(len(array)):
            parray = []
            for col in range(len(array[row])):
                parray.append(isprime(array[row][col]))
            primearray.append(parray)
            print(parray)
        return primearray

    print('parray: this shows if each number in array is prime')
    primearray = get_isprime(array)


    path = [0]
    branch = []
    for row in range(len(path),dim):
        col = path[-1]
        if primearray[row][col] == 0 and primearray[row][col+1] == 1:
            col = col
            path.append(col)
        elif primearray[row][col] == 1 and primearray[row][col+1] == 0:
            col = col + 1
            path.append(col)
        elif primearray[row][col] == 1 and primearray[row][col+1] == 1:
            break
        elif primearray[row][col] == 0 and primearray[row][col+1] == 0:
            col = col
            path.append(col)
            branch.append(row)

    allpath = []
    while len(path) != dim or branch != []:
        try:
            del path[branch[-1]+1:len(path)]
            del branch[-1]
            path[-1] = path[-1] + 1
        except IndexError:
            break

        for row in range(len(path),dim):
            col = path[-1]
            if primearray[row][col] == 0 and primearray[row][col+1] == 1:
                col = col
                path.append(col)
            elif primearray[row][col] == 1 and primearray[row][col+1] == 0:
                col = col + 1
                path.append(col)
            elif primearray[row][col] == 1 and primearray[row][col+1] == 1:
                break
            elif primearray[row][col] == 0 and primearray[row][col+1] == 0:
                col = col
                path.append(col)
                branch.append(row)
        if len(path) == dim:
            if path not in allpath:
                allpath.append(path[:])

    actualpath = []
    maxsum = []
    for i in range(len(allpath)):
        onepath = []

        for j in range(dim):
            onepath.append(array[j][allpath[i][j]])
        actualpath.append(onepath)
        maxsum.append(sum(onepath))
    print('index path :', allpath[maxsum.index(max(maxsum))])
    print('actual path:', actualpath[maxsum.index(max(maxsum))])
    print('sum of path: ',max(maxsum))
    
import time
t1 = time.time()
solvearray(num)
t2 = time.time()
print(f'the function took {t2-t1} s to solve this problem')

The import time is actually not part of the function, just for me to check the computational time. I printed out a lot so that you can actually see what is done in which step. This is the full output:

array: this is the array to be solved
[215]
[193, 124]
[117, 237, 442]
[218, 935, 347, 235]
[320, 804, 522, 417, 345]
[229, 601, 723, 835, 133, 124]
[248, 202, 277, 433, 207, 263, 257]
[359, 464, 504, 528, 516, 716, 871, 182]
[461, 441, 426, 656, 863, 560, 380, 171, 923]
[381, 348, 573, 533, 447, 632, 387, 176, 975, 449]
[223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444]
[330, 131, 333, 928, 377, 733, 17, 778, 839, 168, 197, 197]
[131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928]
[223, 626, 34, 683, 839, 53, 627, 310, 713, 999, 629, 817, 410, 121]
[924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233]
parray: this shows if each number in array is prime
[0]
[1, 0]
[0, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1]
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1]
index path : [0, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 8]
actual path: [215, 124, 237, 935, 522, 835, 207, 716, 560, 632, 931, 778, 528, 713, 253]
sum of path:  8186
the function took 0.006632566452026367 s to solve this problem

Hope it helps. Let me know if something is still unclear.

Alain T. · Accepted Answer · 2021-09-17 03:45:21Z

You can identify all primes using the sieve of Eratosthenes and flag them in the triangle list (i'm using None as the indicator).

Then go from the bottom to the top while tracking the current maximums based on the previous result. Each iteration will reduce the size of the path by one entry and you will end up with a single item list containing the maximum path.

This is practically the same thing as what your code is doing except for the flagging of primes and skipping of the flagged entries.

num="""215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"""

tri = [ [*map(int,line.split())] for line in num.split("\n") ]

Find primes in range of largest value

maxValue = max(map(max,tri))
isPrime = [0,0]+[1]*(maxValue-1) # Sieve of Eratosthenes
p,inc = 2,1
while p*p<=maxValue:
    if isPrime[p]:
        isPrime[p*p::p] = [0]*len(range(p*p,len(isPrime),p))
    p,inc = p+inc,2

Flag primes as None in triangle list:

tri = [ [None if isPrime[n] else n for n in row] for row in tri ]

Accumulate largest total from bottom to top (skipping None entries)

path = tri[-1]
for row in tri[-2::-1]:
    path = [ None if n is None or (a,b)==(None,None) else n+max(a or 0,b or 0)
             for n,a,b in zip(row,path,path[1:]) ]
    
print(path[0]) # 8186 (113 microseconds on my laptop)

Collectives™ on Stack Overflow

Maximum path sum with prime number check in python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related