Pages

Search This Blog

November 27, 2012

frog jumps :)


There is a river and there are n number of steps between two banks of the river to cross the river.
A frog wants to cross the river with the condition that he can jump max one step. Find the number of ways he can cross the river?
For e.g. if there are 3 steps in between, frog can go from paths: _123_, _2_, _13_ so there are 3 different ways frog can cross the river (in the example _ is two ends of the river)


Source: http://www.geeksforgeeks.org/forum/topic/adobe-interview-question-for-software-engineerdeveloper-about-algorithms-31

def frogJumps(n):
    """
    Takes n, checks if it is base case and returns
    base case outputs.
    Else call frogJumps with n-1and n-2.
    Base Cases: 1&2 rocks
    returns a number and list of nodes hopped by frog for n
    """
    if n ==1:
        # one rock no jump
        return (0, [[1]])
    if n == 2:
        # two rocks, one jump
        return (1,[[1, 2]])
    # recurse
    # previous stone !
    jumpsX, rocksX = frogJumps(n-1)
    # one before previous
    jumpsY,rocksY = frogJumps(n-2)
    # jump from previous stones to current stone
    for x in rocksX:
        x.append(n)
    for xinrocksY:
        x.append(n)
    rocks = rocksX+rocksY
    jumps = len(rocks)
    return (jumps, rocks)
jumps, rocks = frogJumps(6)
print jumps
print rocks

No comments:

Post a Comment