/
pe_015.rb
31 lines (27 loc) · 897 Bytes
/
pe_015.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
#
# How many routes are there through a 20×20 grid?
# The Grid can be modelled as a pascals triangle, with the start node being the bottom right corner for the grid
# for a nxn grid, the number of levels in the pascals triangle is 2*n+1
def pascals_triangle_max(size)
levels = 2*size+1
pascals = [[0], [1,1]]
l=3
for i in 2..levels-1
temp_arr = []
for j in 0..l-1
case j
when 0
temp_arr[j] = pascals[i-1][j]
when l-1
temp_arr[j] = pascals[i-1][j-1]
else
temp_arr[j] = pascals[i-1][j-1] + pascals[i-1][j]
end
end
pascals[i] = temp_arr
l+=1
end
pascals[levels-1].max
end
pascals_triangle_max(20)