20 cards with no Set

Question

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 code-golf rules apply. The shortest valid code in bytes wins.

Answer 1

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.

Answer 2

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)

Answer 3

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!

Answer 4

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

Answer 5

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).

Answer 6

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?

Answer 7

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!

Answer 8

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!

Answer 9

Charcoal, 24 bytes

ＵＢ0Ｅ²⁰⮌⍘Σ…”)″&:igＫ⁶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:

ＵＢ0

Pad all lines to the same length using 0.

Ｅ²⁰

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

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

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

Answer 10

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!

Answer 11

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.