Saving the Universe - Code Jam 2008 Qualification problem A

Question

I'm trying to brush up on my Python, so I'm going through some simple problems. Big concerns are style, though any algorithmic problems I'm open to suggestions on.

Basically you have an input file where the first line is the number of test cases.

The following lines are composed of the cases. Each case starts with a number S followed by S unique lines representing search engines. Then there is a number Q followed by Q lines representing queries. Each query is the name of a search engine. You have to run the queries in sequence, but you can batch them up; however you cannot run a query on the corresponding search engine. The program should return the minimum number of switches between engines required. I know that the result is correct (passes the tests on the site), so again focus is mainly style (not just PEP, but also pythonic-ness so to speak).

Source: Problem A. Saving the Universe

import fileinput

def solve(inFile):
    #discard list of possible values
    S = int(next(inFile))
    for i in range(0,S): #Feels wrong doing this one at a time
        next(inFile)

    count = 0
    Q = int(next(inFile))
    queue = set()
    #iterate over queries, adding each one to a set until the set contains all
    #S possible queries. Then increment count and reset set to only include
    #the newest query since we had to have cleared the queue before it arrived
    while Q > 0 :
        Q -= 1
        temp = next(inFile)
        queue.add(temp)
        if len(queue) == S:
            queue -= queue   #Feels wrong but queue=set(temp) doesn't work
            queue.add(temp)
            count += 1
    return count

if __name__ == "__main__":
    inFile = fileinput.input()
    T = int(next(inFile))
    for i in range(1,T+1):
        print("Case #", end="") #Feels wrong having four prints
        print(i, end="")
        print(": ", end="")
        print(solve(inFile))

Answer 1

• #Feels wrong having four prints

  Indeed.

      print "Case %d: %d" % (i, solve(inFile))
  

  is good enough.

• #Feels wrong but queue=set(temp) doesn't work

  Yes. The set constructor requires an iterable. Consider queue = set([temp]).

• #Feels wrong doing this one at a time

  I don't think you can do anything about this. As a side note, what really feels wrong is that these parts of the test cases are totally irrelevant to the solution; only the number of engines really matter. Kudos for realizing this.

  As usual, a no naked loops principle dictates to factor this loop out into a function:

      def discard_names_as_useless(inFile, S):
  

• Naming

  Q and S only make sense for those who read the problem statement. Consider instead something like number_of_queries and number_of_engines.

• import fileinput

  Using fileinput seems like an overkill. It is only useful if you need to process multiple files in a row. In this case an unadorned raw_input() would work just fine.

• PS

  Be careful describing the problem statement. Your description

  The program should return the minimum number of batches required.

  raised an immediate red flag: this code must be off-by-one. I had to read the original to realize that they ask for the number of _engine switches__.