3
1
ProSet is a classic card game that is played normally with 63 cards. One card has 6 colored dots on it, like below
The rest of the cards are missing some of these 6 dots, but each card has at least 1 dot. Every card in the deck is different. Below are some example valid cards.
A ProSet is a nonempty set of cards such that the total number of each color of dot is even. For example, the above set of 4 cards are a ProSet since there are 2 reds, 4 oranges, 2 greens, 2 blues, 0 yellows, and 2 purples.
Interestingly, any set of 7 cards will contain at least 1 ProSet. Hence, in the actual card game, a set of 7 cards are presented, and the player who finds a ProSet first wins. You can try the game out for yourself here.
Challenge
Given a set of cards, each ProSet card can be assigned a value from 1 to 63 in the following manner: a red dot is worth 1 point, an orange 2 points, yellow 4, green 8, blue 16, purple 32. The sum of the values of each dot on the card is the value of the card.
Input: A list of integers from 1-63, i.e.,
[11,26,35,50]
This list represents the above 4 cards.
Output: The number of valid ProSets, which in this example is 1
.
Rules
- This is a code-golf challenge.
- This is also a restricted-complexity challenge, as all valid solutions must be in polynomial time or less in the number of dots (in this case 6) and in the number of cards.
Test Cases
I've created an exponential algorithm to find the correct output for every input here. Again, exponential solutions are not valid submissions. But, you can use this to validate your findings.
Edit
I will address the comments in a bit. But for now, none of the answers have been in polynomial time. It is indeed possible, so here's a hint: binary representation and two s complement.
Moreover, I made a mistake earlier when I said polynomial in solely dots. It needs to be polynomial in dots and cards.
1Just another detail, the complexity is based in the number of dots, but what about the number of cards? can it be exponential to the number of cards? – Rod – 2018-08-23T16:44:32.800
2I don't think complexity in the number of dots makes any sense since the number of dots is fixed in this problem? Wouldn't the naive solution (like Rod suggested) be exponential in the number of cards but linear in the number of dots? – FryAmTheEggman – 2018-08-23T17:03:59.703
1Your reference implementation only checks contiguous sublists of the input. – Nitrodon – 2018-08-23T18:21:13.527
5More concrete test cases please, preferably considering any edge cases – Jonathan Allan – 2018-08-23T19:22:28.127
1To me, the complexity restriction spoils the challenge a little. Just code golf would have been more fun. Also, it may not be obvious if the restriction is being met by an answer or not; answer writers should explain – Luis Mendo – 2018-08-23T20:15:44.627
1"A ProSet is a set of cards such that the total number of each color of dot is even" - the empty set is a set. As such the example output should be 2. – Jonathan Allan – 2018-08-23T20:17:38.850
@JonathanAllen not including empty set – Don Thousand – 2018-08-23T23:05:26.603
1Out of the 6 existing answers, I don't think a single one is polynomial time. You may want to emphasize that requirement more. – user2357112 supports Monica – 2018-08-23T23:27:02.477
Exploring the xorspace is closely related, possibly a duplicate. The number of prosets equals 2^(# elts) / (size of xorspace) - 1. I expect the polynomial-time restriction restriction to be effectively the same as finishing the xorspace test cases within a day. – xnor – 2018-08-24T02:21:55.097
@RushabhMehta No need to apologize, unexpected duplicates are common around here and I've had my share, especially with many different possibilities for terminology that can be used to phrase challenge. – xnor – 2018-08-24T03:01:22.310
@user2357112 "All current answers seem to be exponential in the number of input cards, which is worse, though" no, there is no given relationship between the number of dot-colours (the number of "dots" is said to be 6 in the example) and number of cards. All the "get the powerset of cards" solutions below, while exponential in the number of cards, are, strictly speaking, only linear in the dot-colour count (since keeping the number of cards fixed and varying the dot-colour count we can see a linear relationship). – Jonathan Allan – 2018-08-24T10:18:59.070