Za Waarudo: 05/2008

Just some days ago I found out about Google Treasure Hunt 2008, a fun series of questions to exercise problem-solving skills regarding computer science, networking, and low-level UNIX trivia. I just solved the first two problems, and I will be posting my solutions below, so be please do not read if you still plan on solving them (**spoilers below**).

First problem
The first problem is about a robot and a rectangular grid (with variable dimensions). The robot starts in the top-left corner and must proceed to the bottom-right corner by moving only to the right or downwards (i.e, it cannot move back to the left or upwards). Our mission is to answer how many possible paths can the robot take given the dimensions of the grid.

After I solved the problem, I was curious for other solutions, and googled a bit. Interestingly, most people correctly found the relationship of this problem with the sequences obtained by the Pascal's Triangle. In fact, I couldn't remember this fact, so I tried a more "visual" and "computer science" oriented approach.

The first attempt was to code the algorithm for moving right/down until the robot reached the bottom-right corner for a 50x57 grid. I ran the program but I noticed my naive approach would take me an infinite time to get an answer because the program would never return from recursion...

For the second attempt, I realized the number of possible paths from the cell at [X1, Y1] to the goal cell could be expressed as a constant number: the sum of the paths to the right and downwards (number of paths from [X1 + 1, Y1] plus number of paths [X1, Y1+1]). For that purpose, I created a matrix where the results are stored when they are first calculated. If they are found already calculated, there is no need to proceed to the goal, we can just use that result and sum it to the current subtotal. This made the program result immediately, instead of taking infinite time even for very large grids. I submitted this result to the Google Treasure Hunt 2008 website, but it was not correct. I decided to debug the program and I found out that the subtotals integers were being overflowed, because the answers to the problem indeed involved big numbers that neither 32 nor 64 bit would be enough to hold them. To solve this issue, I used Matt McCutchen's C++ Big Integer Library and converted my "unsigned long long" (64 bit number) to a BigUnsigned object, so that I could deal with virtually unlimited precision integers capable of storing a large sum, which is the case of the robot in a maze. Google Treasure Hunt 2008 accepted my submission after this change.

Second problem

The second problem involved downloading a zip file containing directories and text files. Our mission can be described by the following steps:

Finding each file whose relative path name matches a certain pattern

Reading a certain line (e.g.: 1st,2nd,3rd,4th, ... depending on the pattern) which should hold a number in text format (not binary)

Sum each set of numbers for each pattern (e.g. sum all numbers in the 3rd line for all *foo*.pdf path names, sum all numbers in the 5th line for all *bar*.rtf path names)

Answer: The result of multiplying all sums together (i.e.: sum1 * sum2 * ... * sumN) for all N patterns

Well, I believe the second problem could just involve UNIX shell scripting, but I did not want to mess with complicated expressions, filters or pipes... I decided to take a different approach from the first problem, and writing the solution in the Ruby language, which is easy to code, read and understand, and combined it with the UNIX find command to search for files that match a certain pattern, so I didn't have to deal with that. I realised that searching for just "*foo*.pdf" files would not be enough because the "*foo*" pattern would not match directories as required, just filenames, so many files would be ignored with such call. A complete call would be find . -ipath "*foo*" -iname "*.pdf" so the command would retrieve both "foo/bar/x.pdf" and "bar/foo.pdf", not just the latter.

Code for the solutions

Problem 1

Save the file as robot.cpp, download and extract the bigint library to the same directory and compile the program with:
g++ -Wall robot.cpp bigint/BigInteger.o bigint/BigIntegerUtils.o bigint/BigUnsigned.o bigint/BigUnsignedInABase.o -I bigint -o robot. You can call the program as ./robot 50 57 for a 50x57 grid.


/**
 * Google Treasure Hunt 2008 - Question 1
 * by Mário Freitas (imkira at gmail dot com)
 */

// standard libraries
#include 
#include 

// support for big integers
#include "BigInteger.hh"
#include "BigIntegerUtils.hh"

typedef BigUnsigned Counter;

Counter **gMatrix;
long gNumMatrixColumns, gNumMatrixRows;

inline Counter move (int x, int y)
{
 // number of paths already calculated?
 if (gMatrix[x-1][y-1] != Counter(0))
 {
  // we don't need to calculate it again, we can return it
  return gMatrix[x-1][y-1];
 }

 // number of paths for each direction
 Counter lNumRightPaths = 0, lNumDownPaths = 0;
 
 // can it move right?
 if (x < gNumMatrixColumns)
 {
  lNumRightPaths = move(x+1, y);
 }
 
 // can it move down?
 if (y < gNumMatrixRows)
 {
  lNumDownPaths = move(x, y+1);
 }
 
 // remember this result for the following iterations
 gMatrix[x-1][y-1] = lNumRightPaths + lNumDownPaths;
 
 // and return it
 return gMatrix[x-1][y-1];
}

int main (int argc, char *argv[])
{
 // correct command line syntax?
 if (argc != 3)
 {
  printf("Usage:  \n");
  exit(1);
 }
 
 // read number of columns and rows
 gNumMatrixColumns = strtol(argv[1], (char **)NULL, 10);
 gNumMatrixRows = strtol(argv[2], (char **)NULL, 10);
 
 // correct number of columns and rows?
 if ((gNumMatrixColumns <= 0) || (gNumMatrixRows <= 0))
 {
  printf("Invalid number of columns or rows\n");
  exit(1);
 }
 
 // create the matrix
 gMatrix = new Counter*[gNumMatrixColumns];
 for (int i = 0; i < gNumMatrixColumns; ++i)
 {
  // the default constructor should set the numbers to 0
  gMatrix[i] = new Counter[gNumMatrixRows];
 }
 
 // there is only one path from the goal cell to itself (i.e, by not moving)
 // this is used as the first stopping point for the recursive algorithm
 gMatrix[gNumMatrixColumns-1][gNumMatrixRows-1] = 1;
 
 // start at 1,1, move towards the goal and print the number of paths
 std::cout << move(1, 1) << std::endl;
 
 // destroy the matrix
 for (int i = 0; i < gNumMatrixColumns; ++i)
 {
  delete[] gMatrix[i];
 }
 delete[] gMatrix;
 
 exit(0);
}

Problem 2

Save the file as filesums.rb inside the directory that is created after extracting the zip file you downloaded from Google Treasure Hunt 2008. Change the sum_patterns code structure to reflect the patterns and line numbers for the problem in question. Run the program by calling ruby ./filesums.rb


#! /usr/bin/ruby
# Google Treasure Hunt 2008 - Question 2
# by Mário Freitas (imkira at gmail dot com)

# list of patterns:
# => line: the line number where to obtain the sum
# => find_file_pattern: the find command syntax that retrieves a list of files matching a pattern
sum_patterns = [
  { :line => 3, :find_file_pattern => 'find . -ipath "*foo*" -iname "*.pdf"' },
  { :line => 5, :find_file_pattern => 'find . -ipath "*zzz*" -iname "*.rtf"' }
]

# the product is initialized to 1
sums_product = 1

# iterate each file pattern
sum_patterns.each do |sum_pattern|
  # sum for current file pattern is initialized to 0
  current_sum = 0
  
  # find the list of files that match the current file pattern
  IO.popen(sum_pattern[:find_file_pattern]) do |pipe|
    
    # read the list of files that match the current file pattern
    file_paths = pipe.readlines
    
    # iterate each file
    file_paths.each do |file_path|
      # read the line where the sum is stored
      some_number = IO.readlines(file_path.chomp)[sum_pattern[:line] - 1]
      
      # increment the sum unless the line did not exist
      current_sum += some_number.to_i unless some_number.nil?
    end
  end
  
  sums_product *= current_sum
end

puts "The product of sums is #{sums_product}"

Za Waarudo

5/30/2008

Reviving an old project! Well, kind of...

5/23/2008

Google Treasure Hunt 2008

5/04/2008

Master Thesis on Visualisation Paradigms for 3D Map-Based Mobile Services

Blog Archive

About Me