Treasure hunting robots summary

When I first read this puzzle on the Google Treasure hunt page I didn't think that much of it, but it's clearly actually quite good. Lots of great code, all of it much better than mine which was the worst solution of the lot.

Here's my C++ code:

#include <algorithm>
#include <string>
#include <iostream>

int main() {
    uint64_t answer = 0;
    std::string question(
        std::string( 54, 'd' ) +
        std::string( 42, 'r' )
    );
    for ( ; std::next_permutation( question.begin(), question.end() ); ++answer )
        if ( answer % 1000000 == 0 )
            std::cout << answer << ": " << question << std::endl;
    std::cout << "There are " << answer << " paths" << std::endl;
}

There are two big problems with this code (and one small one). The first is that it gives the wrong answer. As Jon Randy pointed out, if you're looking for the answer on a 3 by 7 grid you can only go right twice and down six times. The code should be searching for permutations of 53 ds and 41 rs.

The second thing that's wrong with it is that it won't produce an answer at all. Well, not without leaving it to run for a very, very long time. Let's put the futility of this solution into perspective.

After running for about 985 minutes (about 16 and a half hours) the program had tried out an impressive 2,018,494,000,000 routes — after all it was checking more than 34 million paths per second. That's super fast. Still, the answer is 760,365,888,182,828,026,538,367,852 and in order to have counted all of the permutations I'd have had to leave it running for around 705,953,403,388 years!

Oh and there's one last problem — it doesn't count the first permutation so it'll be off by one. All in all a pretty poor attempt. All of this is of course what happens when you don't think before you start to tap away at the keyboard.

Thankfully other people were thinking and the right answer was offered by both Jon Randy and JordiB. JordiB posted this Java solution:

import java.math.BigDecimal;

public class Treasure {
    public static void main(String[] args) {
        final int x = 54;
        final int y = 42;

        final int R = Math.min(x,y)-1;
        final int N = x+y-2;

        BigDecimal paths = new BigDecimal(1);
        for (int i = 0; i < R; i++) {
            paths = paths.multiply(new BigDecimal(N-i)).divide(new BigDecimal(i+1));
        }
        System.out.println("Paths: "+paths.toString());
    }
}

Jon didn't send in the code he used, but JordiB certainly spotted a nice little optimisation that cuts down on the size of the numbers used in the partial results and the number of multiplications required.

I think the size of the partial results is the only “problem” with this solution¹ [1Not that it really is a problem if you don't need to worry about overflow on your integer types.], which is neatly side stepped by luke_bkk's Ruby version.

def robot(rows, cols)
  matrix = Array.new(rows).collect{ Array.new(cols) }
  x, y = rows-1, cols-1
  x.downto(0) do |row|
    y.downto(0) do |col|
      a = (matrix[row+1][col] unless matrix[row+1].nil?) || 0
      b = matrix[row][col+1] || 0
      sum = a + b
      matrix[row][col] = sum > 0 ? sum : 1
    end
  end
  matrix[0][0]
end
 
start = Time.now
solution = robot(48, 54)
time = Time.now - start
puts "Robot solution #{solution} computed in #{time}s"

luke_bkk's is very clever. It works out by repeated calculation the number of paths by working back from the destination and realising that the paths going through any point on the grid is related to the number of paths going through the points around it.

So, well done JordiB, Jon Randy & luke_bkk. Not so good Kirit, must try harder…

let factorial n = foldr1 (*) [ 1 .. n ]
let routes r d = factorial (r+d-2) `div` factorial (r-1) `div` factorial (d-1)