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.
Programming Praxis 
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.
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: points.add(p) 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@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..
#include <stdio.h> #include <cstring> 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; }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.
(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)))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.
#!/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; }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