A faster or more memory efficient solution in Python for this Codejam problem

Question

I tried myself on this Google Codejam Africa (the competition is already over, I just did it to improve my programming skills).

Problem:

You have a party with G guests and note that there is an odd number of guests! When planning a party, you intentionally invited only couples and gave each pair a unique C number for their invitation. You would like to highlight the one who came alone asking all the guests for their invitation numbers.

Input:

The first line of input gives the number of cases N. Next, N test cases follow. For each test case there will be:

• One line containing the value of G, number of guests.
• One line containing a space-separated list of integers G. Each integer C indicates the guest’s invitation code. Output

For each test case, output one line containing "Case No.x:", followed by the guest number C, which is one.

Limits:

• 1 ≤ N ≤ 50
• 0 <C ≤ 2147483647

Small data set

3 ≤ G <100

Large data set

3 ≤ G <1000

Input Example:

3
3
1 2147483647 2147483647
5
3 4 7 4 3
5
2 10 2 10 5

Output result:

Case #1: 1
Case #2: 7
Case #3: 5

This is the solution I came across:

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 starts in 12 seconds on my machine with a lot of input .

Now, to my question, is it possible to improve this solution in Python to work for shorter time or use less memory? analyzing the problem gives some guidance on how to do this in Java and C ++, but I cannot translate these solutions back to Python.

Edit:

Alex Martelli IVlad . , 0.079s:

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)):
        codes = map(int, lines[i+1].split(' '))
        alone = 0
        for c in codes: alone ^= c
        output.write("Case #%d: %d" % (testcase+1, alone))

Answer 1

python, - . 2K - 1, , , , , .

:

• x xor x == 0 for all x
• x xor y == y xor x for all x and y
• x xor (y xor z) == (x xor y) xor z (associativity)
• x xor 0 == x for all x

xor . . , python, C xor ^.

, , .

, : 3 ^ 4 ^ 7 ^ 4 ^ 3 == 7, 2 ^ 10 ^ 2 ^ 10 ^ 5 == 5 ..

Answer 2

, - ( main) 19 . for 0,46 ;

      alone = 0
      for c in codes: alone ^= c

0,08 . , , , 235 , , ; -).

Answer 3

:

codes = map(int, lines[i+1].split(' '))

resplit guest? .

:

for guest in range(G):
    codes = map(int, lines[i+1].split(' '))
    alone = (c for c in codes if codes.count(c)==1)

guest. ?

Answer 4

:

src = open('A-large-practice.in')
dst = open('A-large-practice.out', 'w')

n = int(src.readline().rstrip())
for i in xrange(n):
    src.readline() # skip g
    nums = src.readline().split()
    seen = set()
    for n in nums:
        if n in seen:
            seen.remove(n)
        else:
            seen.add(n)
    dst.write("Case #%d: %s\n" % (i+1, tuple(seen)[0]))

src.close()
dst.close()

, -!

Answer 5

Yes, as the analysis page explains, you can use read-only memory, although any approach will work in O (n) time. Here's how a persistent memory solution will work in Python:

numbers = [1, 1, 2, 2, 3, 3, 4, 4, 12345]
missingOne = 0
for number in numbers:
    missingOne = missingOne ^ number
assert missingOne == 12345

The key understands what the xor operator does. Any number equal to zero is itself. And any number associated with itself is zero. If you look at the xor truth table, you should be able to convince yourself of both of these facts, and then prove that xoring the numbers in the list, starting from zero, will result in a non-duplicated number.