copyright RIT 2005, 2007
$Id: writeup.xml,v 1.12 2007/03/16 18:24:43 cs4 Exp cs4 $
Part 1 is due on 8 April 2007.
Part 2 is due on 22 April 2007.
Part 3 is due on 6 May 2007.
Part 4 is due on 18 May 2007.
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 shallow box has several different sized wooden rectangular blocks in it. Not all of the space in the box is taken up with the wooden rectangles so it is possible to slide the wooden blocks around if there is enough empty space around a block. The problem is to move a given block to a specified position by sliding all of the blocks around.
The last problem will be announced after the third submission and will be done individually. If you understand the solutions to the previous three puzzles you will have no trouble with this "Mystery" puzzle.
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 moves 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 sliding block puzzle maps to this abstraction.
The world is a box of rectangular blocks. The current configuration of the world is the size, position, and orientation of each block in the box. An action consists of moving one block one unit horizontally or vertically to a new spot in a legal way (no collisions).
The initial configuration is just the initial setup of all the blocks. The test for an acceptable final configuration would see whether the specified block is at the specified final position.
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 move applicable to C, loop:
Make the move 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 project 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 four of the problems using that design
The general process you should follow goes something like this:
Develop the initial framework design in the abstract.
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 mostly a team project, there is a possibility that we will not be able to accurately assess your programming abilities if your teammates do most of the programming. Therefore, each team member must be responsible for an equal portion of the code written in the activities 2 and 3. 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. Activity 1 is solely an individual submission, while Activity 4 is an individual submission based on the work the team has done during submissions 2 and 3.
Part 1 is due on 8 April 2007.
In this activity you will design a framework capable of solving any puzzle of a specific type and, as a test of this framework, use the framework to solve a very simple puzzle. 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 also have to write classes that conform to it to solve the four problems.
Your design document is a text file that contains a description of the framework that will solve puzzles. It should include a description of the classes and the public methods that the client uses to solve puzzles. This description should explain how the solver will solve puzzles. It is important to realize that the solver must be capable of solving any puzzle and must contain all of the puzzle-solving machinery. The individual puzzles should not contain any puzzle-solving machinery but only contain methods implementing the rules for a particular puzzle. You do not need to design a general puzzle rule mechanism as each puzzle can explicitly code the possible successor states to any (legal) puzzle configuration.
The design document should also explain the flow of control and the sequence of steps that the solver would take when solving a simple puzzle. You should explain how the client uses the interface you have designed and the steps that are taken to solve a specific puzzle. For example, the puzzle problem can be to set the clock to 3 when it now reads 2. The design document explains how this will happen within the general solver framework.
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
puzzle 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 code for specific puzzles.
This activity will also 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! This first puzzle is designed to test your design.
You will have 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. All of the choices given can be made to work. As a hint, students who choose to represent configurations as a vector of ints generally have an easier time.
Getting back to the clock problem, it requires three integers as input:
number of hours on dial - hours run from 1 to the number specified
current clock time
true time
atoi(argv[i]) to convert a command
line argument to an integer. If you get the wrong number
of arguments, or if the times are out of
bounds with respect to the legal hours on the dial,
you should report an error on standard error and quit.
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 named readme
containing your design and any other information about
your program you want. You can also mention
shortcoming of your program too. The readme file is
part of every submission for this project. If you
modify the design in the future, which you can do at
any time without penalty, 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 document must
also be submitted as the
readme.
try cs4-grd project1-1 readme clock.cpp other-needed-code-files
Part 2 is due on 22 April 2007.
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 (and should not 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-2 readme clock.cpp change.cpp other-needed-code-files
Part 3 is due on 6 May 2007.
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 sliding block problem, plug it into your framework, and see how it works.
Your program will need to be told the initial
configuration. The slide program 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.
All locations are in two dimensions. The x (horizontal) coordinate is always given first, followed by the y (vertical) coordinate. The (0,0) location is in the standard place for computer graphics: upper left hand corner. x increases to the right, and y increases downward. Consider this as you decide on how you will print the configurations.
The format for the initial configuration 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 box.
The second line will contain a single integer which is the number of sliding blocks in the box.
The third through second-to-last lines will give the initial locations of the blocks: two integers representing the coordinates of the upper left corner of the block followed by two integers representing the coordinates of the lower right corner of the block. (The number of lines specifying blocks is the number of blocks specified in the second line.)
The last line gives the integer coordinates that the upper left corner of the last block specified (on the previous line) must be moved to.
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 numbers 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.
A sample input file that shows a rather easy version of this puzzle can be found at slide1.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:
The problem is to move the long block to where the square block is located. The square block will have to be moved out of the way because the upper left corner of the rectangle is supposed to go where the upper left corner of the square currently is.
A more complicated example is at slide2.in. It represents the following puzzle (Dad's Puzzler taken from "Winning Ways" by Berlekamp, Conway, and Guy).
The object of this puzzle is to move the big square to the bottom left of the box.
A more complicated example is at slide4.in. It represents the following puzzle (The Century Puzzle taken from "Winning Ways" by Berlekamp, Conway, and Guy).
The object of this puzzle is to move the big square to the bottom center of the box.
The program is to be called
slide, which means the
main function should be defined in a file
named slide. 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 one block moving one square
up, down, left, or right. For example, moving up
3 positions would be considered 3 actions.
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 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 number your blocks
1 through n, where block
n is the one that has to be moved to a
specified position. The locations of the blocks are
put into the matrix as a rectangular array of
identical integers. Unoccupied squares could have -1
in them.
Other possibilities include storing the data much as it is in the input or any other format that would enable you to calculate possible moves.
Note that, except for the block that is to be moved to a specified position, there is no need to distinguish between blocks with the same size and orientation. For the simpler puzzles this is not too important. For the Century Puzzle, however, if you distinguish between the four 1x1 blocks you will have 24 different configurations that all are really the same configuration. This will increase the number of configurations you have to keep track of by a factor of 24. There are also three vertical rectangles for another factor of 6 and two horizontal rectangles for another factor of 2. This gives a total factor of 288 times more configurations to analyze.
One way to avoid analyzing these extra (redundant) configurations is to always put the configuration in a standard form. You could rearrange the pieces until all identically shaped pieces occur in a specified order. If a move results in a nonstandard configuration you would swap identical pieces until it is standard.
You must submit all the .cpp
and .h files required to
build the slide
and change
and clock programs. It must be
possible to compile all three programs by
executing gmakemake and then
simply gmake. Your design model
must also be resubmitted, augmented with the
classes for the sliding block 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-3 readme clock.cpp change.cpp slide.cpp other-needed-code-files
Part 4 is due on 18 May 2007.
Details will be announced after the third submission.
Grade Breakdown:
$Log: writeup.xml,v $ Revision 1.12 2007/03/16 18:24:43 cs4 beginning update to 20063 version (swm) Revision 1.11 2005/10/20 01:14:06 cs4 Documented the fact that the solution offered for "water" sample problem is not a shortest-path. Revision 1.10 2005/09/12 13:39:25 cs4 Changed team description Revision 1.9 2005/07/15 14:55:36 cs4 update for Fall 2005/06 Revision 1.8 2005/03/11 19:20:03 cs4 Update for new term (swm) 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