3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Don't worry, we rarely close questions as duplicates here. \$\endgroup\$ – 200_success Feb 22 '15 at 19:37
  • \$\begingroup\$ 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. \$\endgroup\$ – Loufylouf Feb 22 '15 at 23:48
  • \$\begingroup\$ 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. \$\endgroup\$ – Fleischpflanzerl Feb 23 '15 at 13:05
  • \$\begingroup\$ 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. \$\endgroup\$ – Fleischpflanzerl Feb 23 '15 at 21:09
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.