Python - DP top-down with memoization


  • 0
    A
    class Solution(object):
        def canCross(self, stoneL):
            """
            :type stones: List[int]
            :rtype: bool
            """
            stones = set(stoneL)    # change to set 
            def dp(i, k, mem):
                if (i, k) in mem:
                    return mem[(i, k)]
                if i == stoneL[-1]:
                    mem[(i, k)] = True
                    return True 
                if i == 0:
                    if 1 not in stones:
                        return False
                    else:
                        mem[(0, 1)] = dp(1, 1, mem)
                        return mem[(0, 1)]
                if k == 1:
                    if (i+2) not in stones and (i+1) not in stones:
                        mem[(i, k)] = False
                        return False
                    elif (i+2) not in stones:
                        mem[(i, k)] = dp(i+1, 1, mem)
                        return mem[(i, k)]
                    elif (i+1) not in stones:
                        mem[(i, k)] = dp(i+2, 2, mem)
                        return mem[(i, k)]
                    else:
                        mem[(i, k)] = dp(i+1, 1, mem) or dp(i+2, 2, mem)
                        return mem[(i, k)]
                else:
                    if (i+k+1) not in stones and (i+k) not in stones and (i+k-1) not in stones:
                        mem[(i, k)] = False
                        return False
                    elif (i+k+1) not in stones and (i+k) not in stones:
                        mem[(i, k)] = dp(i+k-1, k-1, mem)
                        return mem[(i, k)]
                    elif (i+k+1) not in stones and (i+k-1) not in stones:
                        mem[(i, k)] = dp(i+k, k, mem)
                        return mem[(i, k)]
                    elif (i+k) not in stones and (i+k-1) not in stones:
                        mem[(i, k)] = dp(i+k+1, k+1, mem)
                        return mem[(i, k)]
                    elif (i+k+1) not in stones:
                        mem[(i, k)] = dp(i+k, k, mem) or dp(i+k-1, k-1, mem)
                        return mem[(i, k)]
                    elif (i+k) not in stones:
                        mem[(i, k)] = dp(i+k+1, k+1, mem) or dp(i+k-1, k-1, mem)
                        return mem[(i, k)]
                    elif (i+k-1) not in stones:
                        mem[(i, k)] = dp(i+k+1, k+1, mem) or dp(i+k, k, mem)
                        return mem[(i, k)]
                    else:
                        mem[(i, k)] = dp(i+k+1, k+1, mem) or dp(i+k, k, mem) or dp(i+k-1, k-1, mem)
                        return mem[(i, k)]
            mem = {}
            return dp(0, 1, mem)
    

  • 0

    Cool, but isn't a bit too verbose for Python? Here's essentially the same thing:

    if stones[1] != 1:
        return False
    stones_set = set(stones)
    known = {}
    def canCross(s1, s2):
        if (s1, s2) not in known:
            if s2 == stones[-1]:
                known[(s1, s2)] = True
            else:
                d = s2 - s1
                known[(s1, s2)] = any(canCross(s2, s3) for s3
                                      in xrange(s2 + d - 1 if d > 1 else s2 + d, s2 + d + 2)
                                      if s3 in stones_set)
        return known[(s1, s2)]
    return canCross(0, 1)
    

    Accepted, but fails on my PC: maximum recursion depth exceeded. But then again, so does your solution. Guess this approach doesn't work well with Python.


  • 0
    A

    @SergeyTachenov It is. I was rushing it. Do u mind pasting the test-case where it overflew? Thx a lot!


  • 0

    Just in case you didn't know, known[(s1, s2)] is the same as known[s1, s2].


  • 0

    @AlgoGuruZ It's a bit too long to paste, but it just goes 0, 1, 2... 999. Calling sys.setrecursionlimit(5000) fixed it, though.

    @StefanPochmann I always confuse when parentheses are needed and when not. Just like I always use parentheses in C++ and Java around >> << and & | ^. But in this case it should've been obvious. I don't feel bad about it, though, as it makes the whole thing more explicit. I'm more worried about that ugly s2 + d - 1 if d > 1 else s2 + d part and the if stones[1] != 1 case, but I can't figure out how to get rid of them in an elegant way.


  • 0

    I think I got it now:

    stones_set = set(stones)
    known = {}
    def canCross(s1, s2):
        if (s1, s2) not in known:
            if s2 == stones[-1]:
                known[s1, s2] = True
            else:
                d2 = s2 - s1
                known[s1, s2] = any(canCross(s2, s2 + d3) for d3
                                    in xrange(max(d2 - 1, 1), d2 + 2)
                                    if s2 + d3 in stones_set)
        return known[s1, s2]
    return canCross(0, 0)
    

    No more that ugly special case, and max certainly looks better than that ugly if.

    Fun fact: using xrange(d2 + 1, max(d2 - 2, 0), -1) instead improves the run time to about 70 ms (from about 100). Guess that's because it uses long jumps when possible, therefore reaching the target earlier.


  • 0

    @SergeyTachenov Nice improvements. You could also directly return True and then you don't need the else and can unindent its contents.

    I disagree that known[(s1, s2)] is more "explicit" than known[s1, s2]. That makes it sound like the latter has implicit parentheses. To quote the Python Wiki, "it is the comma, not the parentheses, that define the tuple" (though it's talking about other cases). Parentheses are not essential for tuples (except for the empty tuple ()), they're just sometimes needed for grouping. Just like they're sometimes needed for grouping other things, e.g., (i + j) * n. Would you also use known[(i + j)] instead of known[i + j] and call the former more explicit?

    Edit: The docs also say "Note that tuples are not formed by the parentheses, but rather by use of the comma operator. The exception is the empty tuple".


  • 0

    @StefanPochmann You mean like this?

    if s2 == stones[-1]:
        return True
    if (s1, s2) not in known:
        d2 = s2 - s1
        known[s1, s2] = any(canCross(s2, s2 + d3) for d3
                            in xrange(d2 + 1, max(d2 - 2, 0), -1)
                            if s2 + d3 in stones_set)
    

    I remember thinking about this, but I don't remember why I didn't it. Definitely looks better.

    Yeah, I have read that stuff about tuples. But I still find it confusing and because of that often add parentheses needlessly without giving it a second thought.


  • 0

    @SergeyTachenov Yeah, like that or with the if s2 == stones[-1]: return True still inside the other if. Not sure what's better.


  • 0

    @StefanPochmann I don't see a point in putting it in the other if. If we're going to return True without memoizing it anyway, why bother checking that the answer is not memoized yet?


  • 0

    @SergeyTachenov It would be faster. Outside, that check will be done at every single call during the search, even on "repeated calls". Inside, it would be done less often.


  • 0

    @StefanPochmann Oh, I hadn't thought of that. Tried to submitting, it doesn't seem there's any difference. Both variants run in about 190 ms (some tests were added, so it's slower now). Interestingly, the variant without the extra return is slightly faster: 160-170 ms. Maybe within margin of error, although I submitted three times.


  • 0

    @SergeyTachenov Yeah, I wouldn't expect it to be noticeable in the OJ. I now tested locally, testing each version three times 100 times on range(1999) + [9999] (that's a case where the inside-vs-outside should play a role, as there are relatively many repeated calls and we must do the full search because there's no way the frog can cross):

    from timeit import timeit
    for _ in range(3):
        print timeit(lambda: Solution().canCross(range(1999) + [9999]), number=100)
    

    With if s2 == stones[-1]: return True inside the other if (times in seconds):
    18.5091165364
    18.4510093963
    18.6512655162

    Outside the other if:
    18.8030853982
    18.9244283874
    18.9133609044

    With known[s1, s2] = True and else:
    18.483076973
    18.6257707035
    18.4797243375

    The "outside"-version looks consistently slower, as expected. The other two look about equally fast.


  • 0

    @StefanPochmann Wow, you must have some impressive hardware. Or use some optimization settings. Here are my results:

    Inside:
    32.6581707025
    32.9920321176
    33.2971709571

    Outside:
    33.6750903148
    34.3595633396
    34.756462441

    If-else:
    32.8538324421
    33.6187497321
    33.2839616224

    And here's a bonus surprise. Bottom-up:
    12.0656952994
    12.1085436985
    12.0477046521

    I guess that bottom-up is more efficient in general, but is slower in the OJ because most OJ test cases are positive, where top-down approach works better because of its DFS nature.


  • 0

    @SergeyTachenov Well I have an i7-6700, that's fairly fast, yes :-). What's the bottom-up code you tested?


  • 0

    @StefanPochmann The second solution from my post.


  • 0

    I have a question. Where is the redundancy coming from? Or someone can give me an example of this redundancy.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.