Project Euler Problem 15

I think this problem is about combinatorics, i.e. finding out in how many ways a series of discrete values can be combined. For this problem I'm going to use factorials, mathematically expressed as "!".

2x2 has 3! combinations: 3x2x1=6
3x3 has 4! combinations: 4x3x2x1=24
4x4 has 5! combinations: 5x4x3x2x1=120

etc.

What I want to do is to write a code that calculated factorials and tells me what 21! is.

def calculate_factorial(val):
    result = 1    for x in range(1, val + 1):
        result *= x
    return result

print(calculate_factorial(21))

  
Outputs: 51090942171709440000 which is WRONG. I'm guessing that it's because this way of doing it includes duplicates of routes. Another approach is to write all routes as directions. I chose R for right and D for down. On a 2x2 grid, going from upper left corner to lower right corner, it takes four directions: RRDD. As long as these four directions are included in the route, it will make the route complete. So I want to make a program that checks all the combinations of the directions and removes all duplicates. When I google for help on these problems I try to avoid websites that addresses the very problems that I'm working on (there's a lot of help to get on Project Euler problems already).

I found a video about this type of problem and I was on the way to finding the solution, what I missed though was that I need to divide the factorial with the number of directions that I'll take (20xR and 20xD). So I get: c(40,(20,20)) which is 40!/(20!20!). Voila, I got it to work. This code works for any grid sized ROW*COLUMN.

def factorial(val):
    result = 1    for x in range(1, val + 1):
        result *= x
    return result


def routes(down, right):
    result = factorial(down + right) / (factorial(down) * factorial(right))
    return int(result)

print("Routes: ", routes(20, 20))

To make this problem a little bit more interesting I'm going to let the user input values in the console instead of having it hard coded. By the way, when googling around, I found an interesting quote:

"The classical Python mentality, though, is that it's easier to ask forgiveness than permission. In other words, don't check whether x is an integer; assume that it is and catch the exception results if it isn't:

try:
    x += 1
except TypeError:
    ..."

So I'm also going to give try-except a shot.

def factorial(val):
    result = 1
    for x in range(1, val + 1):
        result *= x
    return result


def routes(down, right):
    result = factorial(down + right) / (factorial(down) * factorial(right))
    return int(result)

rowInput = input("Rows:")
colInput = input("Columns:")
try:
    print("Routes: ", routes(int(rowInput), int(colInput)))
except:
    print("Invalid input")

Aaaaand it works!

/Ludvig