A Graphical Representation of jam1.in
copyright RIT 2002-2010
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. We will also show you how these problems fit into a more general analysis pattern. If you learn this general analysis pattern, you can design a solution that implements this more abstract model. That will allow you to 'plug in' new concrete puzzle problems with less effort.
There are four problems for you to solve. The background section describes 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.
A man goes to a river with several empty containers of different sizes to get a specific quantity of water in one of the containers. He can perform a sequence of the following operations:
For example, if he has a 5 liter container and a 3 liter container how does he get 4 liters? He can perform the following sequence (which is not a shortest approach to the problem):
We now have 4 liters in the 5 liter container
Imagine you have been asked to get a car out of the parking lot, but it is blocked by other cars. Your goal is to move the other cars (you have all the keys!) in such ways as to eventually get the desired car poised at the exit from the parking lot.
The cars can only move forward and backward - they cannot turn or move sideways.
You may want to think about a similar puzzle many of you may have tried, where you try to rearrange the square pieces of a picture to get them laid out in the proper order.
The specifics of each problem will be given in the detailed submission instructions for parts 1, 2, and 3. You will work on puzzle part 1 by yourself, and then you will work on puzzles 2 and 3 with another student teammate.
After you and your team have solved these puzzles you will have to solve one additional puzzle on your own. The specifics of this problem are given in the detailed submission instructions for part 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, and there may be more than just a single such goal 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 when presenting a solution to a puzzle to list a sequence of configurations that lead to a goal configuration.
Let's see how the parking jam problem maps to this abstraction.
The world is the parking lot. The current configuration of the world is the size, position, and orientation of each vehicle in the lot. An action consists of moving one vehicle to a new spot in a legal way (no collisions).
The initial configuration is just the initial setup of all the vehicles. The test for an acceptable configuration would be to see whether the needed vehicle is situated at the exit, ready to drive out.
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 cfg.
For each move applicable to cfg, 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 guarantees that the first goal configuration that is detected will be a minimum distance from the starting point.
This algorithm could be 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 process is completely general.
The algorithm is incomplete because it does not finish by telling you the sequence of actions that get you to an acceptable configuration. Finding a way to report the sequence of steps that to a goal is an exercise for the student!
We do not say how to determine if a
configuration
"has not already been seen".
Your design and implementation will have to
resolve how to decide that question also.
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 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 a design sketch 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 your latest framework code and all problems solved so far.
In this activity you will design a framework capable of solving any puzzle of a specific type. As a validation test, use the framework to solve the first simple puzzle. The first activity primarily concerns 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 understand that the solver must be capable of solving any puzzle and must contain all of the puzzle-solving machinery. An individual puzzle must not contain any puzzle-solving machinery; a puzzle may contain only the methods implementing the rules for a particular puzzle. You do not need to design a general puzzle rule mechanism because each puzzle instance 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 some type of a
display function that will print a 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 appear only 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
current clock time
true time
std::atoi(argv[i])to convert a command line argument
to an integer (though this does not handle certain types of
invalid data). 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 must report an error on standard
error and quit.
The main function must be defined in a file named
clock.cpp, which means the program will
be called clock.
As submitted, the program
must print the solution by listing the sequence of
configurations needed to reach the chosen goal configuration
from the starting configuration.
Your solution to this problem (and all problems) must print out the step number for each step in your solution.
You must also submit a file named
readme containing your design and any other
information about your program you want. 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. You must also submit your design document,
and that file must also be named readme.
If you have graphics that describe your design, add the files to
the end of the try statement.
Acceptable graphics files are .pdf, .gif, and .jpg. If you need to use another format, see your instructor.
submit: clock.cpp readme
This activity implements the solution of a problem that requires a somewhat more involved configuration design. Write the code for the water measuring 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 desired amount of water. The rest of the command line arguments are integers specifying the capacities of the containers. (The number of containers is the number of remaining command line arguments. There may be one container or many containers. Some of the containers may have the same capacity.) For example, the command
water 4 3 5
would specify the problem of obtaining 4 liters or water using two containers of size 3 liters and 5 liters.
The program is to be called water,
which means the main function should be
defined in a file named
water.cpp. As submitted, the
program must print out the solution that leaves the
desired amount of water in one of the containers. If
there is no solution your program must detect this and
print out an appropriate message.
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 amount of water in each of the containers. There must also be a place where the sizes of the containers is remembered but, since these values never change, these capacities do not need to be included in each configuration.
You must submit all the .cpp
and .h files required to
build the water program.
and the
clock program. It must be
possible to compile both programs by executing
gmakemake and then simply
make. 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 clock.cpp water.cpp readme \
other-needed-code-files
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 parking jam 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
jam 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.
First, all locations are in two dimensions and indicate a square of the parking lot. Consider the x (horizontal) dimension to always be given first, followed by the y (vertical). 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 first line will contain the dimensions of the parking lot, the number of squares horizontally followed by the number of squares vertically. (The exit will always be on the right (maximum x) side of the lot.) The second line will contain the number of cars parked in the lot. The third through last lines will give the locations of the vehicles: two pairs of coordinates for the two squares at each end of the vehicle. All vehicles will be one square in width so either the x or y coordinate of the pair of coordinates will be the same. Vehicles will always be horizontal or vertical. There will be no square (1x1) vehicles, so the orientation will always be clear from the location information. The final vehicle in the file is the one that must be moved to the exit which is at the right-hand side of the puzzle.
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.)
You may assume that there are never more than 25 vehicles on the lot. That is, if there are more than 25, treat it like an input error. We did this to facilitate printing.
A sample input file that shows a rather easy version of this puzzle can be found at jam1.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 jam1.in
A more complicated input file that shows a puzzle can be hard for humans to solve is found at jam3.in. This puzzle can be used as a test case after you have your code debugged. Here is what it looks like:
A Graphical Representation of jam3.in
Be sure that you check your code with puzzles that have no solution and puzzles that are solved by the initial configuration.
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.
Other possibilities include storing the data much as it is in the input. You could also make a list of vehicles where each one goes so far as to precompute where, if anywhere, it might be able to move.
The program is to be called jam,
which means the main function should be
defined in a file named
jam.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 moving one car one space.
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.
You must submit all the .cpp
and .h files required to
build the jam
and
water
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 parking jam 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.)
submit: clock.cpp water.cpp jam.cpp
This activity is to be done individually. You may use all of the files that you generated with your team but you may not share any code you write for this particular activity with anyone. You may use the same framework you developed for the previous submission.
You will need to copy the files from the team account to your personal account before working on this submission. In your own account, you will write the code necessary to develop the last activity.
Complete details of the last activity will be given in lastActivity.html at a later date.
Grade Breakdown: