3
\$\begingroup\$

This question already has an answer here:

ProSet is a classic card game that is played normally with 63 cards. One card has 6 colored dots on it, like below

enter image description here

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.

enter image description here

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 challenge.
  • This is also a 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.

\$\endgroup\$

marked as duplicate by FryAmTheEggman, user2357112, xnor code-golf Aug 24 '18 at 2:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    \$\begingroup\$ Just 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? \$\endgroup\$ – Rod Aug 23 '18 at 16:44
  • 2
    \$\begingroup\$ I 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? \$\endgroup\$ – FryAmTheEggman Aug 23 '18 at 17:03
  • 1
    \$\begingroup\$ Your reference implementation only checks contiguous sublists of the input. \$\endgroup\$ – Nitrodon Aug 23 '18 at 18:21
  • 5
    \$\begingroup\$ More concrete test cases please, preferably considering any edge cases \$\endgroup\$ – Jonathan Allan Aug 23 '18 at 19:22
  • 1
    \$\begingroup\$ To 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 \$\endgroup\$ – Luis Mendo Aug 23 '18 at 20:15
4
\$\begingroup\$

Python 2, 60 bytes

p=[0]
for i in input():p+=[n^i for n in p]
print~-p.count(0)

Try it online!
This generate the powerset from the input (based on this answer), reducing each subset by xor.
The output will be the amount of 0s (0 = all bytes/dots appear an even number of times).
In fact the xoring is done instead of the "powerset appending", but the result is the same

\$\endgroup\$
  • \$\begingroup\$ This is exponential in the number of dots. \$\endgroup\$ – user2357112 Aug 23 '18 at 23:25
  • \$\begingroup\$ @user2357112 no, it's not, it's exponential to the numbers of cards. I've asked some clarifcation to OP when I made this answer, since I don't got an answer, I posted anyway. But it is compliant to the question as it is now. \$\endgroup\$ – Rod Aug 23 '18 at 23:33
  • \$\begingroup\$ I was about to edit (actually, delete and repost) to say "cards". \$\endgroup\$ – user2357112 Aug 23 '18 at 23:37
1
\$\begingroup\$

Japt, 8 bytes

à x@!Xr^

Try it here

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 53 bytes

f=
a=>a.map(i=>p.map(j=>n+=p.push(j^=i)&&!j),p=[n=0])&&n
<input oninput=o.textContent=f(this.value.split`,`)><pre id=o>

Loosely based on @Rod's Python answer.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 8 bytes

ŒPḊ^/€¬S

A monadic Link. 9 bytes if the empty set is considered a ProSet - ŒPḊ^/€¬S‘ (since reducing an empty list errors).

Try it online!

How?

ŒPḊ^/€¬S - Link: list of integers, L
ŒP       - powerset (of cards)
  Ḋ      - dequeue (remove the empty list)
    /€   - reduce €ach with:
   ^     -   XOR
      ¬  - NOT (vectorises)
       S - sum
\$\endgroup\$
0
\$\begingroup\$

Clojure, 182 166 149 127 bytes

(defn f[k]((frequencies(map(fn[x](reduce #(bit-xor % %2)0 x))(reduce(fn[c n](concat(map #(concat %[n])c)[(list n)]c))'()k)))0))

If I had barfed on the screen, it would've looked better than this

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This only seems to check prefixes of the input. \$\endgroup\$ – Nitrodon Aug 23 '18 at 17:50
  • \$\begingroup\$ Ah crap you're right. I'll update it when I have the time \$\endgroup\$ – Lispy Louie Aug 23 '18 at 18:10
  • \$\begingroup\$ Alright, that should do it. \$\endgroup\$ – Lispy Louie Aug 23 '18 at 23:27
  • \$\begingroup\$ This looks exponential time, but I don't know enough Clojure to confirm. The challenge requires a polynomial-time algorithm. \$\endgroup\$ – user2357112 Aug 23 '18 at 23:28
-1
\$\begingroup\$

Python 2, 88 bytes

lambda l:~-sum(x<1for x in f(l))
f=lambda l:l and[n^l[0]for n in f(l[1:])]+f(l[1:])or[0]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ @Downvoters could one of you explain what is wrong with this answer? \$\endgroup\$ – ovs Aug 24 '18 at 16:32

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