Problem Set 4: Designing with Data Abstractions

Out: 26 September 2003 Design Document Due: Thursday, 2 October (beginning of class, two copies) Final Due: Tuesday, 16 October (beginning of class)

Collaboration Policy - Read Carefully

For this problem set, you are required to work in an assigned team as shown below. Unlike other assignments, your group should strive to divide the work in such a way that you can work independently on different parts, and combine your work to solve the problem. In your design document, you will document each member's role.

Abul Kalan ak4f Kian Keyvanfar kk9t William Ingram wai9z	Anna Capetanakis ac6cd Irina Golub ErinGolub Tuan Vu tv7z	Nancy Fechnay nlf6b Christopher Cutrona csc5r Hyun Jong Hong hjh9d	Sam Baumgardner scb7b Stephen Guy sjg5m Dan Laufer dl9h Debora Wesner dtw4e	Craig Pratsch cp9x Guy-Robert Duval gd4b Laura Paulsen lep4f Patrick Rooney pjr2y
Ryan Eagan rme3d Brian Annes baa2j James Layman layman Yohan Kim yk7e	Christine Pearce cep6z Jacosta Silvers jas4xj Steven Li ssl5b	Danielle Fallon df8m Hope Tuck ht8a Raquel Johnathan rdj2f	Donald Conner dec3s James Kulina jk2af Neil Guha png4v	Doug Stewart dds9e Jasjeev Sawhney jss8b Patrick Johnston pnj9t
Elizabeth Verell ekv4r Jimmy Benani jcb7y Nitin Chandra nitin	Eric Kobe ek4t Joseph Burns jcb7j Marija Cvijetic mc6sb Melissa Thomason mbt3w	Frank Gilmore ross Heather McGinness ham5c Landon Shoop lhs8v Marshall (Beau) Ordemann beau	Amin Mehr am3cf Isabelle Estripeaut ie2g Benjamin Hoover bnh3x Deniz Kustu kustu	Kevin David kevin.davis Chad Gallagher cjg5f Thomas Kuklinski tk4m Nicholas Kristoff nmk7f
Lauren Foster lef3v Ryan Tiffany rt7m Michael Packer Jr. mwp5c Karen Yeung kly2b	Atul Khosla atulk Julia Lancaster jal8x Raul Maynigo rmm3g Cemi Almazlinos ca9d

Reading: Chapter 13 (except Section 13.11, we won't cover Data Models).

Purpose

• Learn to solve a problem by designing using data abstractions.
• Learn to design and implement data abstractions.
• Prove you are a genius next time you go to Cracker Barrel.

In Problem Set 3, you implemented a data abstraction given a specification. In this assignment, you will design and implement several data abstractions to solve a complex problem. It is up to you to decide what those data abstractions are.

Problem

The Cracker Barrel peg game is a one-player game played on a board containing fifteen holes. The game begins with one hole empty and the other holes filled with pegs. The goal is to remove all but one of the pegs by jumping pegs over one another. A peg may jump over an adjacent peg only when there is a free hole on the other side of the peg. The jumped peg is removed.

As anyone who has ever attempted to solve the peg game can appreciate, it is difficult to win. For this assignment, you will develop a program that takes as input a position on a peg board, and produces as output a sequence of jumps that wins the game (leaves a single peg), if such a sequence is possible, or a message indicating that there is no winning sequence.

Your program should take one parameter that is the name of a file containing an initial board configuration. The first line in the file contains a number n that indicates the number of rows on the peg board. The remainder of the file contains n lines. Each character is one of:

• * — a peg board hole that contains a peg
• o — a peg board hole that is empty peg)

For example, the standard Cracker Barrel peg board initial configuration with the top peg missing is represented by:

5
    o
   * *
  * * *
 * * * *
* * * * *

Spaces in the input are ignored. We use spaces to make the board above appear as a triangle, but the input file below is equivalent:

5
o
**
***
****
*****

Your program may reject input files that are not in the shape of a triangle. If the input file format is incorrect, your program should print a helpful error message and exit. Note that the format is incorrect if the number in the first line does not match the number of rows in the file.

Otherwise, your program should either output a winning sequence of jumps if one exists, or a message indicating that there are no winning sequences.

A solution to a peg board puzzle is a sequence of jumps that leaves a single peg on the board. We can describe a solution by numbering the squares on the board starting from the top. For the example above, the squares are:

         1
       2   3 
     4   5   6 
   7   8   9  10 
11  12  13  14  15

Your program should print out one of the winning sequences by printing out each jump as the position of the peg that starts the jump, and the landing position.

For example, is the input is:

3
    o
   * *
  * * *

Your program should output

No winning sequences

If the input is,

3
    o
   * *
  * o o

your program should output

4-1
1-6

There may be several possible winning solutions for a given initial configuration. Your program may output any legal solution. If there is no possible solution, your program should output a message indicating that there is no winning solution.

Hints

One way of solving a peg board puzzle is to try all possible legal jumps, and then try all possible legal jumps on the resulting boards.

Starting with the example board, there are two possible legal jumps:

1. The peg in position 4 jumps over the peg in position 2, landing in position 1.
2. The peg in position 6 jumps over the peg in position 3, landing in position 1.

After choice 1, the board would look like this:

    *
   o *
  o * *
 * * * *
* * * * *

Now, we have three possible jumps:

1. 11 jump 7 into 4
2. 6 jump 5 into 4
3. 13 jump 8 into 4

If we recursively try solving each board that results, some choices will lead to winning positions. Searching all possible boards and moves until a winning position is found, or all possibilities have been exhausted without finding a winner.

Design Document

A design document is due on Thursday, 2 October. You should bring two copies of your document to class on 2 October.

It should contain:

• A modular dependency diagram showing the classes you will use to implement your solution.
• Specifications of those classes. All your class specifications should include an overview (that describes the data abstraction, its mutability, and introduces an abstract notation) and specifications for the public operations of the class.
• Work division. Description of who will implement each class in your design, devise unit testing strategies and test cases for each important class, and devise integration testing strategies and test cases.

Final Report

On Tuesday, 16 October turn in a final report containing:

• The four parts of your design document, with explanations of any changes between your proposed design and the final design:
  • A modular dependency diagram showing the classes you will use to implement your solution.
  • Specifications of those classes. All your class specifications should include an overview (that describes the data abstraction, its mutability, and introduces an abstraction notation) and specifications for the public operations of the class.
  • Work division. Description of who will implement each class in your design, devise unit testing strategies and test cases for each important class, and devise integration testing strategies and test cases.
  • Descriptions of your representations, rep invariants and abstraction functions for those classes. If you changed your mind about any of the representations since the design document, explain why.
• All the code you wrote to implement your program. Each datatype implementation should include a rep invariant and abstraction function, documented in comments in the code. Your code should be annotated with ESC/Java annotations, and checked by ESC/Java. Submit your code using the web submission form.
• An explanation of how you tested your code. This is not a list of all the test cases you tried, but an explanation of what you did to validate your code. Include any interesting programs you developed to help your testing.

Credits: This problem set was developed for UVA CS 2001J Fall 2003. We used a version of the Peg Board game for an excercise in CS200 Spring 2003. You can learn more about the Peg Board game from http://www.cs.virginia.edu/pegboard/.

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

Sponsored by the National Science Foundation

cs201j-staff@cs.virginia.edu