Set Game

The game is played by finding sets of three cards that are all the same, or all different, across four independent "facets" or "dimensions". These dimensions are: number, shape, color, and fill. Each of these dimensions has three possible values. Number has: one, two, or three; color has: red, green, or blue; shape has: rectangle, X, or O; and fill has: open, striped, or solid.

Here are three cards that demonstrate all twelve values:

Let's look at some examples. The following three cards are all the same in: number, color, and shape. They are all different in: fill. Because each of the four dimensions are all the same, or, all different, these three cards form a set. The next three cards are the same in: number, and shape. They are different in: color, and fill. Each of the four dimensions is either entirely homogeneous or entirely different; therefore, this is a set. What about the three cards below? We have: same number, same shape, different colors, two open fills, and one striped fill. In order for this to be a set, the fills have to be all the same, or all different. So either the two green Xs have to be open, or, one of the other cards has to be solid. The next three cards are the same in shape; and different in color, number, and fill. This is a set. Below, we have the same shape and number, different fill, two reds, and one green not a set. To make it a set, one of the red cards needs to be blue, or the green card needs to be red. Finally, here is a set where all 4 dimensions are different. Can you find the four sets in the first window of this chapter? The answers are listed in the window displayed in the Iteration 9 section.

At their Web site, the people who invented SET? suggest it is an excellent vehicle for exercising both halfs of your brain. Because the game involves objective rules, players must exercise "left brain" logical, sequential problem solving. However, to find the sets, players must examine the two dimensional arrangement of cards and locate patterns with "right brain" intuitive, spatial perception.

"To effectively employ creative thinking requires use of both left and right sides of your brain. Both right brain thinking skills, and whole brain thinking receive little attention in school. They remain underdeveloped as we go through life because only a few occupations such as a football quarterback, pilot, or artist require them. However, everyone will gain by developing them. Every time you find a set you are using your whole brain and increasing your potential to be creative."

The total number of cards in a SET deck is 81. This is the number of permutations of three variables that each take on three possible values [(3 numbers) * (3 colors) * (3 shapes) * (3 fills) = 81].

Twelve cards are initially displayed on the table. As players identify and pick up sets, the holes are filled by dealing replacement cards. The game is over when all the cards have been dealt, and no more sets can be formed. The maximum number of sets is 27. Because each individual card can participate in quite a few set, it is possible to find yourself at the end of the game with several cards that cannot be matched.

Set - and the software professional

I think programmer's are pathologically left-brain by nature: an algorithm for everything and everything in its algorithm, schema, flowchart, state machine, collaboration diagram, etc.

Only with conscious effort, do we aspire to, and mature in practicing, the art of abstraction. Grady Booch has suggested, "Only about 20-30% of software developers are probably really good at OO abstraction. That doesn't mean the remaining 70-80% are inadequate. Rather, this is a recognition of the fact that some people are better than others at looking at the world and discovering or inventing abstractions of reality."

The practice of abstraction can be strongly linked to the pattern recognition and spatial perception of right-brain thinking skills. The practice of programming (tied as it has been to sequence, selection, and iteration) is routinely prejudiced towards the logical orientation and linear perception of left-brain thinking skills. To succeed in our domains of ever expanding complexity, software architects and practitioners must integrate and leverage their "whole" brain.

Years ago, I heard a definition for innovation - the ability to see what everyone else has seen and think what no one else has thought. So much of this art referred to as "seeing" is really the ability to discern patterns that have heretofore gone unharvested. The SET game is an excellent vehicle for bolstering one's powers of discovery. Software design is a prime beneficiary of expanded powers of discernment.

To the degree that the act of software design remains a discipline characterized by creativity and craftsmanship, there is no substitute for multi-disciplinary powers of perception. Whether these additional dimensions of insight come from mathematical card games, or the competing world views of software design paradigms; every tool we can bring to bear on the systems we build will result in a whole that is greater than the sum of its parts.

Learn and leverage as many paradigms as possible.

The project

Start by building basic drawing functionality. Then introduce user interface and control functions. Finally, design and build the model that supports the business logic of the game.

The nine iterations are:

  1. Draw 12 blank cards
  2. Draw 9 cards - number, shape
  3. Draw 9 cards - number, shape, color, fill
  4. Encode the 4 dimensions and represent 81 cards
  5. Draw 81 cards
  6. Select, hilite, and remove 3 cards at a time
  7. Shuffle cards, build entire UI, count the number of sets found, refill holes
  8. Design the model, validate each set selected
  9. Compute all sets present, display the list of sets present
Iteration 3 is an interesting exercise in, I can name that song in 5 notes, Bob. How can you use indirection to draw one, two, three, red, green, blue, rectangle, X, O, open, striped, solid, and 12 cards in a compact function or two.?

Iteration 4 is a remarkable puzzle where insight and data structure will make all the difference. Once weve laid the foundation with an interesting representation, iteration 5 is easy.

How can the validity of a set be evaluated? Iteration 8 is another significant puzzle, and well discover an algorithm that can be implemented in nine lines of code.

Iteration 1

To get started, lets limit ourselves to drawing the outline of 12 cards. Use the following dimensions to get yourself started. We've previously discussed the practice of using symbolic constants to represent values that are likely to change.
Hard-wiring values produces weak spots in a design that are a lightning rod for change.
Instructions and issues:

Iteration 2

The AWT Graphics class allows shapes to be drawn using the method drawPolygon(polygonXs,polygonYs,numberOfPoints). The outline of the three types of shapes are given below. The first row draws a rectangle, the second row an O, and the final row an X.

The X offset for each shape in one, two, and three-shape cards are also provided.

In this iteration, develop the code for drawing two of our four dimensions: shape, and number. You will need to add together contributions from several data structures to draw each shape within each card.

Instructions and issues:

Iteration 3

Add the last two dimensions (color and fill) in this iteration. Use the drawPolygon(polygonXs,polygonYs,numberOfPoints) method for solid fill. For striped fill, use the relative coordinate arrays below. The fill dimension seems to be usually involved. The open fill and striped fill use two different arrays of relative X,Y values and the drawPolygon() instruction; while the solid fill uses the fillPolygon() instruction and the same relative X,Y arrays as the open fill.

Instructions and issues: How do you want to handle the two different sets of relative X,Y values? Do you need to keep them separate and use an if-else test to access the correct set; or, can you merge the two sets into one and compute the appropriate offset?

Iteration 4

Encode the 4 dimensions and represent 81 cards

All permutations of four 3-value variables

Instructions and issues:

Iteration 5

Draw 81 cards

Instructions and issues:

Iteration 6

Select, hilite, and remove 3 cards at a time

Instructions and issues:

Iteration 7

Shuffle cards, build entire UI, count the number of sets found, refill holes

Instructions and issues:

Iteration 8

Design the model, validate each set selected

Instructions and issues:

Iteration 9

Compute all sets present, display the list of sets present

Instructions and issues:

Iteration 1 - implementation

We need to draw four rows and three columns. We could use an inner loop for the columns, and an outer loop for the rows. Or - we could remove one level of bookkeeping, and use the modulus operator and integer division to achieve the same end. The "i%3" expression cycles through the values 0, 1, and 2. That is exactly what the inner loop did in the previous implementation. This could be described as a "saw-tooth function". Each time the modulus operator jumps back to 0, the integer division expression steps to its next level. That replaces the role of the outer loop.
Integer division is useful as a "stair-step function". The modulus operator yields a "saw-tooth function".
Listing 8.1

Iteration 2 - implementation

We could think of this problem in terms of applying several "overlays". At the highest level there is the position of each card. Then there is the position of each shape within a card. And finally, the X and Y arrays of each individual polygon. A top level loop is needed to iterate through the nine cards. A lower level loop can iterate through the number of shapes for each card. A third loop can apply the contribution from the other two loops to the most finest-grain component of each individual drawing instruction the X and Y vectors for each shape type. If we encapsulate the third loop in a function, then the return value of the function can report how many elements have been populated in the array parameters passed to the function. Notice that the modulus operator (i.e. saw-tooth function) is being used to visit all elements of the one23Xs array for each row; and the integer division operator (i.e. stair-step function) is used to hold the shape choice constant for each row. The computeShapeXYs() function is oblivious to all the decisions being made externally. Its sole responsibility is to iterate through the designated shapes relative positions, and compute absolute positions. The notion of "overlays" put forth at the beginning of this section reminds me of physiology textbooks that represent each sub-system of the human body on its own clear plastic page. The skeletal system, the circulatory system, the respiratory system, the digestive system, and the musculature can be studied in isolation – or – they can be overlayed and examined in concert. In software, this kind of approach has gone by many names: divide and conquer, separation of concerns, layers of abstraction, etc. We used it in this iteration to: decompose the complexity of drawing shapes on cards, and wield remarkable leverage with very little code.
Perspective is everything – separate concerns into "horizontal" layers, and at the last minute overlay them to produce a "vertical" solution.

Listing 8.2

Iteration 3 - implementation

Drawing the new dimension of color should be easy. Like we did with the dimensions of number and fill, lets create yet another array to hold the legal color values. If we wanted to hold the color constant for each row (like we are doing for the dimension of shape), then we would need the expression "i/3". But, the assignment called for varying color like we are already varying the dimension of number, so, the expression "i%3" is appropriate. For the dimension of fill, we could choose to create brand new data structures like the following. The fill dimension needs to cycle in step with the number and color dimensions, so the expression "i%3" will be necessary to compute array indices. When "i%3" is equal to 0, the fill should be open. When "i%3" is 1, the fill is striped. And "i%3" equal to 2 means a fill of solid. Since the fill affects how the polygon Xs and Ys are computed, the method computeShapeXYs() will need to change. asd asd The method paint() needs to decide whether to invoke drawPolygon() or fillPolygon(). Listing 8.3

Iteration 4 - implementation

Encode the 4 dimensions and represent 81 cards

Listing 8.4

Iteration 5 - implementation

Draw 81 cards

Listing 8.5

Iteration 6 - implementation

Select, hilite, and remove 3 cards at a time

Listing 8.6

Iteration 7 - implementation

Shuffle cards, build entire UI, count the number of sets found, refill holes

Listing 8.7

Iteration 8 - implementation

Design the model, validate each set selected

The problem at hand is: how to decide (or compute) whether any arbitrary combination of three Card objects (i.e. three entries from table 2) represent a set. One approach could be to loop through each of the three dimensions, and examine the corresponding digits for each dimension on all three Cards.

To this end, let's enumerate all combinations of the digits 0, 1, and 2 (leaving out all permutations that represent different orderings of the same data). The result would be table 3. The "012" column represents a "different" set; and the "000", "111", "222" columns are "same" sets. The first six columns of digits do not represent sets.

On a hunch, let's try adding each column. All the columns that represent sets are found to be evenly divisible by three. All the columns that don't represent sets are not. That is a remarkable property that significantly simplifies the evaluation of "set-hood".

Given this special "modulus" property, the implementation of the isValid() method is easy. An outer loop can iterate over the number of facets in our domain, and an inner loop can iterate over the number of Cards in a set. If the sum of any of the facets is not evenly divisible by three, then the current combination cannot be a set.

Listing 8.8

Iteration 9 - implementation

Compute all sets present, display the list of sets present

Listing 8.9