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.

About these ads

Pages: 1 2

14 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:
                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        
    
  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[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;
    }

  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[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;
    }
    
  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;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 617 other followers

%d bloggers like this: