CareerCup

void PrintFrogPath(int a[], int length, int aCount,  int path[], int bCount)
{
	if(aCount == length && path[bCount-1] == a[aCount-1])
	{
		for(int i = 0 ; i < bCount ; i++)
			cout<<path[i]<<" ";
		cout<<endl;
		return;
	}
	else if(aCount < length)
	{
		for(int i = 1; i<=2 ; i++)
		{
			path[bCount] = a[aCount];
			PrintFrogPath(a, length, aCount+i, path, bCount+1);
		}
	}
}
void main()
{
	int c[] = {1,2,3,4};
	int d[] = {0,0,0,0};
	PrintFrogPath(c,4,0,d,0);
}

int HasConsecutiveZeroes(n)
{

int flag = 0;

while(n)
{
int z = n & 0x1;

if(z == 0)
if(flag)
return 1;
else
flag = 1;
n = n >> 1;
}
return 0;

}

print(a, n , p)
{

int i = 1, num = 0 ;

int pos, z;
int j = 1;
while( j < p)
{
if(HasConsecutiveZeroes(j))
{
j++;
continue;
}

z = j;

path[num] = a[0];
num++;

while(z)
{
if(z & 0x01)
{
path[num] = a[i + pos];
pos++;
num++;
}
z = z >> 1;
}
path[num] = a[n-1];
for(int q = 0 q < num ; q++)
cout<<path[q];
num = 0;
j++;
}

}

void printPaths(int a[], int n)
{

int p = n - 2;

p = pow(2, p); // for generating all possible combinations...

print(a, n , p - 1);

}
int main()
{

int a[] = { 0 , 1, 2 ,3, 4 };

int n = 5;

printPaths(a, n);

}

Frog can take a leap of 1 or 2 at any time therefore if number of rock is N then total number of paths will be Nth Fibonacci number. Below is the code to print all the paths:

void printFrogLeap (int* pArray, int num, int count)
{
	if(count > num)
	{
		return;
	}
	if(count == num)
	{
		int i;
		if(pArray[count-1] == 1) /*path is complete or not*/
		{
			for (i=0; i < num; i++)
			{
				if (pArray[i] == 1)
				{
					printf ("[%d]", i+1);
				}
			}
			printf ("\n");
		}
		return;
	}
	pArray [count] = 1;
	printFrogLeap (pArray, num, count+1);
	if(count+1 < num)
	{
		pArray [count+1] = 0;/*exclude this entry from path, since its used*/
	}
	printFrogLeap (pArray, num, count+2);
	if(count+2 < num)
	{
		pArray [count+2] = 0;/*exclude this entry from path, since its used*/
	}	
}


int main ()
{
	int *array, num;
	printf ("Enter num of rocks: ");
	scanf ("%d", &num);
	array = (int*)malloc (sizeof(int)*num);
	memset (array,0x00,num);
	printf ("Total paths: \n");
	printFrogLeap (array, num, 0);
	free (array);
	return 0;
}

void print_path(vector<int> path) {
for(int i = 0; i < path.size(); i++) {
printf("%d,", path[i]);
}
printf("\n");
}

void paths(int rocks_left, int total_rocks, vector<int> path) {
if(rocks_left == 0) {
print_path(path);
return;
}
path.push_back(total_rocks - rocks_left + 1);
paths(rocks_left - 1, total_rocks, path);
if(rocks_left > 2) paths(rocks_left - 2, total_rocks, path);
}

int main(int argc, char **argv) {
int rocks = 5;
vector<int> vec;
paths(5,5,vec);
return 0;
}

public static void frogLeap(int N) {
        frogLeap(N, N, new StringBuilder());
    }

    public static void frogLeap(int N, int M, StringBuilder sb) {
        if (N == 0) {
            System.out.println(sb.toString());
            return;
        }
        if (N == 1) {
            System.out.println(sb.toString() + M);
            return;
        }
        final int len = sb.length();
        sb.append("" + (M - (N - 1)));
        frogLeap(N - 1, M, sb);
        sb.setLength(len);
        if (N != M) {
            sb.append("" + (M - (N - 2)));
            frogLeap(N - 2, M, sb);
            sb.setLength(len);
        }
    }

import java.util.*;

public class FrogAcrossRiver {
public static void jump(int n){
jump(0, n, new Stack<Integer>());
}

private static void jump(int from, int dest, Stack<Integer> route){
if(from == dest){
p(route);
return;
}
route.push(from + 1);
jump(from + 1, dest, route);
route.pop();
if(from != 0 && from <= dest - 2){
route.push(from + 2);
jump(from + 2, dest, route);
route.pop();
}
}

private static void p(Stack<Integer> route){
for (int i = 0; i < route.size() - 1; i++){
System.out.print(route.get(i)+ ", ");
}
System.out.print(route.peek() + "\n");
}

public static void main(String[] args){
jump(7);
}
}

void printVector(vector<char>& array)
{
for(int i=0; i<array.size(); i++)
{
cout << array[i] + '0' ;
}
cout << endl;
}

void leapFrog(int i, int n, vector<char>& array)
{
if(i == n)
{
array.push_back(i - '0');
printVector(array);
array.pop_back();
return;
}
else if(i == n-1)
{
array.push_back(i - '0');
leapFrog(i+1, n, array);
array.pop_back();
}
else
{
array.push_back(i - '0');
leapFrog(i+1, n, array);
leapFrog(i+2, n, array);
array.pop_back();
}
}

{{
//Jeff
#include <iostream>
#include <string>
#include <sstream>
#define SIZE 6


using namespace std;



int stones[]={1,2,3,4,5,6};
void hopAcross(int location,string path,bool jumped);

int main(int argc,char** argv)
{
ostringstream path;
path<<stones[0];
hopAcross(1,path.str(),0);

}
void hopAcross(int location,string path,bool jumped)
{
if(location==SIZE)
{
cout<<path<<endl;
return;
}
//produce jump tree
if(jumped==false && location+1<SIZE)
{
hopAcross(location+1,path,true);
}
ostringstream temp;
temp<<path<<"-->"<<stones[location];
hopAcross(++location,temp.str(),false);
}
}}

string int2string(int data){
       ostringstream buffer;
       buffer<<data;
       return buffer.str();
       }
void printFrogPath(int rl,int tr, string s){
     if(!rl)
     {
            cout<<s<<endl;
            return;
     }
     s += int2string(tr-rl+1);
     printFrogPath(rl-1,tr,s);
     if(rl>2)
     printFrogPath(rl-2,tr,s);
}       

printFrogPath(4,4,"");

#include<iostream>
#include<string>
using namespace std;

void paths(int);
void paths(int,int,bool,string);

int main()
{
	int num_stones=0;
	cout<<"Number of stones:";
	cin>>num_stones;
	paths(num_stones);
	return 0;
}

void paths(int num)
{
	string path="1";
	paths(num,1,false,path);
}

void paths(int max,int curr,bool skipped,string path)
{
	if(curr==max)
	{
		cout<<path<<endl;
	}
	else
	{
		paths(max,curr+1,false,path+','+(char)('0'+curr+1));
		if(!skipped && curr+1<max)
		{
			paths(max,curr+2,true,path+','+(char)('0'+curr+2));
		}
	}
}

Sorry posted previous solution before testing...

#include<iostream>
#include<string>
using namespace std;

void paths(int,int,string);

int main()
{
	int num_stones=0;
	cout<<"Number of stones:";
	cin>>num_stones;
	paths(num_stones,1,"1");
	return 0;
}

void paths(int max,int curr,string path)
{
	if(curr==max)
	{
		cout<<path<<endl;
	}
	else
	{
		paths(max,curr+1,path+','+(char)('0'+curr+1));
		if(curr+1<max)
		{
			paths(max,curr+2,path+','+(char)('0'+curr+2));
		}
	}
}

Following is the code to generate the frog path generically(means for ne number of stone) and recursively...I havnt run the code in the complier(it may not be complete syntax compliant)...just wrote and think that it will work fine..Do tell me if there are ne issues..


Following is the concept...
Take the array as 1 1 1 1 1 as for five stones each initially represents '1'...here 1 represents that frog doesnt skip that particular stone..

and if it is 1 1 0 1 1 ..then it skips the 3rd one..
Take the following array to pass into array

a[]=[1, 1 , 1 , 1 ,1] for five stones
so call the following function-- printPathsForFrog(a,1)

printPathsForFrog(int a[],int counter)
{
for(int i=0;i<a.length;i++)
{
if(a[i]==1)
{
printf(i+1);
}
}
for(int j=counter;j<a.length-1;j++)
{
if(a[j-1]==1)
{
a[j]=0;
printPathsForFrog(a,counter++);
a[j]=1;
}
else
{
j++;
}
}

#include<stdio.h>
#define max 20
int n;
void perm(int *p,int index,int i)
{int j;
if(i==n)
{ p[index]=i;
for(j=1;j<=index;j++)
printf("%d ",p[j]);
printf("\n");
}
else
{ p[index]=i;
if(i<n-1)
perm(p,index+1,i+2);
if(i<n)
perm(p,index+1,i+1);
}
}

main()
{
int p[max];
printf("\n Enter no of Rocks :");
scanf("%d",&n);
printf("\n For %d to %d rocks possible paths:\n",1,n);
perm(p,1,1);
}

#include<stdio.h>
#define max 20
int n;
void perm(int *p,int index,int i)
{int j;
if(i==n)
{ p[index]=i;
for(j=1;j<=index;j++)
printf("%d ",p[j]);
printf("\n");
}
else
{ p[index]=i;
if(i<n-1)
perm(p,index+1,i+2);
if(i<n)
perm(p,index+1,i+1);
}
}

main()
{
int p[max];
printf("\n Enter no of Rocks :");
scanf("%d",&n);
printf("\n For %d to %d rocks possible paths:\n",1,n);
perm(p,1,1);
}

Apologies if CODE/Logic was presented already. Thanks

package algorithms;

import java.util.ArrayList;
import java.util.List;

import javax.print.PrintService;

public class FrogRiverCrossing {
	
	public static void main(String[] args) {
		
		int n=5;
		
		List<String> finalList=printSteps(n);
		
		for(int i=0;i<finalList.size();i++){
			System.out.println(finalList.get(i));
		}
	}
	
public static List<String> printSteps(int n){
	
	if(n==1){
		return new ArrayList<String>(){{add("1");}};
	}
	if(n==2){
		return new ArrayList<String>(){{add("1-2");}};
	}
	
	List<String> listMinusOne=printSteps(n-1);
	List<String> listMinusTwo=printSteps(n-2);
	List<String> nList=new ArrayList<String>();
	
	for(int i=0;i<listMinusOne.size();i++){
		nList.add(listMinusOne.get(i)+"-"+n);
	}
	for(int i=0;i<listMinusTwo.size();i++){
		nList.add(listMinusTwo.get(i)+"-"+n);
	}
	
	return nList;
}

}