Essays/Set Game

From J Wiki
Jump to: navigation, search

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.

Set0.jpg

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.