Faster or more memory-efficient solution in Python for this Codejam problem.
- by jeroen.vangoey
I tried my hand at this Google Codejam Africa problem (the contest is already finished, I just did it to improve my programming skills).
The Problem:
You are hosting a party with G guests
and notice that there is an odd number
of guests! When planning the party you
deliberately invited only couples and
gave each couple a unique number C on
their invitation. You would like to
single out whoever came alone by
asking all of the guests for their
invitation numbers.
The Input:
The first line of input gives the number of cases, N.
N test cases follow. For each test case there will be:
One line containing the value G the
number of guests.
One line containing
a space-separated list of G integers.
Each integer C indicates the
invitation code of a guest. Output
For each test case, output one line
containing "Case #x: " followed by the
number C of the guest who is alone.
The Limits:
1 = N = 50
0 < C = 2147483647
Small dataset
3 = G < 100
Large dataset
3 = G < 1000
Sample Input:
3
3
1 2147483647 2147483647
5
3 4 7 4 3
5
2 10 2 10 5
Sample Output:
Case #1: 1
Case #2: 7
Case #3: 5
This is the solution that I came up with:
with open('A-large-practice.in') as f:
lines = f.readlines()
with open('A-large-practice.out', 'w') as output:
N = int(lines[0])
for testcase, i in enumerate(range(1,2*N,2)):
G = int(lines[i])
for guest in range(G):
codes = map(int, lines[i+1].split(' '))
alone = (c for c in codes if codes.count(c)==1)
output.write("Case #%d: %d\n" % (testcase+1, alone.next()))
It runs in 12 seconds on my machine with the large input.
Now, my question is, can this solution be improved in Python to run in a shorter time or use less memory? The analysis of the problem gives some pointers on how to do this in Java and C++ but I can't translate those solutions back to Python.
