Grid walk problem and solving it recursively

Question

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.

Answer 1

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.