Google Treasurehunt: Question 4 (Solution)

Posted by admin on June 14th, 2008 filed in google, treasurehunt
Comment now »

Although I unluckily at the moment do not have the time to solve the question myself I googled a little and found following excellent solution: http://www.catonmat.net/blog/solving-google-treasure-hunt-prime-number-problem-four/

It shows that all of the questions can be solved using the Unix-SHELL as well as any other programming language. But there’s always plenty of choice …


Google Treasurehunt: Question 3 (Solution)

Posted by admin on June 14th, 2008 filed in google, treasurehunt
Comment now »

First of all: I have to apologize for not posting anything (especially the answer for question 3 or even question 4), but unluckily i have been quite busy in the last weeks. I haven’t even had to look for a solution for question 4 and wasn’t able to post my answer to question 3 which I had already figured pretty soon after the question was published. I hope I’ll find enough time to solve question 4, but we’ll see ;)

The solution for question 3 is even easier than the one for the question 2: You simply need to follow these simple rules as you go along the routing-path the packet takes:

  1. If there is an entry in the routing table containing the target IP follow the static route. Example: If there is a routing table entry “248.48.133.230 => 101.13.39.120″ and the target IP is 248.48.133.230 go to the Node with the IP 101.13.39.120
  2. If there is no static route take the default route (i.e. the default gateway)

    Fore reference a question and the corresponding answer:

    The answer: which is correct:


    Google Treasurehunt: Question 2 (Solution)

    Posted by admin on May 29th, 2008 filed in google, treasurehunt
    Comment now »

    Answering Question 2 doesn’t seem to be too difficult, but be aware: Most programming languages will place the first line at the index 0 of an array if you read any of the matching files into an array. Building the regular expression to match each of the path against is pretty much straight-forward:

    1. Before the first string there may be any number of characters
    2. Afterwards too ;)
    3. Before the extension there has to be a “.”
    4. The extension has to be the end of the string

    In Python this would be:

    1. import re
    2. r = re.compile(".*%s.*%s$" % (contains,ext))
    3. if not r.match(path) is None:
    4.      [more code]

    In PHP you’d have to put delimiters around the expression:

    1. if (preg_match("/.*$contains.*$ext$/",$path) {
    2.     [more code]
    3. }

    A function to get the right solution in Python would be:

    1. def get_solution(line,contains,ext,d=None):
    2.     r = re.compile(".*%s.*%s$" % (contains,ext))
    3.     ret = 0
    4.     if d is None:
    5.         d=startdir
    6.     for f in os.listdir(d):
    7.         f = os.path.join(d,f)
    8.         if os.path.isdir(f):
    9.             ret += s(line,contains,ext,f)
    10.         else:
    11.             if not r.match(f) is None:
    12.                 f=file(f).readlines()
    13.                 try:
    14.                     ret+=int(f[line-1])
    15.                 except:
    16.                     pass
    17.     return ret

    Where line is the Line to be added to the sum for each matching file and d the directory where the (unpacked) contents of the archive are located. The global startdir is another way to tell the function where the contents of the archive are. Using it the result for all files whose path contains “ghi” with the extension “.xml” or whose path contains “yz1″ with the extension “.pdf” can be determined like this:

    1. print get_solution(4,"ghi","\\.xml")*get_solution(1,"yz1","\\.pdf")


    Google Treasurehunt: Question 1 (Solution)

    Posted by admin on May 20th, 2008 filed in google, treasurehunt
    Comment now »

    Recently google started a quiz called “treasurehunt” which is hosted on their new “App Engine”-service.

    The first question is on combinatorics. I have seen plenty of approaches on the web for figuring out the number of unique paths the robot can take.

    What surprised me most was the fact, that only very few people tried a mathematical approach. Most used different kinds of iterative algorithms to determine the correct result. This is of course possible, but most likely slower than the mathematical solution:

    Looking at a 3×3 square you’ll notice, that the number of unique paths in each field form part of Pascal’s triangle:



    Thus any of the fields is equal to the binomial coefficient of the line and the column index.

    Knowing this a python program to compute the possible paths can be as easy as this:

    1. def binomial(n,k):
    2.      out=1
    3.      for i in range(1,k+1):
    4.          out = (out*(n-i+1))//i
    5.          return out    
    6. def robot_unique_paths(x,y):
    7.      x-=1
    8.      y-=1    
    9. return binomial(x+y,x)    
    10. #get user-input
    11. print "There are %d unique paths the robot can take!" % robot_unique_paths(
    12.      int(raw_input("Please enter width of the field: ")),
    13.      int(raw_input("Please enter the height of the field: "))
    14. )    
    15.  
    16. #everything after this line is only for convenience
    17. import sys
    18. from time import sleep
    19. print "Exiting in 30 secods"
    20. for i in range(1,30):
    21.      sys.stdout.write(".")
    22.      sleep(1)
    23.  

    Output:

    … which is the correct answer: