Case Study CS00008: The Set Game

The problem: Find valid sets in a dealt hand: This problem is referred to as the Set Game. It is described at the Set Enterprises website. An APL solution is given at Jim Weigang's page. Basically there are four types of sets each containing three items. They form a deck of 81 cards which are shuffled and 12 are dealt to the table. The object is for participants to find a way of mating up three cards such that attributes are all different or all the same.

The solution:

  1. Create the deck of cards and shuffle it.
  2. Take 12 cards into a hand
  3. Find all the possible combinations of 12 cards taken 3 at a time.
  4. For each combination select where attribute counts are all not 2.
  5. Display the winning sets.

Note: You can cut and paste these code fragments into the code pane of the Glee interpreter and experiment as you go along to see the actual operations live.

The Glee code:

$$ 4 different symbols on each card
'Red'   'Green'     'Purple'    =>color;
'Ovals' 'Squiggles' 'Diamonds'  =>symbol;
'One'   'Two'       'Three'     =>number;
'Solid' 'Open'      'Striped'   =>shading;

12=>CardsPerHand; 3=> CardsPerSet;

$$ Create the 81 card deck; shuffle it; and deal a hand
0..80+81 %< 3  #ea"
  ->4+1=>i;
  (color[i[1]]),(symbol[i[2]]),(number[i[3]]), (shading[i[4]])
" =>deck;

deck[deck# %%(deck#)?100 ``>] =>deck;
deck <- CardsPerHand =>hand;

hand[CardsPerHand ! CardsPerSet]=>sets;
sets[sets #ea "< ``& /# ^| 2 ~"<] => valid;
"Hand:"$; (hand >>> ,,)$; "-"%%30$;"Sets:"$; (valid  ,,)$;

The Output:
Hand:
Green Ovals Three Striped
Green Squiggles Three Open
Green Squiggles Two Solid
Purple Diamonds One Open
Purple Diamonds One Striped
Purple Diamonds Two Open
Purple Ovals One Solid
Purple Ovals Three Solid
Purple Ovals Three Striped
Purple Squiggles One Striped
Red Diamonds One Open
Red Squiggles Two Open
--------------------------------
Sets:
Red Diamonds One Open
Purple Ovals Three Striped
Green Squiggles Two Solid

Purple Ovals One Solid
Purple Squiggles One Striped
Purple Diamonds One Open

Purple Squiggles One Striped
Purple Diamonds Two Open
Purple Ovals Three Solid

The play-by-play:

  1. $$ 4 different symbols on each card
    'Red'   'Green'     'Purple'   =>color;
    'Ovals' 'Squiggles' 'Diamonds' =>symbol;
    'One'   'Two'       'Three'    =>number;
    'Solid' 'Open'      'Striped'  =>shading;

    Define four variables to store the three instances each of color, symbol, number and shading. These are just 3 element sequences of strings
  2. 12=>CardsPerHand; 3=> CardsPerSet;
    An unnecessary step to make the code a little more readable (and changable).
  3. $$ Create the 81 card deck; shuffle it; and deal a hand
    0..80+81 %< 3  #ea"
      ->4+1=>i;
      (color[i[1]]),(symbol[i[2]]),(number[i[3]]),(shading[i[4]])
    " =>deck;
     If you have cards containing 4 things with 3 variations, it takes 3^4 or 81 cards to represent them all. I just generate a numeric sequence from 0 to 80 (81 cards) and then add 81 to it (0..80+81). Next I break these numbers into the base 3 representation (0..80+81 %< 3). The result is a sequence of 4 and 5 element numerics. If we hadn't added the 81 we would have gotten from 1 to 4 numerics in each sequence item and would have had to do some gymnastics to fill. Since all elements have at least 4 numbers we can do a simple 4 take on each of them  (0..80+81 %< 3  #ea"  ->4+1=>i;). Base and representation operations are in base 0. I add the 1 to get back to base 1 for Glee indexing. Everything between the double quotes (#ea "....") is executed for each item in the sequence. ( i ) is the 4 element numeric. The first element is for color ((color[i[1]])); the second for symbol ((symbol[i[2]])); etc. Each of these is a one element sequence. I catenate them together to form a 4 element sequence of sequences. I index into each of my attributes and create a 4 item sequence of strings. These sequences represent each of the possible combinations on a card. The output of this (#ea"...") operation is an 81 item sequence which is my deck of cards (..." =>deck;).
  4. deck[deck# %%(deck#)?100 ``>] =>deck; Sorts the cards in the deck. deck# %%(deck#) forms the 81 element numeric vector containing all 81's. Applying the random operator (with fixed seed of 100) (81 81... 81 81 ? 100), I create 81 random numbers between 1 and 81. Grading these gives me 81 randomized indices I use to index into the deck resulting in a new shuffeled deck. (deck[81 81... 81 ?100 ``>] =>deck;).
  5. deck <- CardsPerHand =>hand; gives me a hand out of the shuffeled deck.
  6. hand[CardsPerHand ! CardsPerSet]=>sets;. Given this hand, if I index into it with all the combinations of CardsPerHand taken CardsPerSet at at time (i.e. 12 ! 3) I produce all the possible sets for this hand.
  7. sets[sets #ea "< ``& /# ^| 2 ~"<] => valid;. Valid sets are those where none of the symbols occur exactly two times. I go through each item in the set (sets #ea "...). As it's served up it is a one element sequence containing a 4 item sequence of strings. I disclose it ( < ) giving me the sequence of 12 strings. I find the indices of each unique string (``&) but all I really want to know is how many there are for each (/#). I now have a numeric vector of attribute occurrences. I know if any occur exactly 2 times ( ^| 2 ) they are losers. What remains ( ~ ) are then winners. The result comes to me as a set of 1 element bit vectors. I disclose ( < ) this to get a single bit vector which I then use as the indices into the sets to extract the winning sets (sets[...] => valid;).
  8. "Hand:"$; (hand >>> ,,)$; '-'%%30$;"Sets:"$; (valid  ,,)$; . Displaying the results is all that remains. My results are nested two deep. I want a different separator at each depth. I want to separate the symbols by a space; the cards by a new line; and the sets by two new lines. The monadic version of Glee's  separation operator (,,) supports this need. I display a caption for the hands ( "Hand:"$; ) followed by the hand of sets in sorted order with each set on a separate line((hand >>> ,,)$;). I display a line of dashes '-'%%30$; . I then display the valid sets with its caption ("Sets:"$; (valid  ,,)$;)

This completes the example. To better understand these operators and other things you can do with them, consult the operator pages according to the type of data you see being operated on.