CODEWITHSUNDEEP
pythonrecursion
Brais Romero
Brais Romero

Reputation: 35

Find the possible slide downs in a pyramid

I'm losing my mind with this codewars/project euler problem: https://www.codewars.com/kata/551f23362ff852e2ab000037/train/python

I need to find the max sum in all of the possible pyramid slide downs, and as of right know I'm trying to calculate the possible slide downs that exist in the pyramid. It works fine but for integers bigger than 25 the function begins to be really slow.

My code is this:

def find_seq(x):
'''
input: x, positive integer greater than 1

Returns an array with the slides from the top to the bottom of
an x floors high pyramid
'''
list_slides = []
if x == 2:
    return [[0,0],[0,1]]
else:
    prev_slides = find_seq(x-1)
    for el in prev_slides:
        list_slides.append([0]+el)
    for el in prev_slides:
        list_slides.append([0]+list(i+1 for i in el))
return list_slides

I can see that for each new floor the calculating time grows exponentially but I can't think of any other way to adress the problem.

Upvotes: 0

Views: 2991

Answers (1)

GalSuchetzky
GalSuchetzky

Reputation: 805

tl;dr: Go from the bottom up for linear complexity.

Well, you are right it grows exponentially.
The problem is not your code, but your direction.
Let's look at the pyramid from bottom up - you can see right away that if you are at the second to last layer and you want to slide down, you will choose the path that is directly under you and has the larger value, i.e you can slide only left or right and the bigger will be better.
Now, going up to the third to last, you only need to find the route down to the floor below which is the best (summing up the value of the bottom floor of course).
keep going like that to the top of the pyramid and by the end, you get the value of the best route, or longest slide.

code:

def longest_slide_down(pyramid):
    if len(pyramid) == 1:
        return pyramid[0][0]

    last_layer = pyramid[-1]
    add_layer = []
    for i in range(1, len(last_layer)):
        add_layer.append(max(last_layer[i], last_layer[i-1]))
    
    pyramid[-2] = [a+b for a, b in zip(pyramid[-2], add_layer)]
    
    return longest_slide_down(pyramid[:-1])

And for the efficiency seekers out there, a numpyed version of the same code:

import numpy as np
def longest_slide_down(pyramid):
    if len(pyramid) == 1:
        return pyramid[0][0]
    
    pyramid = np.array(pyramid)
    pyramid[-2] += np.maximum(pyramid[-1][:-1], pyramid[-1][1:])
    return longest_slide_down(pyramid[:-1])

Upvotes: 0

Related Questions