# Saving the Universe - Code Jam 2008 Qualification problem A

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).

import fileinput

def solve(inFile):
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)
if len(queue) == S:
queue -= queue   #Feels wrong but queue=set(temp) doesn't work
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))

• Maybe queue=set(temp) should be queue = set([temp]). But queue seems like a misleading name since a queue usually stores things in a definite, predictable order, but a set doesn't. – Elias Zamaria Aug 19 '16 at 4:12

• #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__.

• FYI, fixed the PS note, in case of additional answers. Also, thanks for the input, especially the no naked loops part. Question about naming convention though; I was using camelCase, but you seem to use underscores; is that more pythonic? – Adam Martin Aug 19 '16 at 12:37
• Also, using Python 3 raw_input() should be input() right? It doesn't seem to work quite the same. – Adam Martin Aug 19 '16 at 17:09