Problem Set 4: Comments

Design

The toughest challenge in designing a good solution to this problem is to find a way to avoid having all the complexity in one module. Many groups had designs that put almost all the difficult code in one module (usually for representing the board state). This makes it hard to divide the work, as well as to devise an implementation and testing strategy that can be done incrementally. A good design would allow you to develop and test modules independently.

To deal with this problem, my design separates the problem of knowing how positions on the board are connected from maintaining the state of a particular game. Hence, there are two modules associated with the board:

• Board — An immutable datatype that represents the board, but does not represent the state of the game. That is, it doesn't maintain anything to do with pegs. The most important method it provides is:

  public int getSquare(int start, Direction direction, int steps)
    // EFFECTS: Returns the number of the position that is reached starting
    //    from the start position, and moving steps number of steps in the
    //    direction.  If the resulting position is not on the board, throws
    //    NotOnBoardException.  If start is not on the board, throws
    //    NotOnBoardException.
  

• BoardState — A mutable datatype that represents a state in the game. BoardState includes:
  • A constructor that creates a board state containing no pegs;
  • Mutators for adding and removing pegs from the board, executing a jump on the board, and undoing a jump.
  • Observers that return the number of pegs on the board and a list of all jumps possible.

Another goal of our design is to be able to deal with the different kinds of jumps in the simplest possible way. In particular, we don't want to have to have six copies of the code for checking if a jump is possible in each of the six possible directions. Hence, we use a Direction module that is an immutable datatype for representing one of the six possible jump directions.

The top-level module, Solver provides a main method that reads in a configuration file and produces a BoardState object corresponding to that configuration file. Then, it calls the solve method which either returns a winning sequence of moves or throws an exception:

static public JumpList solve(BoardState b) throws NoWinnerException
  // EFFECTS: If it is possible to win from b, returns a sequence of
  //    moves that transforms b into a board with a single peg.  If
  //    no such sequence exists, throws NoWinnerException.
  //    (Note: the board with 0 pegs is a losing board.)

The remaining modules are for representing jumps (Jump, an immutable datatype) and lists of jumps (JumpList, a mutable datatype).

We leave producing a module dependency diagram as an exercise. Producing a correct MDD for our implementation is worth 20 bonus points.

Implementation and Testing Strategy

Nearly everything depends on the Board class, but it depends only on Direction. The only method that depends on Direction is getSquare, so first we implement all the other methods of Board and test them. The methods getSquareColumn and getSquareRow take a position number and return its column and row respectively. We can test these by using a for loop to try all squares on a 5-row board. Since its pretty tricky to get these right, and easy to test them all, its worth doing this. We should also check som positions that are not on the board. Similarly, the squareAt method can be systematically tested. (In my cases, these tests did reveal some bugs in my first implementation, such as miscounting the number of columns in a row.)

After that, we can implement Direction (which is a very simple class), and the getSquare (int, Direction, int) method in Board. This is a complicated method to implement correctly, and important to test by itself. If there are any problems in getSquare the puzzle solving code may fail produce incorrect results in mysterious ways.

To test the rest of the code, we tried running the solver on a variety of boards. If those tests did not produce the correct results, it would be necessary to test the other modules independently. In this case, since the solver produced the correct results (and a flaw in our program will cause me considerable embarrassment, but no national disaster), we decided it was not necessary to extensivle test the other modules independently.

Some input files to try:

• Boards with known winning solutions: the standard Cracker Barrel board, simple boards with 3 or 4 rows that a human can solve easily.
• Boards that have no winnning solutions: a board with two disconnected pegs, a board that has several legal moves, but no winning solution.
• An initial board with 1 peg.
• An initial board with 0 pegs (which we defined as a losing board).
• A large initial board with only a few pegs so it is clear how to win.

Finally, we tried running our program on a 7-row board with all pegs except one open hole. I left if running over night, but it didn't complete. This isn't surprising — the worst case amount of work required by our program grows exponentially with the number of pegs. The 7-row board has 27 pegs (2²⁷ = 134 217 728). Any student who can produce a program that can produce a solution for any 7-row board within 6 hours receives an automatic A in the course.

If having a correct Solver was safety-critical, we could test it more comprehensively. It is hard to look at a board and tell if it has a solution, but easy to check a solution if it is produced. We could write a program that takes a configuration file and the output from our solve and checks that it is correct. Then, we could write a program to generate a large number of random peg boards and check the results.

Implementation

The three most interesting modules are shown below. The complete code is available here: ps4-mine.zip.

Board

public class Board {
	// OVERVIEW: A Board is an immutable type that represents a peg board.  A 
	//     typical Board is the 3-row board
	//             1
	//           2   3
	//         4   5   6

	// Rep:
	private int numrows;

	// Abstraction Function:
	//    AF(r) =   the first numrows of
	//                      1     
	//                    2   3
	//                  4   5   6
	//                 7  8   9   10
	//                ...     

	//@invariant numrows >= 1

	//@requires p_numrows >= 1
	public Board(int p_numrows) {
		numrows = p_numrows;
	}

	//@ensures \result >= 1
	public int numberOfSquares() {
		// EFFECTS: Returns the number of squares on this board.
		return calculateNumberOfSquares(numrows);
	}

	//@ensures \result >= 1
	private int calculateNumberOfSquares(int rows) {
		// The one row board has 1 square:
		if (rows == 1) {
			return 1;
		} else {
			// A board with more rows, is a square, with the triangle
			// of one size smaller removed
			return (rows * rows) - calculateNumberOfSquares(rows - 1);
		}
	} //@nowarn Post // can't prove >= 1

	//@requires square >= 1
	public int getSquareRow(int square) throws NotOnBoardException {
		if (square < 1)
			throw new NotOnBoardException();
		int firstsquare = 1;

		for (int rowno = 1; rowno <= numrows; rowno++) {
			if (square - firstsquare < rowno) {
				return rowno;
			}
			firstsquare += rowno;
		}
		if (square <= numberOfSquares()) {
			Assert.error ("BUG: Should have found a row!");
		}

		throw new NotOnBoardException();
	}

	//@ensures \result >= 1
	// EFFECTS: If row, col is on the board, returns the square number
	//    corresponding to row, col.  Otherwise, throws NotOnBoardException.
	public int squareAt(int row, int col) throws NotOnBoardException {
		if (row < 1 || col < 1)
			throw new NotOnBoardException("squareAt: " + row + ", " + col);
		if (col > row) 
			throw new NotOnBoardException("squareAt: " + row + ", " + col);
		
		int squareno = 0;
		for (int rowno = 1; rowno < row; rowno++) {
			squareno += rowno;
		}

		squareno += col;
		
		Assert.check(getSquareRow(squareno) == row);
		Assert.check(getSquareColumn(squareno) == col);
		return squareno;
	}

	//@requires square >= 1
	public int getSquareColumn(int square) throws NotOnBoardException {
		if (square < 1)
			throw new NotOnBoardException();
		int firstsquare = 1;

		for (int rowno = 1; rowno <= numrows; rowno++) {
			if (square - firstsquare < rowno) {
				return (square - firstsquare) + 1;
			}
			firstsquare += rowno;
		}

		if (square <= numberOfSquares()) {
			Assert.error ("BUG: Should have found a row!");
		}

		throw new NotOnBoardException();
	}

	//@requires direction != null;
	//@ensures \result >= 1
	//         and \result <= numberOfSquares ()
	// EFFECTS: Returns the number of the position that is reached starting
	//    from the start position, and moving steps number of steps in the
	//    direction.  If the resulting position is not on the board, throws
	//    NotOnBoardException.
	public int getSquare(int start, Direction direction, int steps)
		throws NotOnBoardException {
		if (start < 1) throw new NotOnBoardException ();
		
		int startrow = getSquareRow(start);
		int startcol = getSquareColumn(start);

		int newrow;
		int newcol;

		if (direction.isEast()) {
			newrow = startrow;
			newcol = startcol + steps;
		} else if (direction.isWest()) {
			newrow = startrow;
			newcol = startcol - steps;
		} else if (direction.isNorthEast()) {
			newrow = startrow - steps;
			newcol = startcol;
		} else if (direction.isNorthWest()) {
			newrow = startrow - steps;
			newcol = startcol - steps;
		} else if (direction.isSouthEast()) {
			newrow = startrow + steps;
			newcol = startcol + steps;
		} else if (direction.isSouthWest()) {
			newrow = startrow + steps;
			newcol = startcol;
		} else {
			Assert.error ("Bad direction!");
			return 1; // Never reached 
		}

		return squareAt(newrow, newcol);
	} 

	// This is for testing only
	static public void main(String args[]) throws NotOnBoardException {
		Board b = new Board(5);

		System.err.println("Number of squares (15): " + b.numberOfSquares());
		for (int i = 1; i <= b.numberOfSquares(); i++) {
			System.err.println(
				"Square "
					+ i
					+ ": "
					+ b.getSquareRow(i)
					+ ", "
					+ b.getSquareColumn(i));
		}

		try {
			b.getSquareRow(b.numberOfSquares() + 1);
			System.err.println("ERROR: Should be off board!");
		} catch (NotOnBoardException e) {
			System.err.println("Off board: okay");
		}

		Additional testing code removed
	}
}

BoardState

import java.util.Enumeration;

public class BoardState {
	// OVERVIEW: BoardState is a mutable datatype that keeps track of the pegs on
	//     a board.  A typical board state is
	//                         o  
	//                        * *
	//                       * * *
	//                      * * * *
	//                     * * * * *

	// Rep:
	private boolean [] pegs;
	private Board board;

	//@invariant pegs != null;
	//@invariant board != null;
	// invariant All the elements of pegs are either 0, or unique positive integers.
	//           (0 can appear in pegs more than once, any other number can only appear once).

	// Abstraction Fuction:
	//   AF (r) =  
	//              p_1
	//           p_2    p_3
	//         ...
	//
	//    where p_i = '*' if pegs[i - 1] == true
	//          p_i = 'o' otherwise
	//

	//@requires b != null
	// EFFECTS: Creates a BoardState for board b with no pegs
	public BoardState(Board b) {
		pegs = new boolean [b.numberOfSquares()];
		board = b;
	}

	// EFFECTS: Returns true iff the location square contains a peg in this.
	//     
	public boolean containsPeg (int square) throws NotOnBoardException {
		if (square < 1 || square > pegs.length) {
			throw new NotOnBoardException ();
		}
		
		return pegs[square - 1];
	}
	
	// EFFECTS: Adds the square to this.
	public void addPeg(int square) throws NotOnBoardException {
		if (square < 1 || square > pegs.length) {
			throw new NotOnBoardException ();
		}
		
		pegs[square - 1] = true;
	}
		
	// REQUIRES: square is in this.
	// EFFECTS: Removes a peg at square from this.
	public void removePeg(int square) throws NotOnBoardException {
		if (square < 1 || square > pegs.length) {
			throw new NotOnBoardException ();
		}
		
		pegs[square - 1] = false;
	}		
		

	// EFFECTS: Returns the number of pegs in this.	
	public int numPegs() {
		int count = 0;

		for (int i = 0; i < pegs.length; i++) {
			if (pegs[i])
				count++;
		}

		return count;
	}

	//@requires jump != null
	// REQUIRES: jump is a legal jump on this.
	// EFFECTS: Modifies this reflect executing jump.  this_post is the
	//    board the results from executing jump on this_pre.	
	public void executeJump (Jump jump) {
		try {
			removePeg (jump.getStart ());
			removePeg (jump.getHop ());
			addPeg (jump.getLand ());					
		} catch (NotOnBoardException nbe) {
			Assert.error ("BUG: jump is not on the board");
		}
	}
	
	//@requires jump != null;
	// REQUIRES: jump is a legal "reverse" jump on this.
	// EFFECTS: Modifies this to the board before taking jump.  this_post is the
	//    board the from which this_pre would result after taking jump.	
	public void reverseJump (Jump jump) {
		try {
			addPeg (jump.getStart ());
			addPeg (jump.getHop ());
			removePeg (jump.getLand ());					
		} catch (NotOnBoardException nbe) {
			Assert.error ("BUG: jump is not on the board");
		}
	}

	//@requires jump != null;
	// REQUIRES: jump would be a legal jump on the board, if the
	//              first and second squares have pegs, and the
	//              third square is empty.
	// EFFECTS: Returns true if jump is a legal jump on this.
	private boolean legalJump (Jump jump) {
		try {
			return (containsPeg (jump.getStart ())
					&& containsPeg (jump.getHop ())
					&& !containsPeg (jump.getLand ()));					
		} catch (NotOnBoardException nbe) {
			Assert.error ("BUG: jump is not on the board");
			return false;
		}
	}
	
	// EFFECTS: Returns a list of all jumps possible on this.
	//@ensures \result != null	
	public JumpList possibleJumps() {
		JumpList res = new JumpList();

		// For each peg, find all the possible jumps for that peg
		for (int i = 0; i < pegs.length; i++) {
			if (pegs[i]) {
				// Try each direction
				int startsquare = i + 1;

				for (Enumeration dirs = Direction.allDirections();
					dirs.hasMoreElements();
					) {
					// We can jump in direction d
					Direction d = (Direction) dirs.nextElement(); //@nowarn Cast
					//@assume d != null
					try {
						int middlesquare = board.getSquare(startsquare, d, 1);
						int endsquare = board.getSquare(startsquare, d, 2);
						Jump jump =
							new Jump(startsquare, middlesquare, endsquare);
						if (legalJump(jump)) {
							res.add(jump);
						}
					} catch (NotOnBoardException nbe) {
						// Not a legal jump - would fall off the board

					}

				}

			}
		}
		return res;
	}
}

Solver

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Enumeration;

public class Solver {
	// OVERVIEW: Solver is the top-level class.  It provides methods for
	//     reading in a board, and solving the game.

	// EFFECTS: If it is possible to win from b, returns a sequence of
	//    moves that transforms b into a board with a single peg.  If
	//    no such sequence exists, throws NoWinnerException.
	//    (Note: the board with 0 pegs is a losing board.)
	//@ensures \result != null 
	//@requires b != null
	static public JumpList solve(BoardState b) throws NoWinnerException {
		JumpList jumps = b.possibleJumps();

		for (Enumeration e = jumps.elements(); e.hasMoreElements();) {
			Jump j = (Jump) e.nextElement(); //@nowarn Cast
			//@assume j != null
			// Try this jump
			b.executeJump(j);
			// See if there is a winning solution
			JumpList winningmoves;

			try {
				winningmoves = solve(b);
			} catch (NoWinnerException nwe) {
				continue; // Try the next possible jump
			} finally {
				b.reverseJump(j);
				// Reverse the jump (restore b to its original state)
				// Note ths finally block will run after the try and catch blocks, whether
				// or not the exception is caught.
			}

			// There is a winning sequence: add this jump to the front of it, and return:
			winningmoves.insertJump(j);
			return winningmoves;
		}

		// Tried all moves
		if (b.numPegs() == 1) {
			// If there's one peg, its a winner
			return new JumpList();
		} else {
			throw new NoWinnerException();
		}
	}

	static public void errorExit(String msg) {
		System.err.println(msg);
		System.exit(-1);
	}

	//@requires args != null
	static public void main(String args[]) {
		if (args.length != 1) {
			errorExit("Usage: java Solver <configuration file>");
			return;
		}

		String cfile = args[0];
		BufferedReader reader;
		try {
			reader = new BufferedReader(new FileReader(cfile));
		} catch (FileNotFoundException e) {
			errorExit("Error: cannot open configuration file: " + cfile);
			return; // Compiler can't figure out errorExit never returns
		}

		String firstline;
		try {
			firstline = reader.readLine();
		} catch (IOException e1) {
			errorExit("Error: problem reading first line: " + e1);
			return;
		}
		int numrows = Integer.parseInt(firstline);

		if (numrows < 1) {
			errorExit("Error: the first line of the configuration file must be a number >= 1.");
			return;
		}

		Board b = new Board(numrows);
		BoardState bs = new BoardState(b);

		int rowno = 1;
		int pegno = 0;
		int inchar;

		try {
			while ((inchar = reader.read()) != -1) {
				char c = (char) inchar;

				if (c == ' '
					|| c == '\t'
					|| c == '\r') { // skip whitespace characters
				} else if (c == '\n') {
					rowno++;
				} else if (c == '*' || c == 'o') {
					pegno++;
					if (c == '*')
						bs.addPeg(pegno);
					if (b.getSquareRow(pegno) != rowno) {
						errorExit(
							"Row "
								+ rowno
								+ " in the configuration file "
								+ cfile
								+ " contains the wrong number of pegs.");
					}
				} else {
					System.err.println(
						"Skipping unrecognized character in configuration file: "
							+ c);
				}
			}
		} catch (IOException e2) {
			errorExit("Error: IO error reading file: " + e2);
		} catch (NotOnBoardException e2) {
			errorExit(
				"The configuration file contains too many pegs.  Read peg "
					+ pegno
					+ ".");
		}

		if (pegno != b.numberOfSquares()) {
			errorExit(
				"The configuration file does not contain enough information.  Only "
					+ pegno
					+ " peg or holes,  when "
					+ b.numberOfSquares()
					+ " is expected.");
		}

		System.out.println(
			"Read board containing " + bs.numPegs() + " pegs...");

		try {
			JumpList winning = solve(bs);
			System.out.println("Winning moves: " + winning);
		} catch (NoWinnerException nwe) {
			System.out.println("There is no winning sequence for the board.");
		}
	} //@nowarn Exception
}

University of Virginia Department of Computer Science CS 201J: Engineering Software

Sponsored by the National Science Foundation

cs201j-staff@cs.virginia.edu