3
\$\begingroup\$

I'm working on the cross river problem (previous post here). 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 set 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, (1) if it is not land, we will check if it could be reached by any speed, return True, (2) if it is not land, we will check if we can reach end position + 1 with any speed.

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)

def can_cross_river(river):
    # a set of tuple (position, speed), means we can reach
    # a specific position by a specific speed
    dp = set()
    dp.add((0,0))
    for i,v in enumerate(river):
        if i == 0 or v != '*':
            continue
        for speed in range(0,i+1):
            if (i-speed, speed) in dp or (i-speed, speed-1) in dp or (i-speed, speed+1) in dp:
                dp.add((i, speed))
                if i == len(river) - 1:
                    return True
    if river[-1] != '*':
        for speed in range(0,len(river)+1):
            if (len(river)-speed, speed) in dp or (len(river)-speed, speed-1) in dp or (len(river)-speed, speed+1) in dp:
                return True
    return False

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

You still have the remnant of the same bug.

Consider the river **.*..*...*....** The last slot exists but is not reachable. Yet you can jump from the penultimate slot to cross the river.

Or consider **.*..*...*....*. The slot just past the end is not reachable but something further to its right is.

This can be dealt with by modifying your code thus:

def can_cross_river(river):
    dp = set()
    dp.add((0,0))
    for i,v in enumerate(river):
        if v != '*':
            continue
        for speed in range(0,i+1):
            if (i-speed, speed) in dp or (i-speed, speed-1) in dp or (i-speed, speed+1) in dp:
                dp.add((i, speed))
                if i+speed+1 >= len(river):
                    return True
    return False
\$\endgroup\$
  • \$\begingroup\$ Nice catch Raziman and smart code, vote up. For ******.., it should return False? \$\endgroup\$ – Lin Ma Feb 14 '17 at 0:20
  • 1
    \$\begingroup\$ Should still be true, right? \$\endgroup\$ – Raziman T V Feb 14 '17 at 6:57
  • \$\begingroup\$ You are right Raziman, figured out i+speed+1 >= len(river) is a nice idea. Mark your reply as answer. \$\endgroup\$ – Lin Ma Feb 15 '17 at 9:08

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.