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.