7
\$\begingroup\$

This code-golf challenge is based on the following puzzle:

You have an odd number of tokens whose weights are known whole numbers, and they don't all have the same weight. Show that there's a token you can remove so that the remaining tokens can't be split into two equal-size sets that have the same total weight.

Here's the canonical solution to the puzzle, which also suggests an algorithm to do it (spoilers if you want to solve the puzzle yourself):

If all the weights are even or all odd, the problem is unchanged if we truncate the least significant bit from each one (i.e. floor-divide by 2). Keep doing that until there's at least one even weight and one odd weight -- this must happen eventually because the total weight decreases at each step. Then, remove a weight whose parity is opposite the parity of the sum, leaving an odd total weight, which clearly prevents an even split.

Your goal is to figure out such a weight to remove. Shortest code wins.

Input:

An odd-size list of positive whole numbers, not all the same. Any list-like structure is fine, though it has to work with the numbers in any order.

Output:

One of those numbers, such that the remaining numbers can't be partitioned into two sets with equal size and equal sum. You must output the number, not its index.

If there's multiple choices, any one of them is fine. It doesn't have to be the number chosen by the solution above.

Your code should be able to handle test cases like below within one second.

Test cases:

[1, 2, 3]
1

[3, 3, 3, 3, 3, 3, 5]
3

[1, 2, 3, 4, 5, 6, 7, 8, 9]
2

[1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
1

[128, 256, 256]
256

[18770, 10578, 7506, 5458, 4434, 6482, 5458, 4434, 2386, 11602, 1362, 16722, 11602, 23890, 12626, 47442, 57682, 35154, 57682, 81234, 44370, 12626, 12626, 46418, 68946, 91474, 2386, 43346, 46418, 35154, 32082]
7506

If you want to see all possible outputs (this is just to show, your code must output exactly one):

[1, 2, 3]
{1, 2, 3}

[3, 3, 3, 3, 3, 3, 5]
{3}

[1, 2, 3, 4, 5, 6, 7, 8, 9]
{2, 4, 6, 8}

[1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
{1}

[128, 256, 256]
{256}

[18770, 10578, 7506, 5458, 4434, 6482, 5458, 4434, 2386, 11602, 1362, 16722, 11602, 23890, 12626, 47442, 57682, 35154, 57682, 81234, 44370, 12626, 12626, 46418, 68946, 91474, 2386, 43346, 46418, 35154, 32082]
{68946, 5458, 44370, 46418, 11602, 23890, 7506, 91474, 32082, 1362, 81234}
\$\endgroup\$
  • \$\begingroup\$ Its my personal opinion that with the time limitation here (and here) answers are mostly forced to use the same algorithm. So its just the matter of language . \$\endgroup\$ – Optimizer Jan 24 '15 at 9:25
  • \$\begingroup\$ "[Truncating] the least significant bit" is the same as floor division by 2, right? \$\endgroup\$ – KSFT Jan 24 '15 at 18:40
  • \$\begingroup\$ @KSFT Yes, it's the same as floor-dividing by 2. \$\endgroup\$ – xnor Jan 24 '15 at 22:59
2
\$\begingroup\$

CJam, 19 17

q~:T{T:^^2bW%}$W=

Input format:

[1 2 3 4 5 6 7 8 9]

2 bytes thanks to Optimizer.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ q~:Q{Q:^^2bW%}$W= 17 \$\endgroup\$ – Optimizer Jan 24 '15 at 8:50
1
\$\begingroup\$

Python 2, 99

This came out pretty badly.

s=input()
b=1
while{x&b for x in s}<{0,b}:b+=b
print[x for x in s if(reduce(int.__xor__,s)^x)&b][0]

Numbers may be input comma-delimited.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ I think it's shorter as a lambda f=lambda L,d=1:{0}<{x&d for x in L}and[x for x in L if(x^reduce(int.__xor__,L))&d][0]or f(L,2*d) \$\endgroup\$ – Sp3000 Jan 25 '15 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.