5
\$\begingroup\$

Working on below cross river problem, and post my code in Python 2.7 using dynamic programming. Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style advice is appreciated.

More specifically, my idea is,

  1. build a DP array to represent if we can reach a location by a certain speed;
  2. when checking whether we are reach a certain location by a certain speed, we check if we can reach (1) location - speed with speed, (2) location - speed with speed + 1, (3) location - speed with speed - 1, if any (1), (2) or (3) is true, it means we can reach a certain location with such specific speed;
  3. For the last location, if could be reached by any speed, return True

Problem,

Given a string representation of the rocks in the river e.g. "***** * * * * * *", determine whether the river is crossable. Where,

* = landable
  = cannot land there

Suppose Initial location: 0 and Initial speed: 0

in each step:
    1. choose a new speed from {speed, speed + 1, speed - 1} (but not negative)
    2. move speed spaces: loc += speed
    3. if I land on water, I fail
    4. if I land past end of river, I win
    5. otherwise, keep going

For example, below river could be crossed by the first method. So, it should return True.

X~~~~~~~~~~~~~~~~~~~~~_______($)
*****  *   * * *  *  *
011 2  3   4   4  3  3   4 (crossed)
01 2 2 (failed)
01111 2 (failed)

Source code in Python 2.7,

from collections import defaultdict
def can_cross_river(river):
    # key: (location, speed) tuple,
    # value: True or False for whether reachable at a specific location
    # with a specific speed
    dp = defaultdict(lambda : False)
    dp[(0,0)] = True
    for i in range(1, len(river)):
        if river[i] != '*':
            continue
        for speed in range(0,i+1):
            if dp[(i-speed, speed)] or dp[(i-speed, speed-1)] or dp[(i-speed, speed+1)]:
                dp[(i, speed)]= True
                if i == len(river) - 1: # reach end of river at any speed is fine
                    return True
    return False

if __name__ == "__main__":
    river = "*****  *   * * *  *  *" # should return True
    #river = "* *" # should return False
    print can_cross_river(river)
\$\endgroup\$
3
\$\begingroup\$

You have a small bug. Consider a river like ******.. such that the last spot is not landable. You can still cross the river by jumping beyond the end of the river from the last landable stone, but your code thinks that you cannot.

The solution to this is to do a top down DP. Define dp(position, speed) to be true if you can cross the river starting from position with given speed. You want to find dp(0,0), which you can do easily with memoised recursion.

\$\endgroup\$
  • \$\begingroup\$ Thanks Raziman, nice catch! Is there a solution which is top down DP without recursive (more iterative/loop way)? I think recursive is a bit slow. \$\endgroup\$ – Lin Ma Feb 13 '17 at 0:09
  • \$\begingroup\$ BTW, vote up for the nice bug catch. \$\endgroup\$ – Lin Ma Feb 13 '17 at 0:09
  • \$\begingroup\$ Hi Raziman, have a new idea still use bottom up DP which is faster than top down, this new solution I post here which can fix the issue you pointed out, your advice is highly appreciated. codereview.stackexchange.com/questions/155200/… \$\endgroup\$ – Lin Ma Feb 13 '17 at 0:28
  • \$\begingroup\$ BTW, for the new solution, I also optimize code by using set other than dict, which should be faster. Mark your reply as answer and we can continue to discuss on the new thread. \$\endgroup\$ – Lin Ma Feb 13 '17 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.