Faster or more memory-efficient solution in Python for this Codejam problem.

Posted by jeroen.vangoey on Stack Overflow See other posts from Stack Overflow or by jeroen.vangoey
Published on 2010-03-27T14:59:17Z Indexed on 2010/03/27 15:03 UTC
Read the original article Hit count: 183

Filed under:
|
|
|

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.

© Stack Overflow or respective owner

Related posts about python

Related posts about code-challenge