August 16, 2013 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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.
By Priyank on August 16, 2013 at 9:10 AM
@Priyank: Do you know the original source of the puzzle?
By programmingpraxis on August 16, 2013 at 12:37 PM
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() # -> 102485By Paul on August 16, 2013 at 1:16 PM
@programmingpraxis: No, I don’t.
By brainydexter on August 16, 2013 at 2:48 PM
uint64_t stupid(const uint64_t max) { return(1+2*max*(max+1)); } // this is incredibly silly
By grin on August 16, 2013 at 4:46 PM
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;
}
By Paolo on August 17, 2013 at 6:30 PM
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; }By Paolo on August 17, 2013 at 6:42 PM
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.
By Ben on August 17, 2013 at 7:50 PM
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.
By Ben on August 18, 2013 at 2:50 PM
I get it to run in 16 ms here: http://ideone.com/5IwYkP
By Priyank on August 18, 2013 at 7:01 PM
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)))By Daniel on August 19, 2013 at 3:48 AM
Here’s a Haskell solution, although probably not optimal (about 30 ms on my machine)
http://pastebin.com/G2MKxkrT
By rayl on August 23, 2013 at 11:34 PM
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
By JP on August 30, 2013 at 4:49 PM
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; }By Juan Ignacio Saba on January 7, 2014 at 8:47 PM
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
By Burke on November 12, 2014 at 9:45 PM