4
\$\begingroup\$

I'm not a C programmer, just wanted to make a fast solution to the problem.

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?

Here's my code:

#include <stdio.h>
#define SIZE 21 // grid size + 1                                                                                                                             

long long int count_routes(long long int cache[SIZE][SIZE], unsigned short x, unsigned short y) {                                                            

    if (cache[x][y] != 0) {                                                                                                                                  
        return cache[x][y];                                                                                                                                  
    }                                                                                                                                                        

    long long int n = 0;                                                                                                                                     

    if (x == 0 && y == 0) {                                                                                                                                  
        n = 1;                                                                                                                                               
    }                                                                                                                                                        
    else {                                                                                                                                                   
        n = 0;                                                                                                                                               
        if (x > 0) {                                                                                                                                         
            n += count_routes(cache, x-1, y);                                                                                                                
        }                                                                                                                                                    
        if (y > 0) {                                                                                                                                         
            n += count_routes(cache, x, y-1);                                                                                                                
        }                                                                                                                                                    
    }                                                                                                                                                        

    cache[x][y] = n;                                                                                                                                         

    return n;                                                                                                                                                
}                                                                                                                                                            

int main(void) {                                                                                                                                             

    long long int cache[SIZE][SIZE];                                                                                                                         

    for (int i = 0; i < SIZE; i++) {                                                                                                                         
        for (int j = 0; j < SIZE; j++) {                                                                                                                     
            cache[i][j] = 0;                                                                                                                                 
        }                                                                                                                                                    
    }                                                                                                                                                        

    printf("%lld\n", count_routes(cache, SIZE-1, SIZE-1));                                                                                                   

    return 0;                                                                                                                                                
} 

Please share your thoughts about what could be improved in it.

\$\endgroup\$
  • 2
    \$\begingroup\$ Those are binomial coefficients right? So \$\frac{n!}{(n-k)!k!}\$ where \$n = 40\$ and \$k = 20\$ should do it? \$\endgroup\$ – Farhad Dec 31 '14 at 10:31
4
\$\begingroup\$

I do not know whether my suggestion makes code faster, but it sure does make it shorter and probably equally fast. It calculates the possibilities dynamically, using the observation that number of ways to get to a square is the sum of numbers of ways to get to the top and the left square, as does yours, but it does not use recursion, so it's perhaps easier to understand or code.

#include <cstdio>

unsigned long long g[21][21];

int main() { 
    for (int i = 0; i < 21; ++i) {
        g[i][0] = 1;
        g[0][i] = 1;
    }
    for (int i = 1; i < 21; ++i) {
        for (int j = 1; j < 21; ++j) {
            g[i][j] = g[i-1][j] + g[i][j-1];
        }
    }

    printf("%lld\n", g[20][20]);
    return 0;
}
\$\endgroup\$
3
\$\begingroup\$

Taking the amount of points in the grid as the input size(n*m), using recursion forces you to make it O(n*m) in space and time.

If we want to go from (0,0) to (20,20) then we already know that we have to go right 20 times and down 20 times. So we can rephrase the question from "How many different ways can you go to (20,20)?" to "In how many different ways can you go 20 times right and 20 times down?". The second question is now purely a basic math permutations calculation. The answer to it is $${40\choose 20} = \frac{40!}{(40-20)!20!}.$$

In C code

#include <stdio.h>

int main() { 
    int res = 1;
    for (int i = 0; i < 20; ++i) {
       res = res * (40-i) / (i+1)
    }

    printf("%lld\n", res);
    return 0;
}

This requires 20 multiplications and 20 divisions. So it is O(n+m) in time, but constant in space.

Note that doing res *= (40-i)/(i+1) will not work. The quotient (40-i)/(i+1) is not an integer for all i. A counterexample is i=1 since 39%2 = 1.

The way I wrote it, the multiplication res (40 -i) is done first, which ensures the division will yield an integer.

To see this, start with n/1 - obviously an integer as 1 divides any number. The next term is n.(n-1)/1.2; if n is not even, then (n-1) must be. Similarly, n*(n-1)...(n-p) must contain a multiple of p+1 somewhere in the product. In this way you can continue and there will always be a factor in the numerator for the 'new' factor in the denomiator to divide out.

\$\endgroup\$
  • \$\begingroup\$ You are right. This is a whole in my answer. For i=1 it already fails. I'll adjust my answer \$\endgroup\$ – bbnkttp Apr 3 '18 at 16:33
  • \$\begingroup\$ I don't think it was wrong. And I think I can sketch a proof that it's right in the general case (n choose k). We start with n/1 - obviously an integer as 1 divides any number. The next term is n.(n-1) / 1.2; if n is not even, then (n-1) must be. Similarly, n.(n-1)...(n-p) must contain a multiple of p+1 somewhere in the product. The proof needs to be more rigorous to show that repeated factors are accounted for (e.g. when we reach 4 in the denominator, we've already cancelled a 2 - but we have accumulated a multiple of 4 and a different multiple of 2 in the numerator). \$\endgroup\$ – Toby Speight Apr 6 '18 at 7:49
  • \$\begingroup\$ It is important to multiply before dividing, though - so point out that you can't replace res = res * (40-i) / (i+1) with res *= (40-i) / (i+1); it would have to be res *= 40-i; res /= i+1;. And this (original) solution is actually better than the new (edited) one, because it is less likely to overflow the integer type. This relevant link might be worth a look. \$\endgroup\$ – Toby Speight Apr 6 '18 at 7:52
  • \$\begingroup\$ You are right again and your sketch makes sense. Should I adjust my answer for the 2nd time? \$\endgroup\$ – bbnkttp Apr 6 '18 at 8:04
  • \$\begingroup\$ Yes, I think so - I suggest you remove the "EDIT" section, and then incorporate something to explain what I wrote in comments (I'll delete the comments once they are no longer needed). Sorry to raise a false alarm! \$\endgroup\$ – Toby Speight Apr 6 '18 at 8:12

protected by Jamal Mar 30 '18 at 1:35

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.