26
\$\begingroup\$

Background

Set is a card game. The deck consists of 81 unique cards that vary in four features: number of shapes (one, two, or three), shape (diamond, squiggle, oval), shading (solid, striped, or open), and color (red, green, or purple).

For convenience, let's write a card as a 4-tuple of numbers from 1 to 3, e.g.

  • 1111 = one red solid diamond
  • 1122 = one red striped squiggle
  • 1223 = one green striped oval
  • 2312 = two purple solid squiggle

Given several cards (usually 12), the objective of the game is to find a "set" of three cards such that

  • They all have the same number or have three different numbers.
  • They all have the same shape or have three different shapes.
  • They all have the same shading or have three different shadings.
  • They all have the same color or have three different colors.

i.e. the cards are either all the same or all different in each of the four features.

Here are some examples of sets:

1111, 1112, 1113
1111, 2222, 3333
2312, 3321, 1333

Here are some examples of non-sets:

1111, 1122, 1123
2131, 3221, 1213

A cap set is a collection of cards that doesn't contain any Set. It was proven in 1971 that the maximum number of cards without a Set is 20. Interestingly, finding the largest cap set for the generalized game of Set is still an open problem in mathematics.

The Wikipedia page shows an example of 20-cap set, and here is the 20 cards in the number notation:

1111, 1113, 1131, 1133,
1312, 1332, 1321, 1323,
3311, 3313, 3331, 3333,
3112, 3132, 3121, 3123,
1222, 2122, 2322, 3222

There are 682344 20-cap sets in total, but under affine transformations on 4-dimensional finite space, they all reduce to essentially one cap set.

Task

Output any of the 20-cap sets in the game of Set.

Input and output

Your program/function is not allowed to take input.

The output is a collection (list, set, ...) of 20 cards which is a cap set. Each card should be represented as a 4-tuple (or equivalent ordered collection) whose elements are one of three distinct values (not necessarily 1, 2, 3). Flexible output applies in the following ways:

  • Nested or flattened list
  • Ordering of cards doesn't matter
  • You may choose to output the same set or different set across runs
  • For string/text output, it's fine as long as we can clearly identify the structure (20 chunks of four items) of the output

Verification script example in Python using the example shown above.

Scoring and winning criterion

Standard rules apply. The shortest valid code in bytes wins.

\$\endgroup\$
  • 3
    \$\begingroup\$ @Arnauld Neither. You can choose to output the same set or different set across runs. \$\endgroup\$ – Bubbler Nov 11 at 9:16
  • 6
    \$\begingroup\$ For anyone that wants to make use of it, we can specify a cap set as all (a,b,c,d) from {0,1,2}^4 with a*a+b*b+c*d=0 (mod 3) except for (0,0,0,0). \$\endgroup\$ – xnor Nov 11 at 9:35
  • 4
    \$\begingroup\$ So I understand, would this count as a boring brute force solution? And so then the game becomes either "find a formula like xor's for generating one of these" or, perhaps, search the entire space of all of them for one that can be compactly represented with some packing function? If the latter, would a kolmogorov-complexity tag be in order? \$\endgroup\$ – Jonah Nov 11 at 16:45
  • \$\begingroup\$ I'm with Jonah. The task does not require computing, just compressing. \$\endgroup\$ – Mindwin Nov 11 at 18:33
  • 4
    \$\begingroup\$ @Jonah Yes, that is a valid solution, though it's arguably a boring one. And yes, it's a compression challenge. No, I don't think it's kolmogorov-complexity, since you can choose from 682344 * 20! / (some constant) possible outputs. Also, I can think of at least three approaches to this problem: 1) compress a cleverly chosen cap set 2) enumerate all 20-card sets and pick one that is a cap set 3) use math formula. \$\endgroup\$ – Bubbler Nov 11 at 23:20

11 Answers 11

25
\$\begingroup\$

Haskell, 62 bytes

tail[t|t@[a,b,c,d]<-mapM(:[1,2])[0,0,0,0],mod(a*a+b*b+c*d)3<1]

Try it online!

Defines a cap-set as all \$(a,b,c,d)\$ from \$\{0,1,2\}^4\$ where $$a^2+b^2+cd=0\bmod3,$$ except not \$(0,0,0,0)\$.

I found this formula by looking at Wikipedia's example and coming up with progressively simpler formulas linking the allowed inner coordinates \$(a,b)\$ to the outer coordinates \$(c,d)\$.


Haskell, 46 bytes

[t|t<-mapM(:"12")"0000",sum[1|'0'<-t!!0:t]==2]

Try it online!

This uses a modified condition giving a different but equivalent cap set:

$$a^2+b^2+c^2 - d^2=0\bmod3,$$ still without \$(0,0,0,0)\$.

This is equivalent to \$a^2+b^2+c^2 + d^2 + d^2 =0\bmod3,\$, so we can duplicate an element and check that the give-element list of squares adds to zero modulo 3. Since squares modulo 3 are 0 or 1, this is further equivalent to this condition:

There are exactly \$2\$ zeroes among \$[a,b,c,d,d]\$.

This automatically excludes the all-zero point. Of course, duplicating $d$ was arbitrary -- choosing another element gives a different but equivalent cap-set.

\$\endgroup\$
  • \$\begingroup\$ +1 for ruining 1/3 of the fun. \$\endgroup\$ – Bubbler Nov 11 at 10:15
  • \$\begingroup\$ @Bubbler Did you know about this polynomial? I'm curious why it works and, from what you say in the challenge, gives a unique solution up to symmetries. flawr and I are discussing it in Primes and Squares. \$\endgroup\$ – xnor Nov 14 at 2:54
  • 1
    \$\begingroup\$ Nah. I tried to read the proof in the linked paper, but to no avail. And for the "unique solution up to symmetries", I just ripped off that part from the Wikipedia page. \$\endgroup\$ – Bubbler Nov 14 at 3:15
8
\$\begingroup\$

05AB1E, 16 13 11 9 bytes

2Ý4ãʒĆ0¢<

Port of the found formula of @xnor, as mentioned in his comment as well as his Haskell answer, so make sure to upvote him!
-2 bytes by using @xnor's updated formula (thanks for letting me know).
-2 bytes thanks to @xnor again by simply counting whether there are exactly 2 zeroes in \$[a,b,c,d,a]\$.

Also outputs a list of lists with values in the range \$[0,3]\$.

Try it online.

Explanation:

Will leave quartets \$[a,b,c,d]\$ for which there are exactly 2 zeroes in the list \$[a,b,c,d,a]\$.

2Ý         # Push the list [0,1,2]
  4ã       # Create all possible quartets using the values in this list
           # by taking the cartesian power of 4
    ʒ      # Filter the remaining quartets by:
     Ć     #  Enclose the quartet; appending its own head: [a,b,c,d] → [a,b,c,d,a]
      0¢   #  Count the amount of 0s in this list
        <  #  And decrease it by one
           #  (Since only 1 is truthy in 05AB1E, the filter with count(0)-1 will only
           #   leave quartets where the [a,b,c,d,a].count(0) is exactly 2)
           # (after which the filtered list is output implicitly as result)
\$\endgroup\$
  • 1
    \$\begingroup\$ This beats the simple compression-based approach, though not by much. A shame that handling leading zeroes costs so much. \$\endgroup\$ – Grimmy Nov 12 at 15:18
  • 1
    \$\begingroup\$ @Grimmy Still a nice approach. Also, can something be saved by using the digits 1234 instead of 0123, so you won't have to deal with the leading 0s? I guess the extra bytes are then still there, but at other places instead? \$\endgroup\$ – Kevin Cruijssen Nov 12 at 15:32
  • 1
    \$\begingroup\$ Good idea, but it ends up worse by two bytes, unfortunately. \$\endgroup\$ – Grimmy Nov 12 at 15:52
  • 1
    \$\begingroup\$ I realized the formula a^2 + b^2 + c^2 - d^2 = 0 mod 3 also works. Maybe this would be shorter for your implementation via negating or duplicating top of element the stack before summing. \$\endgroup\$ – xnor Nov 16 at 7:49
  • 1
    \$\begingroup\$ Another formulation is that the list [a,b,c,d,a] has exactly two zeroes. Since you have a built-in to make that list, might that be yet shorter? \$\endgroup\$ – xnor Nov 16 at 11:23
7
\$\begingroup\$

JavaScript (ES6),  73  67 bytes

_=>[...'11138272726454626454'].map(i=>3333-(t-=i).toString(3),t=80)

Try it online!

Outputs the following set, as an array of integers:

1112, 1113, 1121, 1131, 1223, 1232, 1323, 1332, 2123, 2132,
2222, 2233, 2322, 2333, 3123, 3132, 3222, 3233, 3322, 3333

Test it online!

\$\endgroup\$
5
\$\begingroup\$

Perl 6, 46 36 bytes

{grep *[0,^*].Bag{0}==2,[X] ^3 xx 4}

Try it online!

Uses xnor's updated formula.

Explanation:

{                                  }  # Anonymous code block
 grep                                 # Filter from
                       ,[X]             # The cross product of
                            ^3 xx 4     # 0,1,2 four times
      *[0,^*]                         # Duplicating the first element
             .Bag{0}                  # Where the number of zeroes
                    ==2               # Is equal to 2

\$\endgroup\$
4
\$\begingroup\$

Ruby, 78..52 49 bytes

"U ".bytes{|r|p ($.+=r).to_s 4}

Try it online!

How

The sequence can be DPCM-encoded.

If we consider a card as a single base-4 integer (1111 through 3333), we can take any sequence, sort it, and use a single ASCII character to encode the difference between successive elements. The first character represents the first value of the sequence. All values are relatively small, and the decoding is still simple enough to be golfed.

Thanks Value Ink for -3 bytes ("to print the unprintable")

In theory, with a different encoding, every value can be encoded as a single byte, and this would bring the byte count down to 43, but with UTF-8 it's impossible (or at least, I can't figure it out).

\$\endgroup\$
  • \$\begingroup\$ Can't you just encode the string as unprintables to cut out the -34? 49 bytes \$\endgroup\$ – Value Ink Nov 11 at 22:24
  • \$\begingroup\$ Yes. In that case I could encode the values directly instead of the differences. 3333 base 4 is 255. \$\endgroup\$ – G B Nov 12 at 4:27
  • \$\begingroup\$ Yes that is probably a good idea. \$\endgroup\$ – Value Ink Nov 12 at 4:41
2
\$\begingroup\$

Python 2, 85 bytes

print eval('[[a,b,c,d]'+'for %s in 0,1,2'*4%tuple('abcd')+'if(a*a+b*b+c*d)%3<1]')[1:]

A full program which performs xnor's algorithm.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ That's a nifty way to write the multiple for loops. \$\endgroup\$ – xnor Nov 13 at 2:07
2
\$\begingroup\$

Python 2, 62 bytes

for c in"P}nF-Z>a9*)V=.Q":n=ord(c);print n/50,n%3,n%4,n%5

Try it online!

Using ideas from Bubbler and Jo King, we can cut a few bytes from the below. The decompression method n/50,n%3,n%4,n%5 turns an ASCII value into a 4-tuple. While not every set can be obtained this way using n from 0 to 127, there's enough wiggle room in the choice of cap-set to find one within the obtainable subset. We also avoid problematic characters that need escaping such as \0 or \n, though unprintables can't be avoided.


Python 2, 65 bytes

for c in'RSTW_ahjq"(,15;=CGLP':print[ord(c)/B%3for B in 27,9,3,1]

Try it online!

String compression looks like the way to go for Python. We compress each of the 20 elements as a value from 0 to 80, which we represent as a character. Since we only need the values to be correct modulo 81, we can keep the string within the printable ASCII range. Python 3 could save a few bytes using a bytestring.

An alternative compression method would be 81 bits marking which of the 81 cards are present. Even though the 81 bits needed for this are less than the \$20 \log_2(81)\approx 127\$ bits for the method used, the latter wins out easily for how concisely the string can be written and decoded.

For comparison, here's a solution using the formula I found.

79 bytes

n=81
while n:
 t=a,b,c,d=n/27,n/9%3,n/3%3,n%3;n-=1
 if(a*a+b*b+c*d)%3<1:print t

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I found a string that works with for B in 1,3,7,9, so 64 bytes. Btw, the "wins out easily" link seems to be broken. \$\endgroup\$ – Bubbler Nov 13 at 2:12
  • \$\begingroup\$ In Python 3, you can skip the ord part with a bytestring for 57 bytes \$\endgroup\$ – Jo King Nov 13 at 3:49
2
\$\begingroup\$

Jelly,  13  11 bytes

-2 using more of xnor's ideas

3ṗ4ṁ5ỊS⁼ʋƇ2

A niladic Link which yields a list of lists of integers.

Try it online!

How?

Cards being [a, b, c, d] where \$a,b,c,d \in [1,3]\$ this method picks cards for which there are exactly two 1s in [a, b, c, d, a].

3ṗ4ṁ5ỊS⁼ʋƇ2 - Link: no arguments
3           - literal three
  4         - literal four
 ṗ          - (implicit range(x)) Cartesian power -> [[1,1,1,1],[1,1,1,2],...,[3,3,3,3]]
          2 - set the right argument to two
         Ƈ  - filter keep if:
        ʋ   -   last four links as a dyad:
   ṁ5       -     mould like 5 ([a,b,c,d] -> [a,b,c,d,a])
     Ị      -     insignificant? (abs(x)<=1) (vectorises)
      S     -     sum
       ⁼    -     equals (2)?

Previous

3ṗ4Ṗ2œ?ḋƊ3ḍƊƇ

A niladic Link which yields a list of lists of integers.

Try it online!

How?

A method which works in a similar vein as xnor's.
With cards being [a, b, c, d] where \$a,b,c,d \in [1,3]\$ this method picks cards for which \$3 \mid (a^2+b^2+2cd)\$ (except [3,3,3,3])

3ṗ4Ṗ2œ?ḋƊ3ḍƊƇ - Link: no arguments
3             - literal three
  4           - literal four
 ṗ            - (implicit range(x)) Cartesian power -> [[1,1,1,1],[1,1,1,2],...,[3,3,3,3]]
   Ṗ          - pop off the rightmost (remove [3,3,3,3])
            Ƈ - filter keep those for which:
           Ɗ  -   last three links as a monad:- i.e. f([a,b,c,d])
        Ɗ     -     last three links as a monad - i.e. g([a,b,c,d]):
    2         -       literal two                 2
     œ?       -       nth permutation             [a,b,d,c]
       ḋ      -       dot product                 a*a+b*b+c*d+d*c
         3    -     literal three               3
          ḍ   -     divides?                    (a*a+b*b+c*d+d*c)%3 == 0?
\$\endgroup\$
  • \$\begingroup\$ I realized the formula a^2 + b^2 + c^2 - d^2 = 0 mod 3 also works, in case this is shorter for you to write that the dot product with permutation. You can also write this with duplicating a square rather than negating it: a^2 + b^2 + c^2 + d^2 + d^2 = 0 mod 3. \$\endgroup\$ – xnor Nov 16 at 7:52
  • \$\begingroup\$ Using the fact that squares are 0 or 1 mod 3 that saves at least a byte... think 11 is probably possible; hard on mobile! \$\endgroup\$ – Jonathan Allan Nov 16 at 10:50
  • \$\begingroup\$ Yep 11 was possible - thanks! \$\endgroup\$ – Jonathan Allan Nov 16 at 10:57
1
\$\begingroup\$

Charcoal, 24 bytes

UB0E²⁰⮌⍘Σ…”)″&:igK⁶Mψ”ι³

Try it online! Link is to verbose version of code. Outputs the given set, but with digits decremented and sorted in order of reverse of string. Explanation:

UB0

Pad all lines to the same length using 0.

E²⁰

Loop i from 0 to 19 and implicitly print each result on its own line.

⮌⍘Σ…”)″&:igK⁶Mψ”ι³

Convert the digital sum of the ith prefix of the compressed string 8343834422244383438 to base 3 and print it backwards.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 108 104 100 bytes

Saved 4 bytes thanks to @JonathanAllan!
Saved 4 bytes thanks to @xnor!

Blatant rip of @xnor's algorithm:

lambda:[(a,b,c,d)for a,b,c,d in product(*[(0,1,2)]*4)if(a*a+b*b+c*d)%3<1][1:]
from itertools import*

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Some single byte saves: (1) use (the generally bad)from itertools import* avoiding the t.; (2) use (0,1,2) rather than range(3); (3) unpack i immediately, allowing i[0]**2+i[1]**2+i[2]*i[3] to become a*a+b*b+c*d; (4) test for ...%3<1 rather than ...%3==0. Try it online! \$\endgroup\$ – Jonathan Allan Nov 12 at 19:11
  • 1
    \$\begingroup\$ @JonathanAllan Thanks, really interesting how you can squeeze those bytes out of, what looks like to me, a stone! :) \$\endgroup\$ – Noodle9 Nov 12 at 21:48
  • 1
    \$\begingroup\$ You can also save a few bytes using product(*[(0,1,2)]*4). But almost always, you're better off not using itertools and finding way to do it manually that saves bytes over the lengthy import. \$\endgroup\$ – xnor Nov 13 at 1:46
  • \$\begingroup\$ @xnor Thanks! That makes a lot of sense. \$\endgroup\$ – Noodle9 Nov 13 at 10:50
0
\$\begingroup\$

Scala, 68 bytes

BigInt("3aglhdjjb0zmp3uvkpxvwio58",36).toString(3).grouped(4).toList

Try it online!

Just storing the 20-cap set as a 80-digit base-3 number (using 0, 1, 2 for notation - since it's stated in the question that it's not necessary to use exactly 1, 2, 3), constructing it from base-36 to save space, and splitting the string to 4-character slices, finally getting a list of 20 cards (represented as strings like "1111", "0222" etc.). A couple more bytes probably can be golfed, using a smaller number.

\$\endgroup\$

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.