Peg Game

The Peg Game consists of fifteen holes arranged in a triangle, and fourteen pegs. The object is to remove pegs by jumping until one peg remains. A "jump" consists of: finding two pegs and a hole in a row (either horizontally or diagonally), jumping the outer peg over the inner peg and into the hole, removing the jumped peg. It is all too easy to run out of jumps before you run out of pegs. Leaving five pegs on the board is below average, while three pegs is fairly average. The player chooses where the empty hole is positioned before play is begun.

The project

Write an implementation that supports the demonstrated DOS user interface. Next, we will design and implement two different applications that identify winning game sequences. Finally, one of these solution programs will be adapted and integrated into the original game so that the player is restrained from making moves that have no hope of achieving one peg remaining.

The next chapter will do for this puzzle what the previous chapter did for the Fifteen Puzzle.

Three iterations:

  1. draw board
  2. select peg and remove or reinstate
  3. remove, (from to)

Iteration 1

Let's start with drawing the board once and exiting. No input or move functionality. Instructions and issues:

Iteration 2

In this iteration, add a user interaction loop. Ask the user to identify which peg to remove (or reinstate), and update the board to reflect its new state. If the user enters an empty string, exit the loop. Instructions and issues:

Iteration 3

Refactor the current implementation to allow the user to play a complete game. Ask the user which peg should be removed to start the game. Thereafter, solicit each move as a "from to" pair. If the request constitutes a valid move, then remove the "from" peg and the "jumped" peg, and add the "to" peg. Instructions and issues:

Iteration 1 - implementation

Generating the character sequence 'A' through 'O' could have been implemented with character arithmetic. The choice made in listing 4.1 was to exercise Java's support for the increment operator on a char variable.

Notice how the number of iterations of the inner loop is controlled by the loop control variable of the outer loop.

The indentation for each row could be implemented using the following array of five blank strings. The choice made in listing 4.1 was to minimize the amount of storage used, and compute the correct size blank string each iteration. The String class in Java's standard library has two forms. The one used here is substring( beginIndex ). As the variable row increases, the amount of indentation decreases. The first alternative above relies on the use of memory, or storage. The second uses considerably less storage, but requres more instructions, or processing. Very often, a choice must be made between "store versus compute". The former incurs more memory overhead and less overhead in compute cycles. The latter has the opposite trade-offs. The correct choice is always driven by which of these two finite resources is in shorter supply.

When faced with a "store versus compute" dilemma, always choose the one that involves the least "pain".

Listing 4.1

Iteration 2 - implementation

The implementation in listing 4.2 has chosen an one-dimensional array of booleans to maintain the state of the application. Each hole in the board is represented by an element in the array. Whether a peg is present in a given hole is represented by a true or false value assigned to the corresponding array element.

A two-dimensional array, with the second dimension growing in length, could have been chosen instead of a 1D array. This might seem like a more natural mapping of the problem space on to our solution space. The trade-off is having to specify an "x" and a "y" in order to designate a hole location. Down the road, when we have to think about representing/capturing a "move" with some data structure, two integers will be required instead of just one. Additionally, people are already comfortable talking about pins one through ten in the game of bowling. So, identifying pegs with the numbers one through fifteen, seems easier and more natural.

When a character is input by the user, it is converted to an array index with the expression "(int) input.charAt(0) - 'a'". This converts the character range 'a' through 'o' into the integer range 0 through 14. It is a common problem solving technique to transpose a problem from its original domain (or perspective, or paradigm) to a seemingly unnatural domain, in an effort to find a solution.

An example is the addition of "vectors". A vector is a mathematical abstraction of a quantity that has both magnitude and direction. Wind is reported as a vector: 10 knots from the south. The polar coordinate system is natural for modeling vectors. Adding one vector to another in polar coordinates is hard. But - adding vectors that are modeled in the cartesian cooridinate system is easy.

Drawing the board has been encapsulated in a new display() function. Now that upper and lower case are required, the character arithmetic expressions "(char)('A'+i)" and "(char)('a'+i)" are being used. Knowing whether to output "" or " a " is a simple matter of accessing the value of the first element of the pegsPresent array.

Listing 4.2

Iteration 3 - implementation

Since moves can go up, down, and across the board, there doesn't seem to be any apparent algorithm for computing a legal move. The total number of legal moves is remarkably finite. There are only two legal moves possible from each position, except for the middle position on each side, where there are four possible moves. That means there are a maximum number of 36 moves. This volume of data is entirely reasonable to enumerate.

We might be tempted to eliminate all "duplicate" entries (i.e. jumping from position 1 to 4, or from position 4 to 1). But a move is not symmetric. Jumping from 1 to 4 means that positions 1 and 2 must be occupied, and position 4 must be empty. Whereas, jumping from 4 to 1 means that positions 4 and 2 are occupied, and position 1 is empty. So let's keep all 36 moves in our data structure.

A move can be captured with three integers: "from" position, "to" position, and "jumped" position. This means all possible moves can be captured in an int[36][3] data structure. See the jumpTable attribute in listing 4.3.

We could write a legalMove() function that returns true or false; but do we really need to know if a move request is not legal? What about writing an attemptMove() function that simply updates the pegsPresent attribute when the move request is legal, and does nothing otherwise?

The computation of the "from" and "to" positions in the main() of listing 4.3 generates values 0 through 14. The jumpTable attribute uses values 1 through 15. The "from" and "to" parameters passed to attemptMove() must be incremented before they can be used.

Given the specified "from" and "to" positions, how do we validate that they represent a valid jump? If we find those two values in the jump data structure, then we have part of our answer. How do we want to "search" the jump data structure? Sequentially stepping through the list of 36 moves is certainly easy, but is that choice prudent. Given that this search will only happen once for each user request, trying to identify an algorithm better than sequential search does not seem worth the effort.

The attributes common to great programmers are: hubris, resourcefulness, and laziness.

What we have so far is -

But, is that all? If the "to" position has a peg sitting in it, then we can't honor the move request. The same is true if the "from" and "jumped" positions do not have pegs in them. This means the if condition needs to be extended.

Where is the knowledge of filled and empty positions? In the pegsPresent data structure. What do we need to use that data structure? An index, or offset, that represents a peg/hole position. Do we have any of that information at our disposal? Yes, in the {a,b,c} elements of the jumpTable data structure. What do we need to use that data structure? Two indexes, or offsets, that represent: a move, and a position within that move.

Once we have found the move data structure that corresponds to the user's request, then we need to check if: the "from" position is filled, the "jumped" position is filled, and the "to" position is vacant.

While this is more explicit than the implementation chosen in listing 4.3, perhaps it is more verbose than necessary - if - the more compact code is well documented.

The process we just went through to repeatedly ask: what do I know, and what do I need; could be characterized as a brute force approach, or "focusing on the trees". A lot of energy was invested in chapter 1 to discourage this kind of approach. Perhaps the reconciliation of this apparent contradiction would be to suggest: when you find yourself socked-in with a low ceiling and limited visibility, you should not be embarrassed to feel your way from one tree to the next.

"You can't get there from here" is fairly common advise. But, with enough tenacity, you can usually "find a way or make one." Consider the following cynical characterization of life.

The original intent was to assert, "The only way to get from here to there is always the long way around." Perhaps a more redemptive perspective would be to suggest, "You can always get from here to there with enough tenacity and resourcefulness." Listing 4.3