Lattice traversal functional algorithm

I have the following code which returned the solution I was wanting after running for 1 hour. Are there any techniques I could use to improve run-time?

If I were using imperative programming I would just more aggressively cache the partial results, but that's less appropriate for this approach.

How should I transform this function so it will have less run-time?

-module(pathing).
-export([paths/1]).

paths(N) -> paths(N, 0, 0, 0).

paths(0, 0, 0, 0) -> 1;
paths(0, _, _, _) -> 0;
paths(N, X, Y, Z) -> paths(N-1, X, Y+1, Z-1) 
                 + paths(N-1, X, Y-1, Z+1)
                 + paths(N-1, X+1, Y, Z-1)
                 + paths(N-1, X-1, Y, Z+1)
                 + paths(N-1, X+1, Y-1, Z)
                 + paths(N-1, X-1, Y+1, Z).

The problem is to count the number of paths from a cell to itself in N steps on a hex grid.

p.s. This is a problem from a problem site. I would link to the problem but I don't wish for this to be a spoiler, and I am happy that this code is correct in terms of the actual problem definition.

Caching is definitely appropriate here as well. You can carry a cache through the calculations using an Erlang map.

I took your original code and made the following modifications:

• Grouped the values into a tuple to make it easy to use them together as a cache key.

• Changed the paths/4 function to paths/3, which takes as its arguments a list of value tuples, an accumulated sum, and a map for caching.

• Made paths/3 recursively walk the list of value tuples passed to it. For each value tuple (the head of the list), it checks the cache and if the value tuple is present, it uses the cached sum, but if not found, it calculates the sum for that value tuple and caches it. When the list of value tuples is empty, the accumulated sum is returned.

Here's the revised code:

-module(pathing).
-export([paths/1]).

paths(N) ->
    {Result, _} = paths([{N, 0, 0, 0}], 0, #{}),
    Result.

paths([], Sum, C) ->
    {Sum, C};
paths([{0, 0, 0, 0}|T], Sum, C) ->
    paths(T, Sum+1, C);
paths([{0, _, _, _}|T], Sum, C) ->
    paths(T, Sum, C);
paths([{N, X, Y, Z}=Key|T], Sum, C) ->
    {NewSum,NC} = case maps:get(Key,C,undefined) of
                      undefined ->
                          {NS,NC0} = paths([{N-1, X, Y+1, Z-1},
                                            {N-1, X, Y-1, Z+1},
                                            {N-1, X+1, Y, Z-1},
                                            {N-1, X-1, Y, Z+1},
                                            {N-1, X+1, Y-1, Z},
                                            {N-1, X-1, Y+1, Z}],0,C),
                          {NS,maps:put(Key,NS,NC0)};
                      S ->
                          {S,C}
                  end,
    paths(T,Sum+NewSum,NC).

The final paths/3 clause is where all the interesting work occurs. It first calls maps:get/3 with a default value of undefined to check if the value tuple is present. If it's not, the default value of undefined is returned, and the case clause for undefined creates a new list of value tuples based on the incoming values of N, X, Y, and Z and passes it to a new paths/3 call, setting the initial sum value to 0 and passing the current cache. This call returns a 2-tuple comprising the sum for that value tuple and a new cache. The final line in this case clause inserts the sum for the value tuple into the cache.

The case clause for when maps:get/3 finds the value tuple just returns the cached sum and the current cache.

The result of the case expression is stored into {NewSum,NC}, and then paths/3 is called recursively with T, which is the tail of the value tuple list, a new sum which is Sum+NewSum, and the new cache NC.

We can run the code in a list comprehension to calculate the running times for N values from 1 to 12 using timer:tc/3 like this:

[begin pathing:paths(V), {V,timer:tc(pathing,paths,[V])} end || V <- lists:seq(1,12)].

We execute the pathing:paths/1 function twice for each value and time only the second call — this is a non-rigorous attempt to prime caches and such to get a more accurate measurement.

Some results for your original code are:

[{1,{3,0}},
 {2,{4,6}},
 {3,{16,12}},
 {4,{86,90}},
 {5,{522,360}},
 {6,{2320,2040}},
 {7,{10364,10080}},
 {8,{55940,54810}},
 {9,{339876,290640}},
 {10,{2099300,1588356}},
 {11,{12857019,8676360}},
 {12,{75383602,47977776}}]

The first value is N, the second value the execution time in microseconds, and the third value the result of the pathing:paths/1 function for that N value.

For N values greater than 2, there is roughly a 6x increase in run time at each step. For N of 12, the execution time is just over 75 seconds.

Here are the results for the revised code:

[{1,{4,0}},
 {2,{8,6}},
 {3,{43,12}},
 {4,{139,90}},
 {5,{229,360}},
 {6,{383,2040}},
 {7,{485,10080}},
 {8,{744,54810}},
 {9,{987,290640}},
 {10,{1351,1588356}},
 {11,{1549,8676360}},
 {12,{2683,47977776}}]

First, we can see that the third numbers, the function results, are identical to those for the original code. This means that either the new code is also correct, or both versions are incorrect.

As you can see the execution times are greatly reduced from the original code for all values of N greater than 4. For the smaller values, the original code is faster because it doesn't have any caching overhead. But for the larger values, each increment in N results in only a small increase in execution time. For N of 12, the run time is only 2.68ms, which is roughly 28000 times faster than the original code. With the revised code, calculating N=100 takes only 2.8 seconds:

{100,{2792880,1791977497884763591097926128926348807126038292969051375074848031878536740320}}

StackExchange Code Review Q#105118, answer score: 2