Lua Implementation of Problem 15
View source code here on GitHub!
Includes
math <./lib/math.html>
Solution
- solution()
- Returns:
The solution to problem 15
- Return type:
number
1-- Project Euler Problem 15
2--
3-- Turns out this is easy, if you think sideways a bit
4--
5-- You 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.
6-- You 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
7-- a bit string, and the number of 40-bit strings with 20 1s is 40c20.
8--
9-- Problem:
10--
11-- 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
12-- routes to the bottom right corner.
13
14-- How many such routes are there through a 20×20 grid?
15
16local n_choose_r = loadlib("math").n_choose_r
17
18return {
19 solution = function()
20 return n_choose_r(40, 20)
21 end
22}