14
\$\begingroup\$

This is similar in concept to this challenge, but that is pretty restrictive on input and output and I think opening up these restrictions would lead to a completely different set of solutions that would be interesting in their own right.


Background

Set is a card game in which players compete to construct sets of three cards from a collection based on certain rules. Each card has four attributes: number, shape, color, and pattern. For a set to be valid, the cards must all either match or differ in each of the attributes.

For example, three cards being 1 empty green diamond, 1 shaded red diamond, and 1 filled purple diamond would constitute a Set. An example of a non-set is 1 empty green diamond, 2 shaded red diamonds, and 3 filled green diamonds. This is not a valid Set because while the numbers are different, patterns different, and shape the same, two of them share a color that the third does not.

The Challenge

Your job is to write a function that takes a list of twelve cards as a parameter and outputs the number of valid Sets. The cards must consist of a collection of four values, each representing an attribute on the card. Each attribute may have its own set of values to represent the different states, but there are only three states, and your choice of representation must be consistent across cards and inputs. This is Code Golf, so the shortest solution wins.

Test Cases

In my test cases, cards are represented by a 4-tuple with each attribute being encoded by a number 0-2. The first column is the expected output, and the second column is the input.

0  | (0, 2, 1, 1), (0, 0, 0, 2), (0, 1, 0, 0), (1, 2, 1, 0), (1, 1, 2, 2), (0, 1, 2, 1), (0, 1, 1, 0), (1, 0, 2, 0), (1, 1, 0, 1), (2, 2, 0, 1), (1, 0, 2, 1), (2, 1, 1, 2)
1  | (0, 2, 0, 2), (0, 2, 0, 0), (2, 2, 2, 1), (2, 0, 0, 0), (1, 0, 2, 2), (2, 1, 2, 2), (0, 1, 2, 1), (2, 0, 1, 1), (1, 0, 1, 1), (1, 2, 2, 1), (0, 1, 2, 2), (2, 1, 0, 2)
2  | (2, 0, 1, 0), (1, 0, 1, 1), (0, 1, 0, 0), (2, 0, 1, 2), (2, 0, 0, 1), (2, 2, 2, 0), (0, 1, 2, 2), (1, 1, 0, 0), (0, 2, 2, 2), (1, 1, 1, 1), (0, 1, 0, 2), (0, 1, 0, 1)
3  | (2, 1, 0, 2), (1, 0, 2, 1), (2, 2, 1, 1), (2, 0, 1, 2), (1, 2, 1, 1), (1, 2, 2, 2), (0, 0, 1, 2), (0, 0, 2, 1), (2, 0, 0, 0), (2, 1, 2, 0), (0, 2, 2, 0), (0, 0, 1, 0)
4  | (1, 0, 1, 0), (2, 2, 0, 1), (2, 0, 1, 2), (0, 0, 2, 1), (1, 2, 0, 1), (2, 2, 1, 0), (2, 0, 2, 1), (1, 1, 0, 2), (2, 1, 0, 2), (0, 1, 2, 2), (1, 2, 2, 0), (1, 0, 1, 2)
5  | (2, 2, 1, 0), (1, 2, 1, 0), (2, 0, 0, 0), (0, 0, 1, 2), (0, 0, 0, 2), (0, 1, 2, 0), (0, 2, 0, 1), (2, 2, 2, 0), (1, 2, 1, 2), (0, 1, 1, 0), (2, 0, 1, 0), (2, 1, 2, 1)
6  | (2, 1, 1, 0), (0, 1, 0, 1), (1, 1, 0, 2), (0, 0, 2, 2), (1, 0, 2, 0), (2, 1, 0, 0), (2, 2, 2, 2), (2, 0, 1, 1), (1, 0, 2, 1), (2, 2, 0, 1), (2, 2, 1, 2), (0, 1, 0, 0)
7  | (1, 0, 1, 0), (1, 1, 0, 0), (2, 1, 2, 0), (2, 0, 1, 1), (0, 0, 2, 0), (0, 2, 1, 1), (0, 1, 1, 0), (0, 0, 1, 2), (1, 0, 0, 2), (0, 2, 2, 1), (1, 0, 2, 2), (0, 0, 0, 1)
8  | (1, 2, 0, 1), (2, 2, 2, 1), (1, 2, 2, 0), (0, 1, 2, 2), (1, 1, 0, 1), (0, 0, 1, 1), (0, 2, 2, 0), (2, 0, 2, 1), (2, 1, 0, 2), (0, 1, 0, 0), (1, 2, 1, 2), (2, 0, 0, 2)
9  | (0, 2, 2, 1), (0, 1, 0, 0), (2, 1, 1, 0), (2, 0, 1, 0), (2, 0, 0, 2), (2, 1, 2, 1), (2, 2, 1, 0), (0, 2, 1, 1), (1, 2, 0, 2), (0, 0, 1, 0), (0, 1, 0, 2), (1, 1, 1, 0)
10 | (0, 1, 2, 0), (1, 1, 2, 0), (1, 0, 1, 2), (2, 0, 2, 0), (1, 1, 1, 2), (1, 2, 1, 2), (0, 2, 2, 0), (1, 1, 0, 1), (2, 0, 0, 1), (2, 1, 0, 1), (0, 0, 0, 1), (2, 2, 1, 2)
\$\endgroup\$
2
  • \$\begingroup\$ May I take the list of cards transposed (so it's a 4-tuple of length-12 lists of individual attribute values)? \$\endgroup\$
    – Bubbler
    Jul 27, 2021 at 5:04
  • 1
    \$\begingroup\$ @Bubbler No, the input must be a collection of 12 elements, with each element representing a card \$\endgroup\$ Jul 27, 2021 at 5:44

12 Answers 12

11
\$\begingroup\$

Jelly, 10 bytes

œc3S€3ḍẠ€S

Try it online!

How it works

œc3S€3ḍẠ€S    Main link. Input: a list of 4-tuples of 0,1,2
œc3           3-card combinations
   S€3ḍẠ€     For each combination,
   S€         Sum all the cards' values for each attribute
     3ḍ       Test if each sum is divisible by 3
       Ạ€     Test if all of them are true
         S    Sum the boolean array (count the valid Sets)

Jelly, 10 bytes

Zœc€3§3ḍPS

Try it online!

Alternative solution, which can make a 9 by omitting the leading Z if taking the input transposed is allowed.

\$\endgroup\$
6
\$\begingroup\$

K (ngn/k), 27 25 bytes

{-2+-6!+/*/~+3!+/x@!3#12}

Try it online!

-2 bytes thanks to @ngn

K doesn't have a built-in for combinations. This code uses simple Cartesian 3rd power instead. If you count the number of sets the same way, you get 12 plus 6 times the desired answer (for 12 self-triples and 6 different permutations for each valid Set). Then just divide by 6 and subtract 2.

\$\endgroup\$
4
  • \$\begingroup\$ "If you count the number of sets the same way, you get 12 plus 6 times the desired answer" -- Very nice observation. Is the final sentence supposed to read "and subtract 12"? \$\endgroup\$
    – Jonah
    Jul 27, 2021 at 3:59
  • 1
    \$\begingroup\$ @Jonah The excess 12 is also divided by 6, leaving a +2. \$\endgroup\$
    – Bubbler
    Jul 27, 2021 at 4:04
  • \$\begingroup\$ Ah right. I was checking if this approach could shorten my J solution but doing the cartesian product seems to be a lot bulkier... \$\endgroup\$
    – Jonah
    Jul 27, 2021 at 4:18
  • \$\begingroup\$ 0= -> ~ and x[!3#12] -> x@!3#12 \$\endgroup\$
    – ngn
    Jul 30, 2021 at 5:20
6
+50
\$\begingroup\$

ARM T32 machine code, 48 bytes

b570 0084 2000 e00f 590a 594b 18d2 598b
18d2 230b 435a f012 3f0c bf08 3001 3e04
d5f2 3d04 1f2e d5ef 3c04 1f25 d8fa bd70

Following the AAPCS, this takes the number of cards in r0 (permitted here; this can handle an arbitrary number of cards), and in r1 the address of the cards as an array of size-4 arrays of 8-bit integers, and returns the result in r0.

Assembly:

.section .text
.syntax unified
.global countsets
.thumb_func
countsets:
    push {r4,r5,r6,lr}  @ Save some registers and LR to the stack
    lsls r4,r0,#2       @ First card selector is 4 times number of cards: this is done because narrow LDR can only use for the address the sum of two registers, while only the wide version can have one of the registers shifted
    movs r0,#0          @ Initialise count to 0
    b start
loop:
    ldr r2,[r1,r4]
    ldr r3,[r1,r5]
    adds r2,r3
    ldr r3,[r1,r6]
    adds r2,r3            @ Add up the cards
    movs r3,#11
    muls r2,r3,r2         @ Multiply by 11
    tst.w r2,#0x0C0C0C0C  @ AND with this constant...
    it eq
    addeq r0,#1           @ and increment count if the result is 0
    subs r6,#4     @ Decrease third card selector
    bpl loop       @ Repeat if still nonnegative
    subs r5,#4     @ Decrease second card selector
middle:
    subs r6,r5,#4  @ Third card selector goes to below second card selector 
    bpl loop       @ Repeat if that's nonnegative
start:
    subs r4,#4     @ Decrease first card selector
    subs r5,r4,#4  @ Second card selector goes to below first card selector 
    bhi middle     @ Jump if that's positive
    pop {r4,r5,r6,pc}  @ Restore saved registers and return

This uses three nested loops to iterate over all combinations of three cards. For each combination, it adds the cards up (as 32-bit integers, but the four parts don't interact) and multiplies by 11. The possible results of that are as follows, in binary:

0 -> 00000000
1 -> 00001011
2 -> 00010110
3 -> 00100001
4 -> 00101100
5 -> 00110111
6 -> 01000010
-------------
AND: 00001100

As 11 is a bit more than 32/3, the result's bottom bits form a low number when the sum is a multiple of 3, and a higher number otherwise. Taking the bitwise AND (tst) with an immediate value with each byte being 0C then yields zero if and only if all four sums are multiples of 3, which means that it is a set.

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

Python 3.8, 91 bytes

Outputs False for 0.

Python has a builtin called itertools.combinations to get all of the triplets, but it's shorter just to implement it from scratch.

f=lambda a,*v:a and f(t:=a[1:],*v,a[0])+f(t,*v)or len(v)==3*all(sum(y)%3<1for y in zip(*v))

Try it online!

Python 3, 94 bytes

lambda a:sum(all(sum(y)%3<1for y in zip(*x))for x in combinations(a,3))
from itertools import*

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Minor nitpick, but itertools.combinations is a standard library function. Not a built-in. \$\endgroup\$
    – mypetlion
    Jul 27, 2021 at 19:12
4
\$\begingroup\$

Python 3, 84 81 bytes

lambda a:sum({*map(sum,zip(x,y,z))}<={0,3,6}for x in a for y in a for z in a)/6-2

Incorporating ideas from the answers of @dingledooper and @Bubbler

Try it online!

\$\endgroup\$
3
\$\begingroup\$

J, 48 41 bytes

1#.](0=1#.3|1#.|:)@#~2(#~3=1#.])@#:@i.@^#

Try it online!

-7 after reading Bubbler's divide by 3 trick

\$\endgroup\$
3
\$\begingroup\$

J, 27 bytes

_2+6%~1#.[:,0=1#.3|+"1/^:2~

Try it online!

J makes it hard to construct the Cartesian 3rd power directly, but easy to compute the attribute-wise sum of the cards in it. The result of "Table" x f/ y is dependent on the function rank of f. +"1 has rank 1 on both sides, so it computes the table of "rows of x added to rows of y".

\$\endgroup\$
1
  • \$\begingroup\$ Avoiding the Cartesian product intermediate step and going straight to the sum is very nice. \$\endgroup\$
    – Jonah
    Jul 27, 2021 at 5:47
3
\$\begingroup\$

Brachylog, 12 bytes

{⊇Ṫ\{=|≠}ᵐ}ᶜ

Try it online!

{⊇Ṫ\{=|≠}ᵐ}ᶜ
{         }ᶜ Count all …
 ⊇           subsets of the input …
  Ṫ          that are length 3 (Ṫriplets) …
   \         which transposed …
    {   }ᵐ   only have rows that …
     =|≠     are all equal or all different.
\$\endgroup\$
1
\$\begingroup\$

Vyxal s, 8 bytes

3ḋƛ÷Ṡ3ḊA

Try it Online!

Jelly port be like

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

Perl 5, 126 bytes

sub{1/6*grep{@s=map@$_,@_[map-65+ord,/./g];!/(.).*\1|[M-Z]/&&!grep{$m=$_;eval(join'+',@s[grep$_%4==$m,0..11])%3}0..3}AAA..LLL}

Try it online!

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

Charcoal, 31 bytes

IΣ⭆θ⭆…θκ⭆…θμ⬤E⁴E⟦ιλν⟧§ςπ⬤π⁻²№πς

Try it online! Link is to verbose version of code. Explanation: A group of cards forms a Set if no single attribute appears exactly twice in any aspect.

   θ                            Input
  ⭆                             Map over cards and join
      θ                         Input
     …                          Truncated to length
       κ                        Outer index
    ⭆                           Map over cards and join
          θ                     Input
         …                      Truncated to length
           μ                    Current index
        ⭆                       Map over cards and join
             E⁴                 Map over aspects
               E⟦ιλν⟧           Map over cards
                     §ςπ        Aspect of current card
            ⬤                   All aspects satisfy
                         π      Current aspect
                        ⬤       All attributes satisfy
                            №   Count of
                              ς Current attribute
                             π  In current aspect
                          ⁻     Subtract i.e. does not equal
                           ²    Literal `2`
 Σ                              Take the sum (i.e. count)
I                               Cast to string
                                Implicitly print
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 10 bytes

3.Æ€øO3ÖPO

Port of @Bubbler's Jelly answer, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

3.Æ         # Get 3-element combinations of the (implicit) input list of lists
   €ø       # Zip/transpose each inner list of lists; swapping rows/columns
     O      # Sum the inner lists of columns together for each inner-most list
      3Ö    # Check for each sum whether it's divisible by 3
        P   # Check if all inner-most were divisible by 3 by taking the product
         O  # And check of many are truthy by taking the sum
            # (after which the result is output implicitly)
\$\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.