The Set Game in APL


On Monday, April 8, 1996, Roger Hui posed a puzzle on the comp.lang.apl newsgroup which asked readers to implement the Set game, finding all sets in a 12-card hand. I read the puzzle while I was at work in Greenwich, CT, and thought about it on the drive home late Tuesday night. I had a lot of time to think, because an unseasonable blizzard turned the trip home (to Springfield, MA) into a grueling ordeal of more than three hours! (I'll never forget driving up the middle of I-91 with my headlights off, the only way I could see the ruts where the few other cars had gone before me.) The following article is a refined version of the solution I came up with, written as a tutorial (albeit a rather high-powered one) for readers who are not familiar with the APL programming language. My original comp.lang.apl postings are also available here. They include benchmarking information that might be of interest to APL programmers.

Set Enterprises, Inc., the creators of the Set game, has a delightful Web site that includes a daily on-line Set game, a shareware version of the game, links to related sites, and fascinating information about the game and its history. Check it out!

Note: In this article, the funny symbols that APL is famous for are represented by {keywords}. See my APL-ASCII Transliteration article for more information. A graphic image of the code, showing the APL symbols in their proper form, is also available.


Contents


The Game

Roger Hui described the game as follows: 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 purple
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 Problem: Write a set of programs to simulate the playing of a round: deal 12 cards and identify all the sets contained therein.


Data Representation

Let the four features of the cards be described as:

     Number   Color    Shape      Pattern     -- feature
     ------   ------   --------   -------
        1     Red      Diamond    Filled     |
        2     Green    Oval       Hollow     |-- characteristic
        3     Purple   Squiggle   Lined      |

(The nonstandard pattern names were chosen to make the first letters of the characteristics unique, which will be useful later on.)

A single card can be represented as a 4-row by 3-column 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 example, the three bits for color correspond to Red, Green, and Purple, so if the third bit is on, the card is Purple. For display purposes, it's convenient to list the rows side by side:

        1 0 0   0 0 1   0 1 0   0 1 0        -- bits
        1       Purple  Oval    Hollow       -- corresponding names

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

One of the 3-by-3 matrices shown above is OK if its column sums are either all one or are zeros and three. If any column sums to two, the matrix is not OK. All the matrices have to be OK for the cards to be a valid set, so if there are any twos in the sums for the twelve columns shown above, the cards are not a set.

A single card is represented as a 4-by-3 matrix. We can describe this matrix has having dimensions "[feature;characteristic]", meaning that it has a row for each feature and a column for each characteristic. A collection of cards can be represented as a 3-dimensional array having dimensions [card;feature;characteristic].

You can think of a 3-dimensional array as a spatial arrangement of elements (or as a list of matrices), but we're actually going to need 4-dimensional arrays in the solution, so it's better to simply think of the array only in terms of its dimension list. This technique allows you to deal with n-dimensional arrays as easily as you would deal with a list of n numbers.


Dealing A Hand

The first task is to deal a hand of 12 cards. If we think of the 81 cards as being numbered 0 to 80, then representing a card code as a four-digit base-3 number will give us four numbers that can be thought of as characteristic indices. In APL, this is done using the {represent} function:

      3 3 3 3{represent}42
1 1 2 0

(42 is 1120 in base 3.) To turn these base-3 digits into the bits described above, we can compare the digits with 0 1 and 2.

      1=0 1 2
0 1 0           @ this is (1=0) (1=1) (1=2).  1 means true, 0 false
      1=0 1 2
0 1 0
      2=0 1 2
0 0 1
      0=0 1 2
1 0 0

By using a {jot}.= outer product, we can compare all four base-3 digits with 0 1 and 2 at once:

      1 1 2 0{jot}.=0 1 2
0 1 0
0 1 0
0 0 1
1 0 0

And this is the 4-by-3 matrix describing card number 42.

To pick 12 random numbers from 1 to 81 without repetition, we can use APL's deal function as in 12?81. To produce numbers in the range 0 to 80, simply subtract one from the result. The next two statements put the random numbers in variable R and display R:

      R{<-}(12?81)-1
      R
71 20 43 37 61 73 25 24 5 45 35 12

The {represent} function will turn all these numbers into base-3 numbers for us as follows:

      3 3 3 3{represent}R
2 0 1 1 2 2 0 0 0 1 1 0
1 2 1 1 0 2 2 2 0 2 0 1
2 0 2 0 2 0 2 2 1 0 2 1
2 2 1 1 1 1 1 0 2 0 2 0

However, the digits for each number run down the columns of the matrix. The matrix has dimensions [digit;card]. (And the digit dimension is really the same as the feature dimension, since there is a digit for each feature.) The {transpose} function will exchange the dimensions, giving us a [card;digit] matrix. Then, the same {jot}.= outer product we used above can be used to transform each number to a bit vector. If we execute:

      M{<-}{transpose}3 3 3 3{represent}R  @ M has dimensions [card;digit]
                                                          aka [card;feature]
      M{jot}.=0 1 2

the dimensions of the {jot}.= result are the dimensions of the left argument (M) followed by the dimensions of the right argument (0 1 2). The three elements of the right argument correspond to the characteristics, so the result has dimensions [card;feature;characteristic].

Putting this all together, here is an APL function to deal 12 cards:

     {del} Z{<-}DEAL;M;R
[1]    @Deals 12 cards
[2]    R{<-}(12?81)-1
[3]    M{<-}{transpose}3 3 3 3{represent}R
[2]    Z{<-}M{jot}.=0 1 2
     {del}

In APL, programs are referred to as "functions". {del} symbols mark the beginning and end of a function. On the first line (the "header line") of the function above, the Z{<-} declares that Z is the result variable, DEAL is the name of the function, and M and R are local variables.

If we run DEAL and examine the shape of its result (the size of the 3-D array), we get:

      H{<-}DEAL
      {shape}H
12 4 3

12 4 3 corresponds to the number of cards, features, and characteristics.


Identifying Sets

Given three cards, how can we tell if they are a valid set? The three cards will be represented as a 3-by-4-by-3 bit array having dimensions [card;feature;characteristic]. Here's how we can pick three cards:

      T{<-}H[1 2 3;;]  @ index cards 1 2 and 3
      {shape}T
3 4 3

As described above, we need to add up the the bits for all three cards. In APL, this is done by using +/[i], where i specifies the dimension along which to add. This dimension disappears from the result.

APL's reduction operator (f/A) is a remarkably useful generalization of the summation function in mathematics. Essentially, +/1 2 3 is the same as 1+2+3. Substituting different functions for + yields a variety of useful operations: {max}/ and {min}/ give the maximum and minimum values in a vector, ^/ asks if all the elements in a bit vector are true, and {or}/ asks if any elements are true.

Since we want to add along the card dimension, we will use +/[1] (because card is the first dimension). The plus reduction result has dimensions [feature;characteristic]. (The card dimension is "reduced out" by +/.)

      S{<-}+/[1]T
      {shape}S
4 3

Then, we need to check for twos in these sums. It would be convenient if our test returned true if the set is valid and false if not. Thus, the condition we want to test for is the following: Are all the sums in S not equal to two? We can do this by using S{/=}2 to mark elements that are not 2, and then doing two and-reductions (^/) to ask if all the elements are true. (One reduction per dimension, since the result should be just a single bit.)

      ^/[1]^/[2]S{/=}2
0               @ false, they're not a valid set

Now, these same operations can be done to more than one combination of three cards at once. In particular, we can build a 4-dimensional array F having dimensions [combination;card;feature;characteristic]. The first dimension corresponds to different combinations of cards, and the second dimension will have length 3 since each combination has 3 cards. The same operations shown above can be applied to this array, but we need to increase the f/[i] indices by one to account for the new combination dimension at the front. Here's how we check for valid combinations in F:

                        @ F is [combination;card;feature;characteristic]
      S{<-}+/[2]F       @ S is [combination;feature;characteristic]
      X{<-}^/[3]S{/=}2  @ X is [combination;feature]
      B{<-}^/[2]X       @ B is [combination]

These three statements can be combined into a single expression (read it from right to left):

      B{<-}^/[2]^/[3]2{/=}+/[2]F

The form f/A is the same as f/[n]A with n being the number of dimensions in A. (In other words, f/A reduces along the last dimension.) So the expression above can be simplified to:

      B{<-}^/^/2{/=}+/[2]F

The result in B has the Is-it-a-valid-set? answer for each combination of cards in F. This bit vector can be used to select the valid sets in F by using the compression function (B/D). In its atomic form, compression selects elements of the right argument corresponding to ones in the left argument. For example:

      0 1 0 1/10 20 30 40
20 40

The left argument is always a vector, but the right argument can be a higher-dimensional array. B/[i]D selects levels along the i-th dimension corresponding to ones in the left argument. In our case, we'd like to select levels along the combinations dimension in F, which is the first dimension, so we use:

      B/[1]F

The result, which contains the information for valid sets in the hand, has the same dimensions as F, but the compressed dimension is generally shorter. (And we can use the form B{slashbar}F in place of B/[1]F, because {slashbar} is shorthand for /[1].)

Now, backtracking a bit, how do we generate F? We can generate all possible combinations of integers using a utility function called COMBIN. X COMBIN Y returns a matrix giving all possible combinations of the numbers 1 to Y, taken X at a time. For example:

      3 COMBIN 4
1 2 3
1 2 4
1 3 4
2 3 4

The combination matrix we need is 3 COMBIN 12, since we have 12 cards in the hand and we take them three at a time. The result of 3 COMBIN 12 is a 220-by-3 matrix having dimensions [combination;card].

      I{<-}3 COMBIN 12

The numbers in I are indices (from 1 to 12) of cards in H (returned by DEAL), which has dimensions [card;feature;characteristic]). The statement:

      F{<-}H[I;;]

produces the array F that we want. In dimensional terms, indexing replaces the dimension indexed by I with the dimensions of I itself. Elided dimensions (those without indices specified) are carried through unchanged.

      [     card       ;feature;characteristic]  -- H
              |            |          |
              |            |          |
      [combination;card]   |          |          -- I
            |       |      |          |
            |       |      |          |
      [combination;card;feature;characteristic]  -- H[I;;]

Still with me? Putting this all together gives us the following APL function:

     {del} Z{<-}SETS H;F
[1]    @Returns all the sets in hand H
[2]    F{<-}H[3 COMBIN 12;;]
[3]    Z{<-}(^/^/2{/=}+/[2]F){slashbar}F
     {del}

(The H on the header line specifies that H is the right argument to the SETS function.) The result of SETS has the same dimensions as F: [combination;card;feature;characteristic]. The SETS function is used as follows:

      H{<-}DEAL     @ deal a hand
      S{<-}SETS H   @ find the sets
      {shape}S
2 3 4 3             @ two valid sets

      {shape}SETS DEAL
6 3 4 3             @ six valid sets in another hand

Displaying The Result

The raw four-dimensional result returned by SETS is not a pretty sight. We need a formatting function to convert the result to a display form. As usual, we start by considering the problem of formatting a single card. Given 4-by-3 bit matrix, it's a simple matter to use compression to select the appropriate characteristic keywords. Here's how:

First we create a nested vector containing all the characteristic names, in the same order as the bits in the 4-by-3 matrix:

      C{<-}'1' '2' '3'
      C{<-}C,'Red' 'Green' 'Purple'
      C{<-}C,'Diamond' 'Oval' 'Squiggle'
      C{<-}C,'Filled' 'Hollow' 'Lined'
      {shape}C
12

C is a 12-item array of words. Next, we compress C using the bit matrix, which we'll assume is in A. We have to ravel the matrix first (using ",A") to turn it into the vector required by compress.

      A
0 1 0
0 1 0
0 0 1
1 0 0
      ,A
0 1 0 0 1 0 0 0 1 1 0 0

      (,A)/C
2 Green Squiggle Filled

Next, we extend this atomic solution to the array case. If A contains data for more than one card, we will need to make additional copies of C. In particular, C will need to have the same shape as A. We can do this using reshape (S{reshape}D), which forms an array having shape S using the data in D. Although C is a vector, it is really the ravel of a matrix having dimensions [feature;characteristic]. To make duplicate copies of an array, reshape can be used to add new dimensions to the front of the dimension list. (Adding new dimensions to the end of the list will result in the data being scrambled.) The A array we'd like to use is the one returned by SETS, and it has dimensions [combination;card;feature;characteristic]. The two new dimensions, combination and card, are indeed at the front, so we can simply reshape C to match the shape of A. Then we ravel both arrays and apply compression, like so:

        (,A)/,({shape}A){reshape}C

The result of this compression will be a vector, but for display purposes it would be nice if it were an array. We can do this by reshaping the result. At first glance, you might think we should reshape it to a 4-D array just like A. However, compression has selected exactly one of each characteristic, so the last dimension would have length 1. There's no point in keeping this dimension around, so we will omit it from the reshape. {shape}A gives us the shape of A, and {neg}1{drop}{shape}A drops the last element off the shape. So the compress-and-reshape statement we want is:

        ({neg}1{drop}{shape}A){reshape}(,A)/,({shape}A){reshape}C

Here's the APL function that formats a card bit array:

     {del} Z{<-}FMT A;C
[1]    @Formats cards for display
[2]    C{<-}'1' '2' '3' 'Red' 'Green' 'Purple' 'Diamond' 'Oval' {+
           +} 'Squiggle' 'Filled' 'Hollow' 'Lined'
[3]    Z{<-}({neg}1{drop}{shape}A){reshape}(,A)/,({shape}A){reshape}C
     {del}

Now, here's a cool bit: The argument to this function can be a 2-D matrix (a single card), a 3-D matrix (such as a DEAL hand), or a 4-D matrix (such as the result from SETS), and FMT works correctly in each case! This simple function is a general solution to the problem of formatting an N-dimensional card bit array. Here are some examples:

      FMT A                  @ a card
 2 Green Squiggle Filled

      FMT H                  @ a hand
 1 Green  Oval     Filled
 3 Red    Oval     Hollow
 2 Purple Diamond  Hollow
 2 Green  Diamond  Filled
 2 Green  Oval     Hollow
 3 Red    Diamond  Filled
 3 Red    Squiggle Hollow
 3 Red    Squiggle Lined
 2 Red    Oval     Hollow
 1 Green  Oval     Lined
 3 Green  Oval     Lined
 2 Red    Oval     Lined


      FMT SETS H              @ a collection of sets
 1 Green  Oval     Filled
 2 Purple Diamond  Hollow
 3 Red    Squiggle Lined

 1 Green  Oval     Filled
 2 Green  Oval     Hollow
 3 Green  Oval     Lined

 3 Red    Oval     Hollow
 3 Red    Diamond  Filled
 3 Red    Squiggle Lined

Ahh, APL!


Entering A Hand

One last function will make it easy to key in a hand you've dealt with a deck of cards so you can have the computer find all the sets for you. (I couldn't find any sets at all in the second hand I dealt, so I immediately wanted to find out just how many sets I was missing.)

A card can be identified by the first letters of the characteristics. For example, '3ROH' is 3 Red Oval Hollow. Rather than impose a particular order on the dimensions, I chose to make all the characteristic names have unique first letters, so you can enter them in any order. (So RH3O is the same as 3ROH.)

For a single feature, we can use a {jot}.= outer product to produce the bit vector for the feature. First, we get a matrix:

      '123'{jot}.='3ROH'
0 0 0 0                 @ '1'='3ROH'
0 0 0 0                 @ '2'='3ROH'
1 0 0 0                 @ '3'='3ROH'

The desired bit vector is produced by doing an {or}/ to each row (which asks if there are any ones on the row):

      {or}/'123'{jot}.='3ROH'
0 0 1

Similar statements get the other rows of the 4-by-3 card bit matrix:

      {or}/'RGP'{jot}.='3ROH'
1 0 0

      {or}/'DOS'{jot}.='3ROH'
0 1 0

      {or}/'FHL'{jot}.='3ROH'
0 1 0

We can do these all at once by using a 4-by-3 left argument, as follows:

      L{<-}4 3{reshape}'123RGPDOSFHL'
      L
123
RGP
DOS
FHL
      {or}/L{jot}.='3ROH'
0 0 1
1 0 0
0 1 0
0 1 0

This is the 4-by-3 bit matrix describing the card having three red hollow ovals on it.

We would also like to be able to apply this statement to a collection of cards. In this case, the right argument will be a matrix having a row for each card. We can conveniently build the matrix using the MATRIFY utility function:

      D{<-}MATRIFY'3ROH 2RDL'
      D
3ROH
2RDL

This matrix has dimensions [card;letter]. When we plug D into the {jot}.= statement above, here's how the dimensions track as the statement is executed:

     {or}/        L               {jot}.=     D
                                                   (substitute dimensions)
     {or}/[feature;characteristic]{jot}.=[card;letter]
                                                   (apply {jot}.=)
     {or}/[feature;characteristic;card;letter]
                                                   (apply {or}/)
     [feature;characteristic;card]

The result has the card dimension at the end, rather than at the front as we want it. We can move it to the front using the dyadic transpose function as follows:

     2 3 1{transpose}{or}/L{jot}.=D

Putting this all together yields the following function:

     {del} Z{<-}HAND D;L
[1]    @Translates hand codes to the corresponding bit array
[2]    D{<-}MATRIFY D
[3]    L{<-}4 3{reshape}'123RGPDOSFHL'
[4]    Z{<-}2 3 1{transpose}{or}/L{jot}.=D
     {del}

Here's that second hand I dealt:

      H{<-}HAND'2GLS 1RSF 2RDL 1GSL 2PDH 2PSF 2RDH 1POL 1PDL 3RDL 2RSF 1ROF'

And here is the set I couldn't find:

      FMT SETS H
2 Green  Squiggle Lined
1 Purple Oval     Lined
3 Red    Diamond  Lined

Code Summary

For reference, here are the programs developed in this article, plus the two utility functions that are used by the programs. The APL code in this .html file can be extracted using the APLASCII workspace. See my home page for more information. If you'd like to see the code in its proper symbolic form, a graphic image of the code is also available.

     {del} Z{<-}DEAL;M;R
[1]    @Deals 12 cards
[2]    R{<-}(12?81)-1
[3]    M{<-}{transpose}3 3 3 3{represent}R
[2]    Z{<-}M{jot}.=0 1 2
     {del}

     {del} Z{<-}SETS H;F
[1]    @Returns all the sets in hand H
[2]    F{<-}H[3 COMBIN 12;;]
[3]    Z{<-}(^/^/2{/=}+/[2]F){slashbar}F
     {del}

     {del} Z{<-}FMT A;C
[1]    @Formats cards for display
[2]    C{<-}'1' '2' '3' 'Red' 'Green' 'Purple' 'Diamond' 'Oval' {+
          +}'Squiggle' 'Filled' 'Hollow' 'Lined'
[3]    Z{<-}({neg}1{drop}{shape}A){reshape}(,A)/,({shape}A){reshape}C
     {del}

     {del} Z{<-}HAND D;L
[1]    @Translates hand codes to the corresponding bit array
[2]    D{<-}MATRIFY D
[3]    L{<-}4 3{reshape}'123RGPDOSFHL'
[4]    Z{<-}2 3 1{transpose}{or}/L{jot}.=D
     {del}

     {del} Z{<-}X COMBIN Y;C;J;K;N
[1]    @Returns all possible combinations of {alpha} items drawn from {iota}{omega}
[2]    @ The result is origin-sensitive
[3]    N{<-}1+Y-X
[4]    K{<-}{divide}N  @ give domain error if X=Y+1
[5]    K{<-}(X-1)+{iota}N
[6]    Z{<-}(N,{signum}X){reshape}K
[7]    R{<-}N{reshape}1
[8]   L1:{->}(#IO>1{take}K{<-}K-1)/0
[9]    C{<-}{reverse}R{<-}+\R
[10]   J{<-}({iota}{reshape}J)-J{<-}C/+\0,1{drop}C
[11]   Z{<-}(C/K),Z[J;]
[12]   {->}L1
     {del}

     {del} Z{<-}A MATRIFY V;D;L;I;W;M
[1]    @Forms a matrix from a vector or matrix of names {omega}
[2]    @ The optional left argument is a vector of delimiter characters (which
[3]    @    separate the words in the right argument)
[4]    @ Treats multiple consecutive delimiters as a single delimiter
[5]    @
[6]    {->}(1<{shape}{shape}Z{<-}V)/0 @ return argument unchanged if it's already a matrix
[7]    {execute}(0=#NC 'A')/'A{<-}'' ''' @ set left arg if user didn't supply one
[8]    D{<-}V{epsilon}A              @ mark delimiters in V
[9]    L{<-}{neg}1{drop}1,D          @ push a 1 into the front of each group of 0's
[10]   V{<-}(I{<-}~D)/V              @ delete delimiters
[11]   L{<-}I/L
[12]   I{<-}L/{iota}{shape}L         @ find position of the first of each name
[13]   W{<-}(1{drop}I,1+{shape}L)-I  @ get the width of each name
[14]   M{<-}0{max}{max}/W            @ width of the widest name
[15]   V{<-}(,W{jot}.{>=}{iota}M)\V  @ insert blanks at the end of short names
[16]   Z{<-}(({shape}W),M){reshape}V @ convert to a matrix
     {del}

Copyright © 1996 by Jim Weigang. All rights reserved.


Home Page