Project Euler #15 — count possible lattice paths

Question

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.

Answer 1

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;
}

Answer 2

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.