## 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.

Pages: 1 2

### 15 Responses to “Monkey Grid Puzzle”

1. Priyank said

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.

2. programmingpraxis said

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

3. Paul said

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

```DDIG = dict(zip("0123456789", range(10)))

def digits(number, reverse=False):
"""Generator to split a number (int) into a list of numbers
if reverse is True, the digits are yielded in reverse order
the fastest
"""
s = str(abs(number))
if reverse: s = reversed(s)
return (DDIG[c] for c in s)

def sum_digits(x):
return sum(digits(abs(x)))

def accessible(x, y):
return sum_digits(x) + sum_digits(y) <= 19

def brute_force():
points = set()
Q = [(0, 0)]
while Q:
p = Q.pop()
if not p in points:
x, y = p
newp = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
Q += [(a, b) for a, b in newp if accessible(a, b)]
return len(points)

print brute_force()
# -> 102485
```
4. brainydexter said

@programmingpraxis: No, I don’t.

5. grin said

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

6. Paolo said

This is my c++ solution :)

#include
#include

struct MonkeyGrid {
int pts;
int numPts;

MonkeyGrid() {
memset(&(pts), 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);
}
};

int main(int argc, char**argv) {
MonkeyGrid monkeygrid;
printf(“Monkey Grid Puzzle Result is: %d\n”, monkeygrid.numPts);
getchar();
return 0;
}

7. Paolo said

Apologies for not having read the HOWTO pages before posting.
Hope code is properly formatted this time..

```#include <stdio.h>
#include <cstring>

struct MonkeyGrid {
int pts;
int numPts;

MonkeyGrid() {
memset(&(pts), 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);
}
};

int main(int argc, char**argv) {
MonkeyGrid monkeygrid;
printf("Monkey Grid Puzzle Result is: %d\n", monkeygrid.numPts);
getchar();
return 0;
}
```
8. Ben said

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.

9. Ben said

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.

10. Priyank said

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

11. Daniel said

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.

```(defun space-points (space)
(let ((x (car space))
(y (cdr space)))
(reduce #'+ (map 'list #'(lambda (c)
(digit-char-p c))
(format nil "~s~s" (abs x) (abs y))))))

(defun successors (space)
(let ((x (car space))
(y (cdr space)))
(list (cons (1+ x) y)
(cons (1- x) y)
(cons x (1+ y))
(cons x (1- y)))))

(defun explored (space explored)
(gethash space explored))

(defun unexplored-successors (space explored)
(remove-if #'(lambda (s)
(explored s explored))
(successors space)))

(defun cnt (space)
(let ((unexplored (list space))
(explored (make-hash-table :test 'equal)))
(labels ((rec (cnt)
(if (null unexplored)
cnt
(let ((next (pop unexplored)))
(if (explored next explored)
(rec cnt)
(let ((match (<= (space-points next) 19)))
(setf (gethash next explored) t)
(when match
(dolist (s (unexplored-successors next explored))
(push s unexplored)))
(rec (if match (1+ cnt) cnt))))))))
(rec 0))))

(time (cnt '(0 . 0)))
```
12. rayl said

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

http://pastebin.com/G2MKxkrT

13. JP said

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

14. Juan Ignacio Saba said

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

```#!/usr/bin/perl -w

use strict;
use warnings;

# Calculate points
my \$points = points();
my (\$min_x, \$min_y) = (0, 0);
foreach my \$p (keys %{\$points}) {
my (\$x, \$y) = split ":", \$p;
\$min_x = \$x if \$x < \$min_x;
\$min_y = \$y if \$y < \$min_y;
}

# Print points
for(my \$x = -abs(\$min_x); \$x <= abs(\$min_x); \$x++) {
for(my \$y = abs(\$min_y); \$y >= -abs(\$min_y); \$y--) {
print "O" if(defined \$points->{"\$x:\$y"});
print " " if(!defined \$points->{"\$x:\$y"});
}
print "\n";
}

sub accessible {
my \$x = shift;
my \$y = shift;

my \$sum = 0;
map { \$sum += \$_; } split "", "".abs(\$x);
map { \$sum += \$_; } split "", "".abs(\$y);
return \$sum <= 19;
}

sub points {
my \$points = {};
my \$queue = [[0,0]];
while(scalar(@{\$queue}) > 0) {
my \$p = pop(@{\$queue});
my (\$x, \$y) = @{\$p};
if(!defined \$points->{"\$x:\$y"}) {
\$points->{"\$x:\$y"} = 1;
push @{\$queue}, [\$x-1,\$y] if accessible(\$x-1,\$y);
push @{\$queue}, [\$x+1,\$y] if accessible(\$x+1,\$y);
push @{\$queue}, [\$x,\$y-1] if accessible(\$x,\$y-1);
push @{\$queue}, [\$x,\$y+1] if accessible(\$x,\$y+1);
}
}
return \$points;
}
```
15. Burke said

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