C++ Implementation of Problem 15

View source code here on GitHub!

Includes

Solution

uint64_t p0015()
int main(int argc, char const *argv[])

Note

This function is only present in the Python test runner, or when compiling as a standalone program.

 1/*
 2Project Euler Problem 15
 3
 4Turns out this is easy, if you think sideways a bit
 5
 6You can only go down or right. If we say right=1, then you can only have 20 1s, since otherwise you go off the grid.
 7You also can't have fewer than 20 1s, since then you go off the grid the other way. This means you can look at it as a
 8bit string, and the number of 40-bit strings with 20 1s is 40c20.
 9
10Problem:
11
12Starting 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
13routes to the bottom right corner.
14
15How many such routes are there through a 20×20 grid?
16*/
17#ifndef EULER_P0015
18#define EULER_P0015
19#include <stdint.h>
20#include <iostream>
21#include "include/macros.hpp"
22#include "include/math.hpp"
23
24uint64_t EMSCRIPTEN_KEEPALIVE p0015() {
25    return n_choose_r(40, 20);
26}
27
28PROGRAM_TAIL(p0015)
29#endif

Tags: combinatorics