Due: Monday, 23 September 2019
- The Puzzle
- Program Design
- Instrumentation and Testing
- Submission and Version Control
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
It takes the same options as your project (see Instrumentation and Testing).
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.
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
- A view of the model, which displays the puzzle state to the user.
Our view resides in the
- 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
Controllerclass, although it also uses the GUI class to read mouse clicks.
Your job for this project is just to modify and complete the
We've marked places that need attention with comments containing "
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
--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.
--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
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
java -ea signpost.Main --testing < testing/myscript1.in
This will print out what tester.py sees, which it compares to
--testing, you can thus create
.out testing files to augment the ones we've provided in
We have set up the Makefiles in the
proj0 directory and in the
subdirectory to have targets
unit. In order to use make, you'll
need to install it. Follow the instructions here to do so.
Once installed, the command
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.
make check in the
proj0 directory will run integration tests,
which run the program and check its outputs against expected output using the
testing.py in the
testing subdirectory. By the time
you finish the project both
make unit and
make check should report no errors.
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,
others). Where Python has dictionaries, Java has
Where Python has sets, Java has
BitSets. Where Python uses
"duck typing"—as when it calls something a sequence because we can apply
generic operations like
map to it and iterate over it—Java
explicitly identifies supertypes of its various library types, such as
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
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
FIXME. These appear in the classes
PuzzleGenerator. There is also one trivial FIXME in
is only there as a stopgap to make the initial skeleton display something.
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:
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
Modelis another class
Model.Sq), which represents a square on the board and its contents.
Place- An (x, y) position on a Signpost puzzle board. This differs from
Placeonly corresponds to the location of a square on the board, not its contents.
PuzzleGenerator- Class to help randomly generate Boards.
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.
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
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 add <filepath> # To add, or stage, any modified files. 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.