This question already has an answer here:
- Exploring the xorspace 8 answers
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.
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.,
This list represents the above 4 cards.
Output: The number of valid ProSets, which in this example is
- 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.
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.
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.