Project Euler, Lattice path - Problem 15

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?

[Pham Dang]

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.

Answer 1

[Ramon Villamangca]

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)