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.

About these ads

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

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 635 other followers

%d bloggers like this: