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 n are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than n. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than n.
How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?
Input sample:
There is no input for this program.
Output sample:
Print the number of points the monkey can access. It should be printed as an integer — for example, if the number of points is 10, print “10”, not “10.0” or “10.00”, et
I used JavaScript like below.
const monkeyPlay = (sum) => {
const availablePoints = [{ x: 0, y: 0 }];
const result = [];
const checkAvailable = (point) => {
if (!exist(result, point) && getSum(point.x) + getSum(point.y) <= sum) {
result.push(point);
availablePoints.push(
{ x: point.x + 1, y: point.y },
{ x: point.x, y: point.y + 1 },
{ x: point.x - 1, y: point.y },
{ x: point.x, y: point.y - 1 }
);
}
};
while (availablePoints.length != 0) {
checkAvailable(availablePoints.pop());
}
return result;
};
console.log(monkeyPlay(19));
It works correctly but takes too long time when n>=19.
I’ll be appreciated of any help.
Thanks.