Identifying Sets
Author Message
Identifying Sets

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 following three cards form a set:

2 repetitions of a red shaded  diamond
2 repetitions of a red solid   squiggle
2 repetitions of a red outline oval

(Repetitions are the same; colors are the same; textures are
different; shapes are different.)

The first player to identify a set wins the round.

The Problem:  Write a set of programs to simulate the playing of
a round: deal 12 cards and identify all the sets contained therein.

Fri, 25 Sep 1998 03:00:00 GMT
Identifying Sets

The following does not deal with dealing (the cards, that is).
But it checks for sets in any dealt cards.

The main point of the exercise are really "representations".
I'm using various reps for the cards in the program, as well
as conversions between those reps.  Any J2 or J3 will do.
All comments are welcome, I am sure that it can be improved.
(I have the feeling that some C.ycles are lurking there.)

Martin Neitzel

Sat, 26 Sep 1998 03:00:00 GMT
Identifying Sets
Uh oh.  All this modern software with its
thousands of button and hidden magic...
Here it comes again, straight from a clipboard.

Martin

NB. PART 1:  Representations
NB. ------------------------

NB. Each card is identified according to its four
NB. properties (number, color, shading, shape)
NB. with three values each.  Here are the properties:

numbers =: ;: 'one two three'
colors =: ;: 'red blue green'
shadings =: ;: 'hollow striped solid'
shapes =: ;: 'diamond oval squiggle'

NB. It will be handy to have them all together:

prop_names =: numbers, colors, shadings,: shapes

NB. Any of the 81 cards can be encoded as a single number in the
NB. range 0..80.  We draw 12 distinct cards from the entire deck:

cards =. 12 ? 81

NB. Each card is based on all its four properties, so it's
NB. natural to discover them with anti-base #:

props =: 3 3 3 3 & #:
props cards

NB. To show a card given in any of those two representations,
NB. a third, string-based representation is helpful:

show_props =: {"0 1&prop_names " 1

NB. PART 2:   Completion of Sets
NB. ----------------------------

NB. Two cards of a set already determine the third card in
NB. a set uniquely.  For each property, the following states
NB. what the third property must be, based on how the two ones
NB. that are already known compare:

same =: ]
remaining =: 3: - +

NB. complete has dyadic rank 0 0 but we'll use it on cards:

2 complete 2                                    NB. individual properties
0 0 1 2 complete 0 1 2 2                NB.     two cards (prop collections)
16 complete&.props 24                   NB. in compact representation
show_card 16 24 8                               NB. better inspect it...

NB. PART 3:   Finding SETs in a Set of Cards
NB. ----------------------------------------

NB. find_sets takes a vector of cards as argument
NB. and returns a list of triplets, ie. a table.

find_sets =: 3 : 0

NB. there are no sets in less than three cards:
if. 2 >: #y. do.
i. 0 3
return.
end.

NB. Find all SETs involving the first card.
NB. After that recurse with just the other ones
NB. and combine the two results.

hd =. {. y.
tl =. }. y.

NB. completing_cards and tl will run in parallel all the time:
completing_cards =. hd complete"1 &. props tl

NB. where (boolean) are the self-completing elements?
successful_tails =. (completing_cards&i. < tl&i.) tl

NB. completing_cards i. tl   does the basic search for contained
SETs.
NB. In the expression  (L < R) tl  above,
NB.             R tl    will be just the same as  i.#tl, ie. <:#tl at
most.
NB.             L tl    will often indicate mismatches (#tl).  Those
NB.                             will definitely zero the result wrt
R tl.
NB.                             The half of the remaining i. hits
will be zeroed
NB.                             since if the set (hd,a,b) is in y.
then (hd,b,a)
NB.                             will be in y., too.  We just need
one.
NB. There is problably a more lucid tacit exression for
NB. the same.
NB.
NB. Tack the head to the filtered pairs:
sets_here =. hd ,. successful_tails # tl ,. completing_cards

NB. recurse on the tail and compile the results:
sets_here, find_sets tl
)

NB. PART 4:  Tests
NB. --------------

NB. crash and burn test:
find_sets cards

NB. use a readable form for human verification:
(,&<&show_card find_sets) cards

NB. do repeatedly some experiments:
(,&<&show_card find_sets) 12 ? 81

NB. PART 5:   Comments
NB. ------------------

NB. I was using the single number representation to invoke find_set.
NB. Doing the &.props transformations again and again for the same
NB. numbers degrades the performance by O(*:), so a variant working
NB. directly on base-reps would be faster.  It would move the &.props
NB. just to the outer level, the algorithm could remain the same.
NB. It's also trivial to re-write the clear tail recursion into a loop.

NB. PART 6:  REAL Jugglers
NB. ----------------------

NB. ... would of course use the following representation:

show_props =: 3 : 0 " 1
('ncsf') =. y.
<(((+:>:n) \$ (f{'*+-'),s{' .:'),c{' /~')-.' '
)

test =: 4 3&\$  ,&<&show_card find_sets
test 12 ? 81

Sat, 26 Sep 1998 03:00:00 GMT
Identifying Sets
NB. Cards are represented as 4-vectors

NB. Given x. and y. are 2 cards, what third card will fill out the set?
NB. For each element, use the third combination if the value are different,
NB. or the same value if they are the same

NB. Given y. is a set of cards, create all combinations of 2 cards,
NB. then fill each pair out with the third card that makes a set.
NB. Discard first axis to reshape to nx3x4 (sets of 3 cards)
NB. We draw the same card twice but that's OK

NB. Given y. is the set of all combinations, which sets are actually
NB. in the input?  They are the ones that show up 6 times
NB. (others appear once or twice).  Sort the 2-cells (each set,
NB. that is) into a canonical form, then discard the first 5 elements
NB. in each group of identical sets

NB. Roll em

+-------+-------+
|0 0 1 2|0 0 2 0|
|0 0 2 0|0 1 2 0|
|0 1 0 1|0 2 2 0|
|0 1 2 0|       |
|0 2 2 0|0 0 1 2|
|1 0 0 0|0 1 0 1|
|1 0 2 2|0 2 2 0|
|1 1 0 2|       |
|1 1 2 2|       |
|2 0 0 1|       |
|2 0 2 0|       |
|2 2 1 2|       |
+-------+-------+

O(n**2 log n) in time, O(n**2) in space.

Henry Rich

Sun, 27 Sep 1998 03:00:00 GMT
Identifying Sets
Here's my solution to Roger's "Set" game problem:

============= setgame.js =============
NB. Shuffle the deck and deal a hand:

deck=: 3: combs 4:              NB. Deck is 3 choices for 4 features,

hand=: 12&{.                    NB. and pick off a single hand.

NB. Determine if some cards form a set:

NB. All combinations of cards:
btab=: 2&combs                  NB. Make binary table,

all3=: (3 outof 12)&{           NB. Select all 3-tuples.

NB. Test all combinations for a set:

NB. A verb to display cards:
Props=: _3]\;:}: 0 : 0          NB. Table of properties x labels.
one two three red green blue solid outline shaded diamond oval squiggle
)

NB. And finally put it together:

======================================

NB. Try it:
huihand=. 3 4\$ 1 0 2 0 , 1 0 0 2 , 1 0 1 1  NB. Roger's example.
see huihand                     NB. Display Roger's example,
two red shaded diamond
two red solid squiggle
two red outline oval
isset huihand                   NB. and test it.
1
see h=. newhand ''              NB. See a hand,
three green shaded oval
one blue solid oval
two green shaded diamond
two green solid diamond
three red shaded diamond
three blue solid diamond
one blue shaded diamond
one blue outline squiggle
one red outline oval
two green shaded squiggle
two red shaded oval
one green solid squiggle
play h                          NB. and all sets in it.
+-------------------------+-------------------------+
|three green shaded oval  |one blue shaded diamond  |
|one blue solid oval      |one red outline oval     |
|two green shaded diamond |one green solid squiggle |
|two green solid diamond  |                         |
|three red shaded diamond |three blue solid diamond |
|three blue solid diamond |one red outline oval     |
|one blue shaded diamond  |two green shaded squiggle|
|one blue outline squiggle|                         |
|one red outline oval     |two green shaded diamond |
|two green shaded squiggle|three red shaded diamond |
|two red shaded oval      |one blue shaded diamond  |
|one green solid squiggle |                         |
|                         |one blue solid oval      |
|                         |one blue shaded diamond  |
|                         |one blue outline squiggle|
+-------------------------+-------------------------+

--

Sun, 27 Sep 1998 03:00:00 GMT
Identifying Sets
Kirk Iverson, trying to invert  ;:'I sing of Olaf' :

Quote:

I would like to see a fit feature for "raze" (;) which would insert something
between the opened items.  Then, the following could be equivalent to the
laborious phrase above:

;!.' '

Martin Neitzel

Sun, 27 Sep 1998 03:00:00 GMT
Identifying Sets
Roger Hui wrote on April 8:

Quote:
> 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.

A card can be represented as a 4-by-3 bit matrix having a row for each
feature and a column for each characteristic.  Each row has exactly
one bit turned on, indicating the characteristic for that feature.  For
display purposes, it's convenient to list the rows side by side:

1 0 0   0 1 0   0 0 1   0 1 0         - bits
1       oval    blue    outline       - labels

For three cards to be a valid "set", all the characteristics for a
feature must be either identical or distinct.  Here are the bits for
three cards:

1 0 0   0 0 1   1 0 0   0 1 0         - card 1
0 0 1   0 0 1   1 0 0   0 0 1         - card 2
0 1 0   0 0 1   0 0 1   0 1 0         - card 3
OK      OK      No      No

The column sums for a 3-by-3 matrix shown above must be either all 1s,
or 0s and 3 for the matrix to be OK.  The maximum value of the sums
suffices to identify a valid matrix: if it's 1 or 3, the matrix is OK.
If all four matrices (features) are OK, the three cards are a set.

The coding is straightforward but involves multidimensional arrays,
which can be intimidating if you don't know how to track the dimensions.

{del} Z{<-}HAND

[2]    Z{<-}{transpose}0 1 2{jot}.=3 3 3 3{represent}{neg}1+12?81
{del}

The result of HAND has dimensions [card;feature;characteristic].  (That
is, it has a plane for each of the 12 cards, a row for each of the 4
features, and a column for each of the 3 characteristics.)

{del} Z{<-}SETS H;A

[2]    A{<-}H[3 COMBIN 1{take}{rho}H;;]
[3]    Z{<-}(^/({max}/+/[2]A){epsilon}1 3){slashbar}A
{del}

Variable A in SETS is all possible combinations of three cards
"triples").  It has dimensions [combination;triple;feature;characteristic]
and shape 220 3 4 3.  Keeping these dimensions in mind allows you to
understand the reductions and compression on line [3].  Using names
instead of dimension indices, the statement could be written as:

( ^/[feature] ({max}/[char.] +/[triple] Z) {epsilon} 1 3 ) /[comb.] Z

It may help to mentally execute the expression in the outer parentheses
for the OK/No matrices above, in which the rows are [triple], the
columns are [characteristic] and the four "hypercolumns" are [feature].

The result of SETS has the same dimensions as A, but the first
element of the shape will be different.

{del} Z{<-}FMT A;C

[2]    C{<-}'1' '2' '3' 'diamond' 'oval' 'squiggle' 'red' 'green' {+
+}'blue' 'solid' 'outline' 'shaded'
[3]    Z{<-}({neg}1{drop}{rho}A){rho}(,A)/({rho},A){rho}C
{del}

Originally, I had the dimensions arranged differently, but when it came
time to format the result, I rearranged them to simplify the formatting.

{del} R{<-}M COMBIN N;D;E;F;G;P

+}{omega}
[2]    E{<-}({iota}P{<-}N-R{<-}M-1)-#IO
[3]    D{<-}R+{iota}P
[4]    R{<-}(P,1){rho}D
[5]    P{<-}P{rho}1
[6]   L1:{->}(#IO>1{take}D{<-}D-1)/0
[7]    P{<-}+\P
[8]    G{<-}+\{neg}1{drop}0,F{<-}{reverse}P
[9]    E{<-}F/E-G
[10]   R{<-}(F/D),R[E+{iota}{rho}E;]
[11]   E{<-}G
[12]   {->}L1
{del}

COMBIN is from Gary Bergquist's Zark APL Tutor Newsletter, 1995 Quarter
2.  (It was included as part of the problem description for the
Permutations puzzler, which was discussed in comp.lang.apl starting on
June 5, 1995.)  Although this may not be the fastest algorithm, the
point is moot:  If you want SETS to run fast, you should precompute
3 COMBIN 12 just once, store the result in a variable, and use that
variable on line [2] of SETS.

Some examples:

#RL{<-}16807
{rho}H{<-}HAND
12 4 3
({enclose}[3]H) (FMT H)
0 0 1  0 1 0  0 0 1  0 1 0   3 oval     blue  outline
1 0 0  0 0 1  1 0 0  0 1 0   1 squiggle red   outline
0 1 0  0 1 0  0 0 1  1 0 0   2 oval     blue  solid
0 1 0  0 1 0  1 0 0  1 0 0   2 oval     red   solid
0 0 1  1 0 0  0 0 1  1 0 0   3 diamond  blue  solid
0 0 1  0 0 1  1 0 0  1 0 0   3 squiggle red   solid
1 0 0  0 0 1  0 0 1  1 0 0   1 squiggle blue  solid
1 0 0  0 0 1  0 1 0  0 0 1   1 squiggle green shaded
1 0 0  1 0 0  0 1 0  0 1 0   1 diamond  green outline
0 1 0  0 1 0  0 0 1  0 0 1   2 oval     blue  shaded
0 1 0  1 0 0  0 0 1  0 1 0   2 diamond  blue  outline
1 0 0  0 1 0  1 0 0  0 0 1   1 oval     red   shaded

FMT SETS H
1 squiggle red   outline
1 squiggle blue  solid
1 squiggle green shaded

2 oval     blue  solid
3 diamond  blue  solid
1 squiggle blue  solid

3 squiggle red   solid
1 diamond  green outline
2 oval     blue  shaded

1 squiggle blue  solid
1 diamond  green outline
1 oval     red   shaded

#RL{<-}12345
FMT SETS HAND
3 squiggle red   outline
1 oval     blue  shaded
2 diamond  green solid

3 squiggle red   solid
2 diamond  green solid
1 oval     blue  solid

Nice programming puzzle, but I'm not sure I'd want to play this game!

Jim

Sun, 27 Sep 1998 03:00:00 GMT
Identifying Sets
Martin Neitzel writes on Wednesday, April 10:

Quote:
> Kirk Iverson, trying to invert  ;:'I sing of Olaf' :

> I would like to see a fit feature for "raze" (;) which would insert something
> between the opened items.  Then, the following could be equivalent to the
> laborious phrase above:

>        ;!.' '

;:^:_1 (the inverse of word formation) works well for this purpose.  Thus:

[ x=.;:'I sing of Olaf'
+-+----+--+----+
|I|sing|of|Olaf|
+-+----+--+----+
;:^:_1 x
I sing of Olaf

|.&.;: 'reverse the words in this sentence'
sentence this in words the reverse
|.&.>&.;: 'reverse each word in this sentence'
esrever hcae drow ni siht ecnetnes

Sun, 27 Sep 1998 03:00:00 GMT
Identifying Sets

Roger Hui writes on Monday, April 8:

Quote:
> 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.  ...
> The first player to identify a set wins the round.

> The Problem:  Write a set of programs to simulate the playing of
> a round: deal 12 cards and identify all the sets contained therein.

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
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=: (12"_ ? (#cards)"_) { 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.  There are various ways
to test for this; the one that I prefer is that 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

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 n combinations of i.m is well-known
and was previously discussed in this forum.  Thus:

comb=: 3 : 0
:
i=.1+x.
z=.1 0\$k=.i.#c=.1,~(y.-x.)\$0
while. i=.<:i do. z=.;k,.&.>(-c=.+/\.c){.&.><1+z end.
)

ci  =: 3 comb 12

\$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

Eugene McDonnell's solution "Sett" uses a single integer 3#.v
to represent a card, temporarily converting to the vector
representation only to apply the set test.  Eugene's solution
is more suitable for implementation in other APL dialects
because it does not depend, as my solution does, on the
availability of matrix e. matrix.

The following timings were obtained on a P90 running Windows NT
and J3.02x, reported as seconds averaged over 100 trials:

timer=:6!:2
100 timer 'sets deal 0'
0.0061
100 timer 'Sett 12?81'
0.01152

Jim Weigang's solution, using a constant for 3 comb 12, gives
a timing of 0.01091 on APL*PLUS III the same machine.

Several other variations on the vector vs. scalar representation
theme are possible, including the following ultimatum:

vector of the sets for every possible round, and the expression

Quote:
>(?12!81){s  deals 12 cards (encoded as the single integer

?12!81) and computes the sets contained therein.  The arrays
involved in this "solution" are big, but far less in number
of bytes than the number of particles in the universe ...

Of the other solutions posted so far, the one by Kirk Iverson
is similar to the solutions discussed above, and the ones
by Martin Neitzel and Henry Rich compute the sets by forming
all pairs from the 12 cards and then completing the third member
of the set.  The verb "allsets" in Rich's solution,

can be made shorter and clearer, by reformulating the second
verb in the composition as a table (outer product) on the verb
(thirdblade , ,:)"1, thus:

________________________________

Bonus Question 1:  If a card has f features, each having c
possible values, and a set contains c cards, what is the
minimum number of cards that should be dealt in a round to
ensure that the probability of finding a set is at least p?
(To make the game interesting, p should probably be set at 0.9
or higher.)

Bonus Question 2:  Use standard utilities (e.g. Windows Paintbrush)
to create the bitmap card images, and use your favorite language
to provide a GUI for this game.

Mon, 28 Sep 1998 03:00:00 GMT
Identifying Sets
Jim Weigang writes on Wednesday, April 10:

Quote:
> Nice programming puzzle, but I'm not sure I'd want to play this game!

You are telling me!  The first time I played this game, I was
soundly beaten by Natasha Whitney, who was all of five years old
at the time.

Mon, 28 Sep 1998 03:00:00 GMT

 Page 1 of 2 [ 26 post ] Go to page: [1] [2]

Relevant Pages