GCJ 2008: Saving the Universe

July 18th, 2008 § 3 comments

That’s was the title of the first and very funny problem of Google Code Jam Qualification Round 2008

The urban legend goes that if you go to the Google homepage and search for “Google”, the universe will implode. We have a secret to share… It is true! Please don’t try it, or tell anyone. All right, maybe not. We are just kidding.

You can find (I think you need to register) the whole problem here.

I did it recursively and for the large input I had to setrecursionlimit up to 2000. I’ll show you why…

You can download my solution here.

That’s my implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
sys.setrecursionlimit(20000)
 
def process(se, q, switch = 0):
    if len(q) == 0:
        return switch
    rank = {}
 
    notin = False
    for i in se:
        if q.count(i)>0:
            rank[i] = q.index(i)
        else:
            notin = i
 
    if notin == False:
        a,b = rank[se[0]],0
        for i in rank:
            if rank[i]>b:
                a = i
                b = rank[i]
        switch += 1
        return process(se,q[b:],switch)
 
    else:
        return switch

In words…

se is the list ( [‘Google’,’Yahoo’,…] ) of search engines
q is the list (like the one above) of queries

  • At the beginning I did no switches (switch = 0), but it’s a default value, when I’ll call it I’ll set it
  • If there is no query I don’t need to switch anymore, I can return the number of switches (switch)
  • rank is a dictionary. It’s just like ‘Search Engine': ‘position of the first query with the same name of this search engine’
  • if the name of a search engine does not appear in the query list I may do all searches with that search engines (the notin test)
  • else I look in the dictionary for what is the search engine that appear as later as possible in the query list and I use it, I add 1 to the switches counter, and return (recursively) the process giving the same se, the current switches number but a different query list!

The new query list is just the remaining queries. Example:

se = Yeehaw, NSM, Dont Ask, B9, Googol
q = Yeehaw,Yeehaw,Googol,B9,Googol,NSM,B9,NSM,Dont Ask,Googol

Call #1
We did no switch, so switch = 0
All search engines appears in the query list… Here is the list of each se with the index of the first query with the same name:

Yeehaw: 0, NSM: 5, Dont Ask: 8, B9: 3, Googol: 2

Dont Ask has an higher index so we can use that to search up to that index with it, and process the next call with the new query list:

se = Yeehaw, NSM, Dont Ask, B9, Googol
q = Dont Ask,Googol

Call #2
We did one switch, so switch = 1

Yeehaw, NSM and B9 do not appear in the query list, I can use any of them without do any other change, I return the current number of switches ;^) Quite simple ;^)

In the big file there was a query list of 999 items Like this:

se = [‘A’, ‘B’]
q = [‘A’, ‘B’,’A’, ‘B’,’A’, ‘B’,’A’, ‘B’,’A’, ‘B’,…]

ok? It did lots of recursion and went over the limit, I had to adjust that :^D

return ‘Bye’

Tagged , ,

§ 3 Responses to GCJ 2008: Saving the Universe"

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>