Teaching Programming
http://www.vincehuston.org/teaching
Vince Huston

Games and puzzles   Consider:
  1. You can never have too many exercises, case studies, or activities.
  2. Domain-specific algorithms and data structures occur every day in the workplace. They should be discussed early and often in school.
Games and puzzles address both of these opportunities.

Logic activities

Mastermind ... Guess the 4 random colors selected by the program. Putting too many colors (and the responses) in play too early makes it very difficult to organize a scheme for drilling down to the answer.

Set Game ... Exercises both halves of the brain: the logical hemisphere (analytical thinking), and the holistic thinking hemisphere (perceive and interpret complex patterns). Given 12 cards: find a set of 3 cards that satisfy the criteria of a set across 4 dimensions (number, color, shape, and fill).

Peg Game ... Jump and remove pegs until one peg remains. The program evaluates each requested jump, and does not allow a jump that would result in more than one peg remaining when all possible jumps have been exhausted.

Decrypt ... Recover the original quote by identifying how each letter in the cipher stands for another.

Towers of Hanoi ... Move 5 disks from the first peg to the third peg by: moving one disk at a time, and never putting a larger disk on top of a smaller disk.

Grid Game ... Find the target in a 10x10 grid. A very simple game that is remarkably engaging.

  


 Input: 1 1 2 2
                  2  1 
 Input: 4 4 6 6
                  1  0 
 Input: 1 4 1 2
                  1  1 
 Input: 2 1 6 2
                  4  0
Programming projects

Mastermind ... A GUI is hard, but a command line interface (using digits 1 through 6) is very straight-forward (above and to the right). Computing the "totally correct" response is easy. Computing the "partially correct" response may seem too advanced for the beginner; but I propose it is an interesting algorithm puzzle.

Cracker Barrel Peg Game ... How should jump requests be validated and implemented? Is it algorithm, or data structure, or both?

Alphametics (solving addition problems where numbers have been replaced with letters) ... How would you solve this puzzle with pseudocode? Is it reasonable to address this puzzle by evaluating all possible combinations or permutations? Which is needed: combinations or permutations? What is the formula for computing the total number of combinations/permutations?

Set Game ... Algorithm: how to decide whether 3 cards constitute a set. Algorithm: how to compute all the sets present in an array of 12 cards. Is it reasonable to evaluate all combinations (or permutations?) of 12 cards taken 3 at a time?

Decrypt ... Design the data structure(s) and layer(s) of indirection that make the encryption and lookup straight-forward.

Fifteen Puzzle, Towers of Hanoi, and Grid Game are fairly ambitious with a GUI **but** they are very straight-forward with a command line interface.

Fifteen Puzzle

Introductory opportunities   Data structure opportunities   Algorithm opportunities
  • cout and a loop to print a row
  • 2 loops to print the "board"
  • std::setw() to right-justify numbers
  • conditional expression and a single loop to print board
  • ternary operator, integer arithmetic, and a single loop to print board
  • array to hold board "state"
  • 2D [4][4] array or 1D 16-element array
  • mapping numbers to positions
  • supporting the "never disturb any previously positioned number" strategy
  • move number
  • mix up the numbers
  • move several numbers at once (recursion)
  • support user-defined width and height
  • compute edge conditions instead of using lots of logical expressions

    • Mastermind

    Introductory opportunities   Data structure opportunities   Algorithm opportunities
  • cout and cin to prompt for and receive input
  • loop until puzzle is complete
  • encapsulate "evaluate guess" as a function
  • beside the answer array, are there auxiliary
    data structures that are necessary
  • compute the "black" response
  • compute the "white" response

    • Grid Game

    Introductory opportunities   Data structure opportunities   Algorithm opportunities
  • cout and loops to print the board
  • std::setw() to right-justify
  • sprintf to perform integer-to-string conversion
  • stringstream to perform integer-to-string conversion
  • introduce vector to replace arrays
  • use class to encapsulate the puzzle engine
  • how to represent the state of the board
  • how to calculate "delta X plus delta Y"
  • roll-your-own right-justification

    • Peg Game

    Introductory opportunities   Data structure opportunities   Algorithm opportunities
  • cout and a loop to print the board
  • cout and cin to prompt for and receive input
  • is "validate a requested move" a data structure issue?
  • is "validate a requested move" an algorithm issue?
  • how to evaluate if requested move is ill-advised (e.g. search a table of winning puzzles, try thousands of random moves, build an exhaustive puzzle tree)
  • recursion – depth first search
    •  

    Set Game

    Introductory opportunities   Data structure opportunities   Algorithm opportunities
  • use a loop and random numbers to shuffle the cards
  • decomposition into many functions (i.e. methods)
  • how to represent the color/number/shape/fill value of each card
  • do color/number/shape/fill values need to be stored, or can they be computed as needed?
  • how to decide whether 3 cards constitute a set
  • how to compute all the sets present in an array of 12 cards
  • in that computation: are you enumerating all combinations or all permutations?
    •  

    Alphametics

    Introductory opportunities   Data structure opportunities   Algorithm opportunities
  • not an easy problem
  • arrays (in spades)
  • map
  • new
  • next_permutation()
  • C command line arguments
  • use of an "off the shelf" object
    		•
  • multiple levels of indirection
  • a map that holds the association between a character and its corresponding position in an integer array that represents the current guess
  • support a variable number of terms
  • implement "all permutations of all combinations of 10 digits taken N at a time"
  • is_guess_valid()
  • get_value_for_word()
  • print_word()

    • Towers of Hanoi

    Introductory opportunities   Data structure opportunities   Algorithm opportunities
  • not an easy problem
  • implement each "peg" as an instance of a class
  • implement each "peg" as a stack
  • recursion
  • how to represent the behavior of the solution
    with a "DOS command line" user interface