Essays/Set Game
The Game
Set is a game marketed by Set Enterprises Inc. In each round, 12 cards are dealt from a deck of 81 distinct cards. Each card is imprinted with one or more repetitions of a symbol with the following four features:
- repetition: 1, 2, or 3
- shape: diamond, oval, or squiggle
- color: red, green, or blue
- texture: solid, outline, or shaded
A "set" consists of three cards wherein each feature is either the same in all three cards or different in all three cards.
For example, the three cards marked by an X form a set (repetitions are different; colors are different; textures are different; shapes are different):
2 repetitions red outline diamond 3 repetitions purple shaded oval 1 repetition green solid squiggle
And the three cards marked by a Y form a set (repetitions are different; colors are different; textures are different; shapes are the same):
2 repetitions red outline squiggle 1 repetition purple shaded squiggle 3 repetitions green sold squiggle
The first player to identify a set wins the round.
Write a set of programs to simulate the playing of a round: deal 12 cards and identify all the sets contained therein.
A Solution
A card can be represented by a 4-element vector of the integers 0 1 2, and the deck of cards can be represented by:
cards=: (#: i.@(*/)) 3 3 3 3 $ cards 81 4 8 {. cards 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 1 1 0 0 1 2 0 0 2 0 0 0 2 1 _4 {. cards 2 2 1 2 2 2 2 0 2 2 2 1 2 2 2 2
(12?#cards){cards deals 12 cards, codified as a verb thus:
deal=: cards {~ 12 ? (#cards)"_ ] d=: deal '' 2 1 2 1 0 2 0 1 1 1 2 0 1 1 0 0 2 0 2 0 2 2 0 0 0 2 2 0 0 2 1 2 0 0 1 1 1 1 2 2 1 0 2 1 0 1 0 2 $ d 12 4
Three cards form a "set" if each feature is the same in all 3 cards or different in all 3 cards. Thus each feature must be one of 0 0 0, 1 1 1, or 2 2 2 (the same in all 3 cards) or a permutation of 0 1 2 (different in all 3 cards). That is, if 3 cards are represented by a 3 4 integer matrix, then:
univ=: (3 $"0 i.3) , (i.!3) A. i.3 test=: *./"1 @: (e.&univ) @: (|:"2) univ 0 0 0 1 1 1 2 2 2 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0 $ univ 9 3 3 {. d 2 1 2 1 0 2 0 1 1 1 2 0 test 3 {. d 0 test 3 4 $ 0 0 0 0 0 0 0 1 0 0 0 2 1
It remains to form all size 3 combinations of the 12 cards and select those combinations that pass the test. A verb that generates all size x combinations of i.y can be found in the Combinations essay:
comb=: 4 : 0 k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z ) ci =: 3 comb 12 sets=: (test # ]) @ (ci { ]) $ ci 220 3 3!12 220 sets d 0 2 0 1 0 2 2 0 0 2 1 2 1 1 2 0 2 0 2 0 0 2 2 0 2 2 0 0 0 0 1 1 1 1 2 2 0 2 2 0 0 0 1 1 0 1 0 2 $ sets d 4 3 4
Collected definitions:
comb=: 4 : 0 k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z ) cards=: (#: i.@(*/)) 3 3 3 3 deal =: cards {~ 12 ? (#cards)"_ univ =: (3 $"0 i.3) , (i.!3) A. i.3 test =: *./"1 @: (e.&univ) @: (|:"2) ci =: 3 comb 12 sets =: (test # ]) @ (ci { ])
See also
Contributed by Roger Hui. A version of this text previously appeared as a thread in the newsgroup comp.lang.apl on 1996-04-08.