Frog puzzle to cross the river

Puzzle:

A frog wants to cross a river that is 11 feet across.

There are 10 stones in a line leading across the river, separated by 1 foot. He can either jump to the next stone or jump over a stone, and if he jumps over a stone he must land on the next one. The furthest he can jump is 2 feet. Also, he always moves forward (toward the other side of the river). In how many different ways can he cross the river?

For example, one way to cross would be 1,2,2,1,1,2,1  with representing the frog moving 1 foot forward to the next stone, and representing the frog jumping over one stone, moving 2 feet forward.

The total distance jumped must be 11 feet; that is, if the frog is at 10 feet, the frog can’t jump by 2 feet.

Hint: What are the possible conditions before getting to the stone?

Bonus: Try to come up with a recursive routine to calculate this value for  stones.

Solution:

Correct answer: 144

To get to (n+2)th stone, he could either come from (n+1)th  stone or nth  stone. For instance, the frog can either get to 5th  stone from 4th  stone or from the  3rd stone.

Let’s examine what this means with a few smaller examples. If there is one stone, then the frog can either jump on it, or jump over it:

Option 1 Stone
1 On
2 Over

If there are two stones, then the following options are available:

Option 1 Stone 2 Stone
1 On On
2 On Over
3 Over On

There are only 3 options, because the frog cannot jump over two stones straight to the other side. At most his jumps take him 2 feet forward.

If there are three stones, then the following options are available:

Option 1 Stone 2 Stone 3 Stone
1 On On On
2 On On Over
3 On Over On
4 Over On On
5 Over On Over

There are 5 options.

This is actually enough to start seeing a pattern. The number of ways to get to the 3 stone is a3 = a2+a1  or 5 = 3 +2 . If you continue with 4, 5, 6, etc. stones, you’ll find that this pattern continues. So, the number of ways to get to nth   stone is an = an-1+ an-2 or the famous Fibonacci numbers.

With this formula we can predict the 11 stone as the 11 term of the Fibonacci sequence,

 

Simple algorithm for fibonacci series:

def fibonacci(n):
        if n < 0:
                raise ValueError("invalid index!")
        if n==0:
                return 0
        if n==1:
                return 1
        return fibonacci(n-1) + fibonacci(n-2)
Advertisements

What is the difference between a++ and ++a in coding?

I hope you are quite familiar with the terms PRE-INCREMENT and POST-INCREMENT.

What is the term pre and post ???

It is just similar to the postpaid sim cards and prepaid sim cards.

In postpaid sim we will do all the actions(calls , texting , data consuming and all other actions) and finally we will pay the bill .

Whereas in prepaid, first we will pay the bill and then we perform our desire action.

This same logic is applied in this pre-increment and post-increment.

Pre-Increment is similar to prepaid sim and post-increment is similar to postpaid sim.

class Demo{

public static void main(String[] args){

int a=10; // a is assigned an value

int b = ++a; //b value is 11 as it is pre-incremented (Now a =11 and b=11)

int c = a++; // c value is also 11 and a value is 12

System.out.prinltn(“a=”+a+ “b=” +b+ “c=” +c);

}

}

Output

a=12 b=11 c=11

Both,

++a and a++ performs same operation when it is not assigned to any variable.

But when it is assigned to any value it shows it’s nature 🙂