# Grid walk problem and solving it recursively

On CodeEval, there's a Grid Walk challenge:

There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).

Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

The first solution that came to my mind, intuitively, is to walk possible points recursively, breadth-first. Like this:

var monkey = function (x, y) {
if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
visited.push({x: x, y: y});
return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
} else {
return 0;
}
};


So I return the count of current point and all adjacent points recursively, checking each point that it's allowed by game rules and hasn't been visited before. First is that the sum of the digits of x and y is less or equal 19; second is that the point isn't in visited array. The complete code is like:

var visited = [];

var isPointAllowed = function (x, y) {
var o = 0;
for (var i = 0, x = Math.abs(x), s = x.toString(), l = s.length; i < l; o += +s[i++]);
for (var i = 0, y = Math.abs(y), s = y.toString(), l = s.length; i < l; o += +s[i++]);
return o <= 19;
};

var isPointVisited = function (x, y) {
for (var i = 0; i < visited.length; i++) {
if (visited[i].x == x && visited[i].y == y)
return true;
}

return false;
};

var monkey = function (x, y) {
if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
visited.push({x: x, y: y});
return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
} else {
return 0;
}
};

console.log(monkey(0, 0));


The problem is that, on CodeEval's environment, my code executes more than 10 seconds, thus is always being terminated, and the challenge failed.

I tried to optimize the search and modified it to search only one (first) quadrant:

var monkey = function (x, y) {
if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
visited.push({x: x, y: y});
return 1 + monkey(x + 1, y) + monkey(x, y + 1);
} else {
return 0;
}
};

console.log(monkey(0, 0)*4 - 299*4 + 1);


It outputs correct value but is still too slow.

Am I doing it wrong with recursion? Should I abandon this idea and implement simple nested cycle search?

What are most inefficient fragments of my code, like searching exhaustively for each point within visited array?

P.S. The problem itself is duplicate here but I believe my question is unique.

• Welcome to Code Review! Don't worry, we rarely close questions as duplicates here. Feb 22, 2015 at 19:37
• Have you tried to profile your code to see what's slow in your code ? For example, in Chrome, you have one profiler for javascript in Tools -> Developer Tools -> Profiles. Feb 22, 2015 at 23:48
• I run the code on Node and I haven't used server-side profiles before. However, it's nice of you to give such an advice, I'll try to profile the code in Chrome. Feb 23, 2015 at 13:05
• So I found out that isPointVisited function was flawed. Iterative search in an array is slower that accessing certain value by key. I should have thought about that. Feb 23, 2015 at 21:09

Profiling the code has shown that iterative search in sequential array (integer keys 0, 1, ...) is far slower that simply accessing a value by string key in an associative array of non-sequential keys represented by strings (like '-1,1' or similar). So I modified isPointVisited function:

var isPointVisited = function (x, y) {
// console.log('isPointVisited, x = %s, y = %s', x, y);
if (visited[[x, y]])
return true;

return false;
};


and monkey function:

var monkey = function (x, y) {
if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
visited[[x, y]] = true;
return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
} else {
return 0;
}
};


This code still executes for a bit longer than 10 seconds (11800 ms on CodeEval) but it's at least 8 times faster than before.