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+k1) 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+k1, k1, mem)
return mem[(i, k)]
elif (i+k+1) not in stones and (i+k1) not in stones:
mem[(i, k)] = dp(i+k, k, mem)
return mem[(i, k)]
elif (i+k) not in stones and (i+k1) 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+k1, k1, mem)
return mem[(i, k)]
elif (i+k) not in stones:
mem[(i, k)] = dp(i+k+1, k+1, mem) or dp(i+k1, k1, mem)
return mem[(i, k)]
elif (i+k1) 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+k1, k1, mem)
return mem[(i, k)]
mem = {}
return dp(0, 1, mem)
Python  DP topdown with memoization


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.

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

@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 uglys2 + d  1 if d > 1 else s2 + d
part and theif stones[1] != 1
case, but I can't figure out how to get rid of them in an elegant way.

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 uglyif
.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.

@SergeyTachenov Nice improvements. You could also directly
return True
and then you don't need theelse
and can unindent its contents.I disagree that
known[(s1, s2)]
is more "explicit" thanknown[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 useknown[(i + j)]
instead ofknown[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".

@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.

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

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

@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.

@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: 160170 ms. Maybe within margin of error, although I submitted three times.

@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 insidevsoutside 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 otherif
(times in seconds):
18.5091165364
18.4510093963
18.6512655162Outside the other
if
:
18.8030853982
18.9244283874
18.9133609044With
known[s1, s2] = True
andelse
:
18.483076973
18.6257707035
18.4797243375The "outside"version looks consistently slower, as expected. The other two look about equally fast.

@StefanPochmann Wow, you must have some impressive hardware. Or use some optimization settings. Here are my results:
Inside:
32.6581707025
32.9920321176
33.2971709571Outside:
33.6750903148
34.3595633396
34.756462441Ifelse:
32.8538324421
33.6187497321
33.2839616224And here's a bonus surprise. Bottomup:
12.0656952994
12.1085436985
12.0477046521I guess that bottomup is more efficient in general, but is slower in the OJ because most OJ test cases are positive, where topdown approach works better because of its DFS nature.

@SergeyTachenov Well I have an i76700, that's fairly fast, yes :). What's the bottomup code you tested?
