CareerCup

int recursive(int x, int y){
if(x == 1 || y == 1) return 1;
return recursive(x-1, y) + recursive(x, y-1);
}

as for NxN, calculate recursive(N, N)

Ok, this question is extremely easy if you look at it in the right light... For an NxN square it takes (2N - 2) steps to move from the upper left corner to bottom right corner. Of these steps, half must be right and half must be down (N - 1 in each direction). Knowing this, we can look at it as a string permutation or how many ways can you write "RRRDDD", etc. (this would be for N = 4, "RRDD" for N = 3 and so on). Now we just have to count the number of permutations for this string which in terms of N will be (2N - 2)!/((N - 1)!(N - 1)!). And there you have it...these numbers match up with Godot's post of:
2, 2
3, 6
4, 20
5, 70
6, 252
7, 924
8, 3432

The first technique that comes to my mind is to employ a depth first search until the entire tree is exlored, and count how many times the goal (ie. the right-bottom cell) is reached.

pin

N * N+1

This is a dynamic programming problem.
Use an NxN array A where A[i,j] is the number of paths into cell i,j.
Initialize
A[0,0] = 1
and iterate through the array calculating
A[i,j] = A[i-1,j] + A[i,j-1]
The number of paths into a cell is the sum of the number of paths into the cells to the left and up.

It takes 2N-1 steps to reach the destination. At each step, you have two choices, except the last step where you have only one choice to make. So, it will be 2*2*..(2n-2 times)*1 = 2^(2n-2)

But for the right most column and bottom row, there is only one choice. how to subtract it from the above result ?

Guys, this is a catalan number, mathematically there are 2n!/(n!(n+1)!) paths.
Search Catalan_numbers in Wikipedia.

No dynamic programming , no catalan. Its a simple counting problem. Answer is C( 2(n-1), n-1 )
Explanation: If we assume the initial location is [1,1], the robot has to move n-1 steps to right and n-1 down. This problem can be seen as making 2 groups of size n-1 out of 2n-2.

Mohit ur solution doesnot work, check it properly.... say for n=2, ur ans is 2 but the actual answer is 4,,,just check it out...

hi jh how is it 4 for n = 2?

C'mon, guys the ans is C(2n,n) , check it out! see the following explanation.
Lets encode the movements as below
down = 0
right = 1
now the total path lenght is 2n, in this 2n steps the robot has to take n steps down and n steps right. now our job is to to a selection of n steps form 2n..
or in our encoding we can say that we want to put n no of 1s in n no no 0s(or put n 0s in n 1s, both are same as the matrix is nxn, otherwise it wud have been different) so just select n out of 2n and thats the answer. hope it makse sense...

it needs (n-1)Down and (n-1)Right steps..

so, d ans is C(2n-2,n-1)..
try it with n=3 or so..

call it with

count(N, 1, &c);

void count(int m, int n, int *c)
{
  printf("m = %d , n = %d \n" , m, n );
  if ( m == 1 && n == N )
    (*c)++;
  else
  {
    if ( m > 1)
      count(m-1,  n, c);
    if ( n < N )
      count(m,  n+1, c);
  }
}

should be C(2n-2,n-1)


int N;

int count (int x, int y)
{
if ((x==N-1)&&(y==N-1))
return 1;
else if (x==N-1)
return count(x,y+1);
else if (y==N-1)
return count(x+1,y);
else
return (count(x+1,y)+count(x,y+1));
}

initially call count(1,1)

it can be recursively generated.
Assume the path is expressed as "RRDD", meaning that path is R->R->D->D.
The following code works.

void genePath(int i, int j, int index, char arr[], int n) {
if (index == 2*n) {
int i =0;
for (i =0; i< 2*n; i++)
printf("%c,",arr[i]);
printf("\n");
}

if (i < n) {
arr[index] = 'R';
genePath(i+1,j,index+1,arr,n);
}

if (j < n) {
arr[index] = 'D';
genePath(i,j+1,index+1,arr,n);
}
}

int main(void) {
int n = 3;
char* arr = (char*) malloc(n*(sizeof(char)));
genePath(0,0,0,arr,n);
return 0;
}

a minor correction:
if((x==(n-1))&&(y==(n-1)) return 0;
if((x==(n-1))||(y==(n-1)) return 1;
return (count(x+1,y)+count(x,y+1));

only nathan is correct. it's surprising how stupid people are... (DFS? WTF?)

Totally (N-1) steps down and (N-1) steps right. Use 1 to represent up and 0 to represent down. We need to find all the strings having 2(N-1) characters with (N-1) '1' and (N-1) '0'. A recursive solution is as following:

#include <stdio.h>
#include <malloc.h>
#define N 3

void Assign( char *start, char *current, int One, int Zero){
if(!One && !Zero){
printf("%s\n", start);
return;
}
if(One){
*current='1';
Assign(start, current+1, One-1, Zero);
}
if(Zero){
*current='0';
Assign(start, current+1, One, Zero-1);
}
}

void main(){
char *path=(char*)malloc((2*(N-1)+1)*sizeof(char));
path[2*(N-1)]='\0';
Assign(path, path, N-1, N-1);
}

Here is my code:

#define N 4

void Walk(char *out,int *used,int i, int recurlen)
{
if(recurlen==(2*N-2))
{
int k=0;
while(k<recurlen)
{
printf("%c",out[k]);
k++;
}
printf("\n");
return;
}

if(used[i]==1)
{
out[recurlen]='D';
used[i]=0;
Walk(out,used,i+N,recurlen+1);
used[i]=1;
}

if(used[i]==2)
{
out[recurlen]='R';
used[i]=0;
Walk(out,used,i+1,recurlen+1);
used[i]=2;
}

if(used[i]==3)
{
out[recurlen]='R';
used[i]=1;
Walk(out,used,i+1,recurlen+1);
used[i]=3;

out[recurlen]='D';
used[i]=2;
Walk(out,used,i+N,recurlen+1);
used[i]=3;
}

}

int main()
{

char * out = (char *)malloc((2*N-2)*sizeof(char));
int used[] = {3,3,3,1,3,3,3,1,3,3,3,1,2,2,2,0};

Walk(out,used,0,0);

return 0;
}

I am treating the NxN board as a single dimension array and have modified the indexing appropriately.

A few comments. The used array basically gives me the moves that I can make from that square i.e. R, D or both R and D.

I know I could have named the array better, permissions might have been a better name but whatever :).

if(used[i]) = 1 it means you can move Down (D) from there, if it is 2 you can move Right (R) from there. If used[i]=3, you can move both right and down from there.

Also, I have assumed that at every square you can make some move. If a square is completely off limits the code will still work with minor modifications.

This is a typical dynamic programming question.

for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(i==0 || j==0)
a[i][j]=1;
else
a[i][j]=a[i-1][j]+a[i][j-1];
}
}
The number of paths to any square is the sum of the no. of paths to the above square and no. of paths to the left square.

This code can find the number of paths to each square in the board.

yea dynamic

To calculate C(2N,N) or (maybe off by 1 C(2N-2, N-1)), if you say dynamic programming, then fine.


--
Half knowledge is dangerous. Most posters visiting this site are armed!

I think DFS may not work. It will ignore some paths which have back-edges. The total number of paths is C(2N, N).
length of every path = 2N
Given a set (1,2,3,...,2N), which represents the path (2N steps). we compute all the possible subsets that have exactly N elements and consider the numbers in the subset as the steps that go down.

i think mathematically we can say that there will be (n+1)! paths.
please check my proof.
proof:
since to reach the destination.....in any case the robot will take have to take n steps in the vertical direction to reach ..
i represent those n steps as a1,a2,a3,...
a1 a2 a3 a4 a5 a6 a7 ........an(these are all vertical steps taken at some point of time)
between these steps there can be many horizontal steps(have be to n to reach destination)
since there are n+1 spaces between thses steps....so we choose n spaces out of these n+1 and permute them...
n+1Cn * n!
Any comments?