Ad
  • Custom User Avatar

    You are using index method to find the first occurrence of actual, but there may be duplicate values in each row.

  • Custom User Avatar

    OP solved it, closing

  • Custom User Avatar

    Apparently not. You must traverse all grids whether starting from bottom or at the top to identify the maximum path down the pyramid. The T.C can be O(N^2) if N is the length of the bottom row of the pyramid or just O(N) whereby N is the number of cells in the pyramid.

  • Custom User Avatar

    OP solved it, closing

  • Custom User Avatar

    Neither. The number of path to reach each cell of the pyramid can be represented by the pascal triangle. As for how to derive those numbers, a simple visualization with a pen and paper should suffice! ^^

  • Custom User Avatar
  • Custom User Avatar

    'down' can be misleading.
    I found it misleading. doesnt mean everyone will find it misleading.
    Sorry for the confusion. Should have clarifed that only some people would be confused by it.

  • Custom User Avatar

    Recursion has a T.C of O(2^N) which is too slow here. However, you had already found the recurrene relation with recursion, so you can simplify the code to a top-down / bottom-up iterative approach, which will cost at most O(N) time whereby N is the total sum of each row's length

  • Custom User Avatar

    down is not misleading. It can go down to the next row's left (if it has one) or right (if it has one) or both (if it is in the bounds of the pyramid) The visualization is clear regarding this aspect, as for the latter wording, it has been raised below

  • Custom User Avatar

    Resolved

  • Custom User Avatar

    Yeah, output is (23, 23) now. I thought the tests are isolated. Ok, I'll take care about it. Thank you!

  • Custom User Avatar

    It's not a problem in the tests, try calling your function locally like in the tests, that is, one after the other:

    print(longest_slide_down([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]))
    print(longest_slide_down([
                [75],
                [95, 64],
                [17, 47, 82],
                [18, 35, 87, 10],
                [20,  4, 82, 47, 65],
                [19,  1, 23, 75,  3, 34],
                [88,  2, 77, 73,  7, 63, 67],
                [99, 65,  4, 28,  6, 16, 70, 92],
                [41, 41, 26, 56, 83, 40, 80, 70, 33],
                [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
                [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
                [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
                [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
                [63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
                [ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23],
                ]))
    

    And see what you get.

  • Custom User Avatar

    "The problem is, memo isn't reset, it keeps its value"
    Is it the solution problem? Then don't understand why.
    Or tests problem?

  • Custom User Avatar

    "Have you tried locally calling your function more than once?"
    Sure, many times, with the same or different pyramids, but one per try.

    "...distinguish between '11' + '10' and '111' + '0'?"
    Didn't think about it. Looks reasonable. The test suite is pretty small, probably need to make it bigger

  • Custom User Avatar

    Have you tried locally calling your function more than once? The problem is, memo isn't reset, it keeps its value. Also point being a concatenation of x + y, how would you distinguish between '11' + '10' and '111' + '0'?

  • Loading more items...