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