Project Euler problem 15 : code and explanation

The problem is simply stated as -

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Note, we can not move up, or left at any point.
For input 2, there are 6 ways, as shown-

Solution 1- There is a combinatorics solution, which reduces the problem to a simple expression, in terms of 'N', but I solved it using Dynamic Programming, which is solution 2. If you want the expression, just ask :)

Solution 2 - There is a common problem in programming, where we need to find the sum of elements in a NxN matrix, moving from top left to bottom right, in same fashion. So I just use the strategy, but instead of summing the elements, I counted the number of paths. Also for a input N, the DP solution of mine needs a matrix of size (N+1)x(N+1). Try visualizing the above image imposed on a 3x3 matrix.

Python code-

#Problem 15

import numpy

table = numpy.zeros((21, 21), dtype=numpy.int64)

def rec(r, c):
    if table[r, c] != 0:
        return table[r, c]
    if r == 0 and c == 0:
        return 1
    rsum = 0
    csum = 0
    if r != 0:
        rsum = rec(r-1, c)
    if c != 0:
        csum = rec(r, c-1)
    table[r, c] = rsum + csum
    return rsum + csum

if __name__ == "__main__":
    n = int(raw_input("Enter n : "))
    print rec(n, n)

If I remove the memoization, the input number '20' will take forever to come with solution.

Redirecting standard input and standard output

Redirecting input to stdin from a file -
./a.out < in.txt

Redirecting input from stdout to a file -
./a.out > out.txt

Combining both -
./a.out < in.txt > out.txt

Sum of digits of factorial of a number

This is another projecteuler.net problem. This is again, very simple and gives programmers a chance to practice any new language they are learning. I wrote it in Python :)

#Problem 20
#Sum of digits in factorial

def fact(n):
    m = int(n/5)
    r = n - (m*5)
    i = 1
    f = 1
    while m > 0:
        m = m - 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f / 10
    while r > 0:
        r = r - 1
        f = f * i
        i = i + 1
    return f

def digsum(n):
    s = 0
    while n > 0:
        s = s + (n%10)
        n = n/10
    return s

if __name__ == "__main__":
    n = int(raw_input("Enter n : "))
    f = fact(n)
    s = digsum(f)
    print f, s

Read the code carefully, while it is not perfect (100% correct though), there are many things to learn for newbie.