Yes, the result will be very "ugly", but it will also be very fast (at runtime - if you want fast coding time, just adapt your solution to 562).
I haven't had time to code up my solution, it's all in my head!
I can give you a few pointers though. If you have more questions or want to see my solution (I'll finish it this weekend sometime) then please send me a private message. (Since this is suppose to be a discussion about 562).
1) Consider the parity of the number of marbles of each type. The reasoning is that the even "part" can easily be split into two sets of equal value. This leaves 64 cases (2^6), 32 of which have an odd total value and the result is false for these.
2) Store the parities using the bits of a integer, parities.
- Code: Select all
parities & 0x01 // parity of number of marbles of value 1
parities & 0x02 // parity for value 2
parities & 0x04 // parity for value 3
This will make the code more concise and simpler.
3) Some of the solutions, say odd parities for only 3, 2, 1, have trivial solutions that split evenly, namely 3 and 2 + 1 = 3 in this example. Of the 32 remaining cases, 18 (or so) fall into this category.
4) We can be smart and rather than have 18 if clauses, we can simplify (same idea as Karnaugh maps). i.e. Of the 32 cases with even totals, all with both 3 and 2 having odd parities fall in the category mentioned above. So with one check (parities & 0x06) we can handle 8 cases at once!
5) That leaves 14 cases...these are the difficult ones...I need to give more thought into a simple, reusable method. With your example above, only 2 has an odd parity. We have currently assigned one 2 and one 3 to each person and have one 3 left. We can swap person A's 2 with person B's 3 for a change of in values of 1 to each person. A is +1 and B is -1 for a total value difference of 2 (which is the value of the unassigned marble). The remaining 2 gets assigned to B and the values are equal and all the marbles are assigned! To describe this more generally, consider x := <half the total of the unassigned marbles>. We need to find a set of marbles assigned to person A and a set assigned to person B whose difference is x. If such sets exist then the result is true, otherwise the result is false. This isn't too hard to code up, but it might be a bit "ugly".