CODEWITHSUNDEEP
algorithm
Anathema.Imbued
Anathema.Imbued

Reputation: 3491

Dead or Alive turtle jumping Algorithm

River is divided into n segments breadth wise, with either stone or water [ 1,0,0,1,1,0,1,1,0,1... ].A turtle is present on one side of the bank and he can make a move with speed of x, x speed means he can cross x segments of the river at a single time. After making a cross with x speed, he can acquire, either of these three speeds, x,x+1,x-1. He can move in both directions.

Now 1 represents stone and 0 represents water. If the turtle jumps into water he dies, but if he makes a jump on stone, then he can acquire new speed according to the given rule.

Given no. of segments (n), distribution of segment(array[n]), and the initial speed(x). Find is there any possibility of the turtle making it to the other side of the bank ?

I've solved this problem recursively, but not able to do using non-recursive method.

Turtle on one side||1,0,1,1,0,0,0,1,1,0,1,....||Other side of the river

Upvotes: 3

Views: 319

Answers (1)

tobias_k
tobias_k

Reputation: 82899

Basically it's a simple search problem, where your states are tuples of the current position of the turtle and it's speed. It can be implemented without recursion using a stack (depth first) or a queue (breadth first search). Here's an implementation using a queue, i.e., breadth-first, in Python:

from collections import deque

def cross_river(river, position=0, speed=1):
    queue = deque([(position, speed, [])])
    visited = set()
    while queue:
        position, speed, path = queue.popleft()

        # if  last stone of river, return sequence of jumps to get there
        if position == len(river) - 1:
            return path

        # check whether we've been here before
        if (position, abs(speed)) in visited:
            continue
        visited.add((position, abs(speed)))

        # for all possible jumps, add the new state to the queue
        for i in [-1, 0, +1]:    # change in speed
            for k in [-1, +1]:   # change in direction
                new_spd = (speed + i) * k
                new_pos = position + new_spd
                if 0 <= new_pos < len(river) and river[new_pos] == 1:
                    queue.append((new_pos, new_spd, path + [new_spd]))

print cross_river([1,0,1,1,0,0,0,1,1,0,1])  # Result: [2, -2, 3, 4, 3]

(In fact, this algorithm is a bit stricter than what's described in your question, as the turtle has to to land exactly on the last stone, instead of anywhere on the other side, but this should be easy to change.)

Upvotes: 3

Related Questions