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