## Monkey Grid Puzzle

### August 16, 2013

It is obvious that the monkey is limited to the range -300 to +300 on both axes, since 2+9+9>19, so a brute force search will be sufficient. We can limit our search to the first quadrant of the plane, so from point (x,y) the monkey can move to (x+1,y) or (x, y+1), and we can start our search at (0,0), being sure not to visit the same point twice:

`(define visited (make-matrix 301 301 #f)`

```(define (monkey x y)   (if (matrix-ref visited x y) 0     (begin (matrix-set! visited x y #t)            (if (not (legit? x y)) 0              (+ (count x y)                 (monkey (+ x 1) y)                 (monkey x (+ y 1)))))))```

A point (x,y) is legitimate if the sum of the digits is less than or equal to nineteen:

```(define (legit? x y)   (< (+ (sum (digits x)) (sum (digits y))) 20))```

The only other thing we need is to count the points. The origin counts once. Each point on an axis counts twice, because we only include two of the four axes in our search. And each point in the interior counts four times, once for each quadrant:

```(define (count x y)   (cond ((and (zero? x) (zero? y)) 1) ; origin         ((or (zero? x) (zero? y)) 2) ; axis         (else 4))) ; other points```

And that’s it:

```> (monkey 0 0) 102485```

We used `sum`, `digits`, and the matrix functions from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/68dndvxS. Fun little problem.

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