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:
- Create the deck of cards and shuffle it.
- Take 12 cards into a hand
- Find all the possible combinations of 12 cards taken 3 at a time.
- For each combination select where attribute counts are all not 2.
- 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:
- $$ 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
- 12=>CardsPerHand; 3=>
CardsPerSet;
An unnecessary step to make the code a little more readable (and changable).
- $$ 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;).
- 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;).
- deck <- CardsPerHand =>hand;
gives me a hand out of the shuffeled deck.
- 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.
- 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;).
- "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.