Project Euler, Lattice path - Problem 15
2 views (last 30 days)
Show older comments
This is the problem I am trying to solve: https://projecteuler.net/problem=15
I thought iteration would be the best choice and this is my function:
function [ ] = lattice( N, E )
global count n e %global variables, counter and position (north, east)
if N ~= n && E ~= e %If not at end of square
lattice(N+1,E) %Add to north position
lattice(N,E+1) %Add to east position
elseif N ~= n %If not at north end of square
lattice(N+1,E) %Add to north position
elseif E ~= e %If not at east end of square
lattice(N,E+1) %Add to east position
else
count = count + 1; %If at top right position add to counter
end
So I start the function with lattice(0,0) and it returns the correct amount of possible ways in a 2x2 grid (n=2 and e=2) and it is fast but it quickly gets too slow for bigger n and e.
As far as I can imagine I am not counting any paths more than once so I am not sure why it is so slow. Any ideas on how I can improve this code?
1 Comment
Pham Dang
on 12 Aug 2016
You are using a greedy algorithm and the number of cases to test is really huge. In the "Problem 15", the order of magnitude of the solution is 10^11. If each step of your algorithm takes 1µs (and I expect it to longer), it would take about 28 hours to perform the whole algorithm.
To solve this problem, I used graphs : each corner can be represented as a node. The path between each corner is represented by a vertex. This graph has cycles.
The vertices leaving a given node have to be weighted by a coefficient which is obtain by summing the weights of the vertices arriving to this node.
For example :
1--2--4--7
| | | |
3--5--8--11
| | | |
6--9--12-14
| | | |
10-13-15-16
gives : (the nodes are integers alone and the vertices and weights are marked with slashes and brackets)
1
[1]/ \[1]
2 3
[1]/ \[1][1]/ \[1]
4 5 6
[1]/ \[1] [2]/ \[2] [1]/ \[1]
7 8 9 10
[1]\ /[3] [3]\ /[3] [3]\ /[1]
11 12 13
[4]\ /[6] [6]\ /[4]
14 15
[10]\ /[10]
16
[20]
The number of paths are the sum of external weights below the widest row of nodes : ([1] + [4] + [10] + [20])*2 = 70
Building this tree and counting the weights with a program is much faster than the greedy approach.
Answers (1)
Ramon Villamangca
on 21 Jun 2021
Project Euler Problem #15, is a combinatorial problem. if we mark going down as "D" and going the right as "R", the problem is reduced to finding all arrangements of 20-D's and 20-R's. So the code is simply:
answer = factorial(40)/(factorial(20)^2)
0 Comments
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!