Project 0: Signpost

Introduction

This initial programming assignment is intended as an extended finger exercise: a mini-project rather than a full-scale programming project. The intent is to give you a chance to get familiar with Java and the various tools used in the course.

We will be grading solely on whether you manage to get your program to work (according to our tests) and to hand in the assigned pieces. There is a slight stylistic component: the submission and grading machinery require that your program pass a mechanized style check (style61b), which mainly checks for formatting and the presence of comments in the proper places. See the style61b guide for a description of the style it enforces and how to run it yourself.

First, make sure that everything in your repository is properly updated and checked in. Before you start, the command

cd  ~/repo
git status

should report that the directory is clean and that there are no untracked files that should be added and committed. Never start a new project without doing this.

To obtain the skeleton files (and set up an initial entry for your project in the repository), you can use the command sequence

git fetch shared
git merge shared/proj0 -m "Get proj0 skeleton"
git push

from your Git working directory. Should we update the skeleton, you can use the same sequence (with an appropriate change in the -m parameter) to update your project with the same changes.

On the instructional machines (only), you can run the staff version of this program with the command

 staff-signpost

It takes the same options as your project (see Instrumentation and Testing).

The Puzzle

The puzzle game Signpost is one of Simon Tatham's collection of GUI games (available on a variety of operating-system configurations, including Ubuntu.) He attributes the puzzle to Angela and Otto Janko, who call it Pfeilpfad (arrow path). In this mini-project, you are given an incomplete Java program that creates these puzzles and allows its user to solve them, and you must supply the missing parts to complete the implementation.

The puzzle itself is quite simple. It is played on a $W\times H$ rectangular grid of square cells. All but one of the squares is annotated with an arrow pointing horizontally, vertically, or diagonally. The remaining square—the goal—is annotated with a star. Some squares contain distinct numbers between 1 and $W\cdot H$. The first and last squares in sequence (those numbered 1 and $W \cdot H$) are always numbered. The puzzle may be set to have free ends, in which case the first and last squares may appear anywhere on the board. By default, there are no free ends and the first and last squares are in the upper-left and lower-right corners, respectively. The idea is to connect the squares into a sequence from square 1 to $W \cdot H$. Each square is connected to another that is in the direction of its arrow such that all the squares are connected. If a square initially has a number, it must be the number of that square in the sequence of connected squares.

The diagrams below show a sample puzzle on the left and its solution on the right. The bottom-left corner of the board has the coordinates $(0, 0)$, with the positive x-axis running horizontally to the right, and the positive y-axis running vertically upwards.

To connect two squares, press and hold on the first in sequence and drag to the second. To disconnect them, press and hold on the first, drag to a position off the grid, and release.

Program Design

The skeleton exhibits a design pattern in common use: the Model-View-Controller Pattern (MVC).

The MVC pattern divides our problem into three parts:

• The model represents the subject matter being represented and acted upon—in this case incorporating the state of a board and the rules by which it may be modified. Our model resides in the Model and Place classes.
• A view of the model, which displays the puzzle state to the user. Our view resides in the GUI and BoardWidget classes.
• A controller for the puzzle, which translates user actions into operations on the model. In our case, it also notifies the view when the model has been modified. Our controller resides mainly in the Controller class, although it also uses the GUI class to read mouse clicks.

Your job for this project is just to modify and complete the Model, Place, PuzzleGenerator, and BoardWidget classes. We've marked places that need attention with comments containing "FIXME" (the style checker will point these out to you should you forget to fix one). Don't let that stop you from looking at all the other code in the project. That's actually part of the point of giving you the skeleton. You can learn a great deal about programming by reading other people's programs.

In fact, you can change other source files if you want, just so long as the program continues to behave the same when tested.

Initially, the skeleton contains some dummy code so that when run, you'll see a board, although you won't be able to do anything with it to speak of.

Instrumentation and Testing

To facilitate automated testing of your work, there are a few features that you can use to record sessions and to play back moves for testing or debugging purposes. The skeleton is set up so that when you start your program with

java -ea signpost.Main --log

you'll get a record on the standard output of all of the edges clicked, all the randomly created puzzles, and all the menu commands entered. Typically logs would be printed to the terminal, but one might want to save them to a file which can be done by capturing a log through redirection. You can capture logs using redirection, like this:

java -ea signpost.Main --log > testing/myscript1.in

The --seed option will allow you to prime the random number generation so that you can get the same set of random numbers each time:

java -ea signpost.Main --seed=42

The same seed produces the same random sequence, which will make the puzzle deterministic. This way bugs and other behavior can be reproduced.

The --testing option reads in a script produced by --log and uses it (in place of user clicks and random numbers) to supply the results of getPuzzle and getCommand. It also prints out a textual display of the initial board and after each command, which Tester.py can use to test the program. For example, to read back the file myscript1, use

java -ea signpost.Main --testing < testing/myscript1.in

This will print out what tester.py sees, which it compares to testing/myscript1.out. Using --log and --testing, you can thus create your own .in and .out testing files to augment the ones we've provided in testing.

We have set up the Makefiles in the proj0 directory and in the signpost subdirectory to have targets check and unit. In order to use make, you'll need to install it. Follow the instructions here to do so.

Once installed, the command

make unit

will run unit tests on Model.java. A unit test checks a particular unit of a program—typically a method or small group of methods. If you try this on the skeleton, you'll see that, unsurprisingly, it fails all these tests, giving you an indication of what needs to be changed.

In addition, make check in the proj0 directory will run integration tests, which run the program and check its outputs against expected output using the scripts tester.py and testing.py in the testing subdirectory. By the time you finish the project both make unit and make check should report no errors.

Getting Started

This project is largely an exercise in reading someone else's program and understanding its intent, which is actually a common activity in "real-world" programming as well. While you can, in fact, scrap everything and start from scratch (you are free to change files other than Model.java), you certainly should not do so simply because you don't understand the skeleton provided.

You'll see numerous uses of parts of the Java library we haven't talked about. However, you have seen all these data structures in Python. Where Python has lists, Java has arrays, ArrayLists, ArrayDeques, and LinkedLists (among others). Where Python has dictionaries, Java has HashMaps and TreeMaps. Where Python has sets, Java has HashSets, TreeSets, and BitSets. Where Python uses "duck typing"—as when it calls something a sequence because we can apply generic operations like len and map to it and iterate over it—Java explicitly identifies supertypes of its various library types, such as List, Set, and Collection. These and many more library classes are all defined in the online Java library documentation, which should constitute much of your bedtime reading for this semester.

A reasonable first step is to understand what Place and Model are supposed to do and what the comments on each of their methods are supposed to mean. You might ask, "but how can I understand it unless I know how it's being used?" It certainly helps to understand its use, but you should start developing the ability to understand and work on modules in isolation, one aspect of the "separation of concerns" that makes the construction of large systems possible. Also, we've gone to some pains to provide comments that actually indicate what things do (in sharp contrast, I fear, to standard practice these days). We'd like you to get into the habit of doing the same.

Reading and trying to understand these files and comments before beginning programming will be well worth the time. Spending up-front time before writing code can feel a bit counterintuitive at first. If you begin writing code before making an attempt to understand the preexisting code, you will likely struggle more. You need not understand every line of the given code, but you should strive to understand the different objects, their instance variables, what their instance methods do, and how the methods relate to one another. The comments in line with the methods and instance methods are a great way to begin learning about the code. Feel free to read these, discuss with classmates, and ask questions as they arise.

We have marked places where code needs to be added with // comments containing the work FIXME. These appear in the classes Model, Place, and PuzzleGenerator. There is also one trivial FIXME in BoardWidget, which is only there as a stopgap to make the initial skeleton display something. Generally the FIXME's will have instructions to implement something specific, remove certain lines, etc. Again do not feel as if you have to adhere to these instructions, but they should be a good starting point.

Again the four files you will need to modify are as follows:

1. Model - Represents a signpost puzzle. The instance variables of this object store the information needed to describe the state of the puzzle (the dimensions of the board, the arrows in the squares, which squares are connected, which squares have numbers, etc.) and will be updated as the puzzle is solved. This contains the vast majority of the code you will change, so understanding this file will be crucial. Contained within Model is another class Sq (or Model.Sq), which represents a square on the board and its contents.
2. Place - An (x, y) position on a Signpost puzzle board. This differs from Model.Sq: Place only corresponds to the location of a square on the board, not its contents.
3. PuzzleGenerator - Class to help randomly generate Boards.
4. BoardWidget - An object that describes how to display the puzzle board. This file can remain mostly untouched, only one thing needs to be removed. The contents of this file are less important to understand than the rest (but by all means take the opportunity to peruse it).

This project tries to make good use of abstraction; the simpler functions you write will be instrumental in helping you accomplish more complex goals. Be sure to respect the abstraction barriers to minimize the impact of bugs or logical errors in your code. Further, if you find yourself bogged down by the details of a particular method, consider pausing to break it down into "helper" functions, each performing some coherent piece of the original function (only, as a stylistic matter, do give these new functions descriptive names, generally avoiding the word "helper" in the name.)

Submission and Version Control

It is important that you commit work to your repository at frequent intervals. Version control is a powerful tool for saving yourself when you mess something up or your dog eats your project, but you must use it regularly if it is to be of any use. Feel free to commit every 15 minutes; Git only saves what has changed, even though it acts as if it takes a snapshot of your entire project.

The command git status will tell you what you have modified, removed, or added since the last commit. It will also tell you what you have not yet sent to your central repository. You needn't just assume that things are as you expect; git status will tell you whether you've committed and pushed everything.

If you are switching between using a clone of your central repository on the instructional computers and another at home (or on your laptop), be careful to synchronize your work. When you are done working on one system, be sure to push your work to the central repository:

git status                          # To see what needs to be added or committed.
git commit -a -m "Commit message"   # To commit changes.
git push

If you start working on the other system, you then do

git status          # To make sure you didn't accidentally leave
# stuff uncommitted or untracked.
git pull --rebase   # Get changes from your central repo.

Submit your project by committing and tagging it:

git tag proj0-0     # Or proj0-1, etc.
git push
git push --tags

Be sure to respond to all prompts and to make sure the messages you get indicate that the submission was successful. Don't just "say the magic words" and assume that everything's OK.