A Graphical Representation of jump1.in
copyright RIT 2002
$Id: writeup.xml,v 1.7 2002/10/10 20:27:19 cs4 Exp cs4 $
Part 1 is due on 26 September 2004.
Part 2 is due on 10 October 2004.
Part 3 is due on 24 October 2004.
Part 4 is due on 7 November 2004.
Part 5 is due on 9 November 2004.
You will improve your design skills while learning many new design techniques and styles.
You will learn what it takes to develop a larger program in the C++ language.
Some of the techniques you learned in more standard object-oriented languages may not apply here. In addition, C++ has some unique features that you may be able to exploit. This project should help expose you to these issues and show you how to make choices you can live with.
Below you will read about some specific problems you are to solve. However, we will also show you how these problems fit into a more general analysis pattern. If you know this, you can design your solution to this more abstract model, thereby allowing you to plug in new concrete problems with less effort.
Here are the three problems you are to solve. We describe in the background section the common characteristics of these problems.
Your clock has gone dead because you forgot to wind it or replace the battery, or you had a power outage. This clock has hands, so you must turn them to adjust the time. Which way, and how far, should you turn the hands to fix the time the most quickly?
You've probably guessed that this will be the easy one of
the bunch. In fact, we'll trivialize it even further. The
clock only has an hour hand, so the question becomes how
many whole hours backwards or forwards the hour hand must
be moved. Then we will "complicate" it a bit by
turning it into a general modulo-n counting
problem, by saying that the clock displays n
hours on its face.
You are visiting a new country whose currency comes in several strange denominations. You have obtained a temporary job in a grocery store but making change in this new currency is a problem. What is the smallest number of coins you need to give change of a given amount and how do you do it? (Some amounts may not even be possible!)
For example, if the currency denominations are 3, 7, and 12, and we want to make change of 20 units we could give two "3" coins and two "7" coins.
A board has several holes into which pegs can be placed. A legal move consists of jumping a peg over a neighboring peg and placing it in the next location in line (which must be empty). The peg that is jumped over is then removed. These jumps cam be made in any direction - horizontally, vertically, or diagonally - if permitted by the parameters of the particular puzzle. A long jump is a succession of legal jumps with the same peg making all of the jumps and counts as one move. The object is to leave a single peg.
Sometimes you can find a triangular version of this puzzle in some restaurants.
To allow for more variety we will specify, for each instance of the puzzle, the allowed jumping directions. The possibilities are: vertically (either direction), horizontally (either direction), diagonally from upper left to lower right (either direction), and diagonally from upper right to lower left (either direction).
For example, if there are four holes and three pegs in a
horizontal line in the pattern +.++ (where
+ represents a peg in a hole and
. represents a hole) and horizontal jumps are
allowed then the sequence of two jumps
+.++ ++.. ..+.
will solve the puzzle.
The specifics of each problem will be given in the detailed submission instructions for parts 2, 3, and 4.
The problems described in the overview section belong to a class of problems that can be characterized as follows:
There is some kind of world that can be in one of many configurations. Actions cause the configuration of the world to change in some small and incremental way.
The set of all possible configurations is not known ahead of time; they must be computed by applying actions and seeing where they take us.
We are presented with an initial configuration, and asked to bring the system to an acceptable goal configuration.
The acceptability of a configuration as a goal configuration is testable (often there is more than just one such configuration).
The solution is then a sequence of actions that propel the world from the initial configuration to one of the goal configurations. It is enough to list a sequence of configurations that lead to a solution configuration.
Let's see how the jumping peg puzzle maps to this abstraction.
The world is a box of holes for pegs. The current configuration of the world is the state of each hole (peg or no peg). An action consists of jumping a peg over one or more pegs with a single peg and removing the pegs that are jumped over.
The initial configuration is just the initial setup of all the pegs. The test for an acceptable final configuration tests for exactly one peg.
The interesting thing about these problems is that we do not have to think about the concrete problem instance in order to describe an algorithm to solve it! Read and make sure you understand the algorithm below:
Create an initially empty queue of configurations.
Insert the initial configuration into the queue.
While
the queue is not empty and
the first configuration in the queue does not meet the goal,
loop:
Remove the first configuration from the queue and call it C.
For each action A applicable to C, loop:
Apply A to C, and enqueue the resulting
configuration if it has not already been seen.
end-loop.
end-loop.
The acceptable configuration is now at the head of the queue;
but if the queue is empty, there is no solution to the problem.
Did you recognize a pattern in the way the algorithm organizes and traverses its search space? It is a breadth-first search of a tree, where the nodes of the tree are discovered and attached as you go. This algorithm could be made more efficient. As written, it finds a goal configuration, but keeps looping until that configuration gets to the head of the queue. Feel free to improve or even redo the algorithm.
Notice some important things about the above algorithm:
No specific concrete problem is ever mentioned.
The algorithm is incomplete because it does not finish by telling you the sequence of actions that get you to an acceptable configuration. That, again, is left as an exercise for the student!
We do not say how to determine if a
configuration "has not already been
seen".
The activities in this lab will have you design a framework that is easily adapted to all the problems of the classification described above. You will then implement and test all three of the problems using that design
The general process you should follow goes something like this:
Develop the initial framework design in the abstract.
Submit the design to your instructor.
Write the code for the abstract framework.
For each problem for which you must implement a solution,
Code the specific problem classes.
If the previous step forced a modification of your design,
Modify the code for the design as needed to make it work
Modify the code for the previous problems as needed
Submit the code for your latest design and all the problems solved so far
Because this is the only project you are doing in this course, and it is a team course, there is a possibility that we will not be able to accurately assess your programming abilities if your teammate does most of the programming. Therefore, each team member must be responsible for roughly half the code written in each activity, 2, 3, and 4. In the header comments, the name of the principal author should show up first, as always, in each code file. The principal author of a piece of code must be able to explain it orally if asked by his/her instructor.
Part 1 is due on 26 September 2004.
In this first activity, you are mainly concerned with the design of the framework. The term framework means a set of classes that enable implementation of solutions to certain problems. However, the framework by itself is not a complete program. You will work with abstract notions such as configuration, goal, and find-next-configuration. The problem solver should be able to solve any problem that conforms to an interface that you develop in your design. Think carefully about this interface, as you will later be writing classes that conform to it to solve the three problems.
Your design document is a Rose UML model that contains use case, sequence, and class diagrams. For this particular project, the use case diagram is rather trivial. Just show a user actor requesting that the system solve the problem.
The more interesting work is in the class and sequence diagrams. The classes you show for this activity are only the ones of the framework, not of any particular problem. For the sequence diagrams, show some interesting scenarios involving part of the above algorithm. Although this would be illegal in real code, include objects that are instantiated from your abstractions. Note that there must be a method in some class that runs an algorithm like the one described in the Background section.
When you design the generic configuration class, make
sure you include a display function that
will print some textual representation of the
configuration to standard output. This will be of
great help while you are debugging your code. The
problem solver algorithm can be enhanced by a call to
the display function inside the loop. Of course, the
implementations of display() will only
show up in the specific problems' configuration
classes.
You might want to look at choices.html for some possible design choices before you do your design.
Call your model file
config-puzzle.mdl. It should contain
all the diagrams you have developed.
try cs4-grd project1-1 config-puzzle.mdl
Part 2 is due on 10 October 2004.
The purpose of this activity is to perform the first validation of your design. You will write the code for your design. Then you will add code for the set-the-clock problem, put the two together, and see how they work. It is important to note that you are expected to be using a framework that is equally applicable to the other problems. Clearly, there are far easier solutions to this problem than the one we are having you build!
Now your design must get more detailed. This is probably the right time to think about exactly how you will realize your design within the constraints of the C++ language. Although you are free to make your own decisions, some suggested approaches are shown at choices.html that satisfy the requirement of a framework that adapts well to different "configuration/puzzle" problems.
Getting back to the clock problem, it requires three integers as input:
number of hours on dial
current clock time
true time
The program is to be called clock,
which means the main function should be
defined in a file named
clock.cpp. As submitted, the
program must print out the solution by listing the
sequence of configurations needed to reach the chosen
goal configuration from the starting configuration.
You must also submit a file names readme
containing any information about your design or
program you want. If you have modified the design,
you must submit an explanation of changes in the
readme file.
You must submit all the .cpp
and .h files required to
build the clock program. It
must be possible to compile the
clock program by executing
gmakemake and then simply
make. Your design model must
also be resubmitted, augmented with the classes
for the clock problem. If your underlying design
changed, include the
readme file mentioned
above.
try cs4-grd project1-2 clock.cpp other-needed-code-files config-puzzle.mdl readme
Part 3 is due on 24 October 2004.
The purpose of this activity is to implement the solution for a problem that requires a slightly more involved configuration design. Write the code for the making change problem, plug it into your framework, and see how it works.
The program takes command line arguments specifying the initial state of the problem. The first command line argument is an integer representing the amount of change desired. The rest of the command line arguments give the denominations that are available in the currency. For example, the command
change 20 3 7 12
would specify the problem of making 20 units of change using coins of denominations 3 units, 7 units, and 12 units.
The program is to be called change,
which means the main function should be
defined in a file named
change.cpp. As submitted, the
program must print out the solution for the given
change making problem or report if no solution is
possible.
If you have modified the design, you must submit an
explanation of changes in the
readme file.
The world, although more complicated than the clock, is still fairly simple. The configuration basically consists of the number of each coin denomination. There must also be a place where the desired change and the available denominations of the coins is stored but since these values never change, these values do not need to be included in each configuration.
You must submit all the .cpp
and .h files required to
build the change program.
and the
clock program. It must be
possible to compile both programs by executing
gmakemake and then simply
make. Your design model must
also be resubmitted, augmented with the classes
for the change problem. If your underlying
design changed, include the changes in the
readme file mentioned above.
(
If you had to change your design, then you
probably need to update the clock program so
that it continues to work.
)
try cs4-grd project1-3 clock.cpp change.cpp other-needed-code-files config-puzzle.mdl readme
Part 4 is due on 7 November 2004.
The purpose of this activity is to implement the solution for a problem that at least appears very complex to humans. We hope that you will be surprised how easily your framework discovers a solution to this problem. Write the code for the jumping peg problem, plug it into your framework, and see how it works.
Your program will need to be told the initial
configuration of the puzzle. The program will be called
jump and will take two arguments:
The name of the input file to read for the
initial configuration data. If this name
is "-" then the initial
configuration data is read from the
standard input.
The name of the output file where the
solution is to be written. If this name is
"-" then the solution is
written to the standard output.
The puzzle can be considered to be a 2-dimensional
array of characters. The character '.'
represents an empty hole, the character
'+' represents a hole with a peg, and the
character '#' represents a place that
cannot contain a peg. The jump program
will be given the size of the puzzle, the allowed
directions for jumps, and the starting configuration.
The format for the data (either from a file or standard input) is as follows:
The first line of the initial
configuration data will contain two
integers which are the width and height of
the puzzle followed by a string of one or
more of the characters '-',
'|', '/',
'\'. These characters
indicate the allowed directions for the
jumps. Only jumps in the indicated
directions can be taken in solving the
puzzle.
The interpretation of the direction characters is as follows:
'-': jumps may be
horizontal in either direction.
'|': jumps may be
vertical in either direction.
'/': jumps may be
along a 45 degree diagonal with
positive slope in either
direction. This is in the
direction from the lower left to
the upper right or from the upper
right to the lower left.
'\': jumps may be
along a 45 degree diagonal with
negative slope in either
direction. This is in the
direction from the lower right to
the upper left or from the upper
left to the lower right. (Note
that, in your code, the backslash
character is '\\' as \ is the
escape character.)
This will be followed by a number of
strings, one per line, each having "width"
characters. The total number of strings
will equal the height of the puzzle. These
strings represent the initial
configuration of the puzzle and the
characters in the strings represent
hole('.'), hole with
peg('+'), or not part of the
puzzle('#').
You should not assume that there is exactly one empty space - there might be none or there might be more than one.
The object of the jump puzzle is to perform a legal sequence of jumps that leaves a single remaining peg.
You are responsible for detecting any irregularities in the input and exiting the program with a message to standard error. If there are too many or too few strings on a line, but it is compensated for in the rest of the input, we do not require that you detect this error. In other words, your input reader does not have to be aware that new lines are a different kind of white space.
An easy way to read this input is to use formatted
input to read the strings, e.g., is >>
str;. Note that this will skip whitespace so it
will also skip any number of blank lines. You do not
have to check for the presence or absence of blank
lines in your program.
A sample input file that shows a rather easy version of this puzzle can be found at jump1.in. It is an example that is easily solved by hand. Be sure and use it as an early test case. Here is what it looks like:
A Graphical Representation of jump1.in
The problem is to jump a single peg horizontally.
Here are three more puzzles that indicate the proper interpretation of the allowed jumping directions.
A Graphical Representation of jump2.in
A Graphical Representation of jump3.in
A Graphical Representation of jump4.in
A more complicated example is at jump5.in. It represents a 4 x 4 puzzle with one peg missing. This puzzle can be solved by jumping only horizontally and vertically. (If the empty spot is in a corner then the puzzle cannot be solved.)
A Graphical Representation of jump5.in
The puzzle found in some restaurants is at jump6.in. The allowable jumps are horizontally, vertically, and along the diagonal from upper left to lower right. It can be solved with the empty peg in any position.
A Graphical Representation of jump6.in
The program is to be called jump,
which means the main function should be
defined in a file named
jump.cpp. As submitted, the
program must print out the solution by listing the
sequence of configurations needed to reach the chosen
goal configuration from the starting configuration.
An action consists of jumping one peg over one or more
pegs in allowed directions.
Note that there is a possibility that no solution
exists. If that is the case for a particular input,
the program should print, "no solution
exists" on the output (file or standard
out), and then exit.
If you have modified the design, you must submit an
explanation of changes in a file named
readme.
The world is now more complicated. You may recall that
one of the framework approaches in choices.html was to represent the
configurations as a vector of integers. Even if you
choose another design, you can still put a vector of
integers into your configuration class. For this
puzzle, a 2D matrix might be easier to work
with. Think about indexing a single vector with an
accessing function to represent a 2-d matrix with a
1-d vector. You could use the character codes as the
integers in your vector. You could then cast the
integers to char for printing.
You must submit all the .cpp
and .h files required to
build the jump
and change
and clock programs. It must be
possible to compile all three programs by
executing gmakemake and then
simply make. Your design model
must also be resubmitted, augmented with the
classes for the jumping peg problem. If your
underlying design changed, include the
readme file mentioned above.
(
If you had to change your design, then you
probably need to update the other two programs
so that they continue to work.
)
try cs4-grd project1-4 clock.cpp change.cpp jump.cpp other-needed-code-files config-puzzle.mdl readme
Part 5 is due on 9 November 2004.
The last activity, due two days after the previous one, is the team evaluation.
Only a textual evaluation form is submitted. It is available as team-evaluation in the web directory for this project.
From your own account, submit your evaluation as follows:
try cs4-grd project1-5 team-evaluation
Grade Breakdown:
$Log: writeup.xml,v $ Revision 1.7 2002/10/10 20:27:19 cs4 Added option of custom.mk make file. (jeh) Revision 1.6 2002/09/29 00:46:43 cs4 Added link to design choices documents. (jeh) Revision 1.5 2002/09/19 03:52:38 cs4 First complete version (jeh) Revision 1.4 2002/09/13 20:24:49 jeh Minor changes (jeh) Revision 1.3 2002/09/13 02:42:54 jeh Changed problems to be implemented in parts 2 & 3 (jeh) Revision 1.2 2002/09/12 15:50:35 cs4 First version of overview (jeh) Revision 1.1 2002/09/07 23:05:46 cs4 Initial revision