## Monkey Grid Puzzle

### August 16, 2013

I’m not sure of the original source of this fun little puzzle:

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?

Your task is to write a program that counts the number of available points. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Glad to see my post on SO showed up here.

As a further optimization, you can actually limit your search from first quadrant, to 0 to 45 degrees. That is, if(x,y) is reachable, so is (y,x). This way, you search for less number of points. Also, if (x,y) is a legit point, then you should add (y,x) to the set where you count points.

@Priyank: Do you know the original source of the puzzle?

In Python. It runs in about 1 sec, so there is no point to optimize.

@programmingpraxis: No, I don’t.

uint64_t stupid(const uint64_t max) { return(1+2*max*(max+1)); } // this is incredibly silly

This is my c++ solution :)

#include

#include

struct MonkeyGrid {

int pts[300][300];

int numPts;

MonkeyGrid() {

memset(&(pts[0][0]), 0, 300*300*sizeof(int));

numPts = traverse(0, 0);

}

int traverse(int x, int y) {

if (((x/100 + (x%100)/10 + (x%10))+(y/100 + (y%100)/10 + (y%10))) > 19)

return 0;

if (pts[x][y])

return 0;

int tot = pts[x][y] = (x==y)? (1 + 3*(x!=0)) : (4 + 4*(y!=0));

tot += traverse(x+1, y);

if (x > y)

tot += traverse(x, y+1);

return tot;

}

};

int main(int argc, char**argv) {

MonkeyGrid monkeygrid;

printf(“Monkey Grid Puzzle Result is: %d\n”, monkeygrid.numPts);

getchar();

return 0;

}

Apologies for not having read the HOWTO pages before posting.

Hope code is properly formatted this time..

A solution in Clojure:

http://pastebin.com/fyQ4BNSD

It generates a lazy sequence of all the positions that are accessible to the monkey. Determining the number of such positions is a simple matter of counting the number of elements in this sequence. It takes advantage of symmetry to reduce the amount of work to be done.

https://www.refheap.com/17735

This solution computes the number of squares reachable by the monkey starting at [0,0] without generating an intermediate sequence and is correspondingly faster than my previously posted solution.

I get it to run in 16 ms here: http://ideone.com/5IwYkP

Here’s a Common Lisp brute force solution. It’s not elegant or efficient, but it returns 102,485 in less than half a second on my machine.

Here’s a Haskell solution, although probably not optimal (about 30 ms on my machine)

http://pastebin.com/G2MKxkrT

I went a slightly different direction, generating an image of the result rather than just counting points. There’s also a bit about depth-first vs breadth-first searches and a few other functions (testing if the x/y coordinates are prime / coprime looks rather neat).

Pretty pictures: Visualizing the Monkey Grid

Here’s Paul’s brute force solution, adapted for Perl, and modified to print the ASCII “image” to STDOUT.

Here’s a solution that goes up to 7712 in under 5 seconds on ideone.com. I know for sure that it’s correct up to level 43 http://ideone.com/vECpmq