Project Euler, Lattice path - Problem 15

4 views (last 30 days)
Robin Lindström
Robin Lindström on 11 Aug 2016
Answered: Ramon Villamangca on 21 Jun 2021
This is the problem I am trying to solve:
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
count = count + 1; %If at top right position add to counter
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
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 :
| | | |
| | | |
| | | |
gives : (the nodes are integers alone and the vertices and weights are marked with slashes and brackets)
[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]
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.

Sign in to comment.

Answers (1)

Ramon Villamangca
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)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!