Project Euler Problem 15

Problem 15

19 April 2002

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

Answer: 137846528820

 

 

n right moves

n down moves

choose n down moves out of 2n, where n = 20

40C20

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    class Program {
        static void Main(string[] args) {            
            // 40! / 20! / 20!
            // = 40(39)..21 / 20!
            BigInteger p = 1;
            for (int i = 40; i >= 21; i--) {
                p *= i;
            }
            for (int i = 20; i >= 1; i--) {
                p /= i;
            }
            Console.WriteLine(p);
            Console.ReadKey();
        }
    }
}

Python

def problem15():
    # 40! / 20! / 20!
    # = 40(39)..21 / 20!
    p = 1
    for i in xrange(40, 20, -1):
        p *= i    
    for i in xrange(20, 0, -1):
        p /= i    
    print p
    
problem15()


Go

func problem15() {
    // 40! / 20! / 20!
    // = 40(39)..21 / 20!
    p := big.NewInt(1)
    for i := 40; i >= 21; i-- {
        p.Mul(p, big.NewInt(int64(i)))

    }
    for i := 20; i >= 1; i-- {
        p.Div(p, big.NewInt(int64(i)))
    }
    fmt.Println(p)
}

func main() {
    problem15()
}


C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class BigInteger {
private:
    string value;
public:
    BigInteger() : value("0") {}
    BigInteger(string s): value(s) {}
    BigInteger operator +(BigInteger other) {
        auto length = max(value.length(), other.value.length());
        string r = "";        
        auto carry = 0;
        for (unsigned int d = 0; d <= length - 1; d++) {
            auto s = carry + (*this)[d] + other[d];
            auto s2 = s % 10;            
            r = ::ToString(s2) + r;

            carry = s / 10;
        }
        if (carry > 0) r = ::ToString(carry) + r;
        return BigInteger(r);
    }

    BigInteger operator *(int other) {
        auto length = value.length();
        string r = "";        
        auto carry = 0;
        for (unsigned int d = 0; d <= length - 1; d++) {
            auto s = carry + (*this)[d] * other;
            auto s2 = s % 10;
            r = ::ToString(s2) + r;

            carry = s / 10;
        }
        if (carry > 0) r = ::ToString(carry) + r;
        return BigInteger(r);
    }

    BigInteger operator /(int other) {
        BigInteger r = "";        
        int carry = 0;
        for (unsigned int i = 0; i < value.length(); i++) {
            int c = value[i] - '0';
            int c2 = c + carry * 10;
            carry = c2 % other;
            c2 /= other;
            if (r.value.length() > 0 || c2 != 0) r.value += ::ToString(c2);
        }

        return r;
    }

    int operator [](unsigned int digit) {
        auto length = value.length();
        if (digit > length - 1) return 0;
        return value[length - 1 - digit] - '0';
    }

    string ToString() {
        return value;
    }
};

void problem15() {
    // 40! / 20! / 20!
    // = 40(39)..21 / 20!
    BigInteger p = "1";
    for (int i = 40; i >= 21; i--) {
        p = p * i;
    }
    for (int i = 20; i >= 1; i--) {
        p = p / i;        
    }
    cout << p.ToString() << endl;
}

 
Racket
 
(define (problem15)
  ; 40! / 20! / 20!
  (display (/ (apply * (range 40 20 -1)) (apply * (range 20 0 -1)))))