Computer Science 4 - Project

Configuration Puzzles

Due Dates:

The span of this project was approximately 8 weeks. Each deliverable was graded and returned prior to the next due date.

Goal

1. Design

You will improve your design skills while learning many new design techniques and styles.

2. C++ Programming

You will learn what it takes to develop a larger program in the C++ language.

3. C++ Survival

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.

Overview

Abstraction as a Means of Extensible Design

Below you will read about some specific problems you are to solve. However, we will also show you how this problem fits 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 three problems whose common characteristics will be revealed.

The Parking Lot Jam

One concrete problem you will be asked to solve is a somewhat contrived situation for a valet parking attendant. 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.

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 Farmer's Dilemma

A farmer went to town and bought a fox, a goose, and a bag of corn. Unfortunately, he had to cross a river on the way home and the boat he had could only hold one of his purchases at a time. Furthermore, he realized that if he left the fox alone with the goose the fox would eat the goose and if he left the goose alone with the corn the goose would eat the corn.

How could the farmer get all of his purchases across the river uneaten?

One thing to notice is that the fox can be left alone with the corn. Another thing to notice is that neither the fox and goose or the goose and corn can be left on one side of the river when the farmer is on the other side of the river.

Fixing the Time on Your Clock

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 is 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.

The specifics of these problems will be given in the activity sections.

Background

A Single Abstraction for these Problems

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 ( Sometimes it is enough to list the sequence of configurations ) that propel the world from the initial configuration to one of the goal configurations.

Mapping the Abstraction

Let's see how the parking lot 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 vhicles. The test for an acceptable configuration would see whether the needed vehicle is situated at the exit, ready to drive out.

We will leave it as an exercise to the student to determine the mappings to the other two problems.

The Algorithm

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's 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 (This design technique is often referred to as Template (not to be confused with the meaning of the term in C++).)
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 first two points are typical of the design pattern known as Template Method (not to be confused with the meaning of the term template in C++). A template method defines the "skeleton" of an algorithm, deferring some steps to other objects that are involved in a particular application.

What To Do

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

Shared Programming Responsibility

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

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 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.

Part 2

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

These integers are to be provided on the command line in the order shown above. If you get the wrong number or type 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.C. As submitted, the program must print out the solution by listing the actions and configurations needed to reach the chosen goal configuration from the starting configuration.

If you have modified the design, you must submit an explanation of changes in a file named rationale.

If you want to submit a custom make file, rename it to be called custom.mk and submit it along with the other files.

If you submit your own custom.mk make file, invoking make without any arguments must produce an executable called clock that solves the clock problem described here.

Part 3

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 farmer problem, plug it into your framework, and see how it works.

This problem does not have multiple instances, so no input of any kind is required.

The program is to be called farmer, which means the main function should be defined in a file named farmer.C. As submitted, the program must print out the solution by listing the actions and configurations needed to reach the chosen goal configuration from the starting configuration.

If you have modified the design, you must submit an explanation of changes in a file named rationale.

Configuration Design Suggestions

The world, although more complicated than the clock, is still fairly simple. The configuration basically consists of two sets. One set contains the participants that are on the starting side of the river; the other contains those who are on the destination side. An active involves "ferrying" one or two participants from one side of the river to the other. The participants are the farmer, fox, goose, and corn. Of course, there are restrictions on number of participants on the ferry, and who may be left alone. They must be observed when a configuration is asked what its legitimate neighboring configurations are.

You must submit all the .C and .h files required to build the farmer program. and the clock program. It must be possible to compile both programs. You may submit custom.mk as before. Your design model must also be resubmitted, augmented with the classes for the farmer problem. If your underlying design changed, include the rationale 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. )

Part 4

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 lot problem, plug it into your framework, and see how it works.

Input

Your program will need to be told the initial configuration. It will be done via standard input.

First, all locations are in two dimensions. 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 second line will indicate the location of the exit by giving the coordinates of the square within the lot that is adjacent to it. (The exit will always be on the right (maximum x) side of the lot.) The third through last lines will give the locations of the vehicles: two pairs of coordinates for the two endpoints. Vehicle positions 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.

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 9 vehicles on the lot. That is, if there are more than 9, 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 parking1.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 parking1.in

The program is to be called parking, which means the main function should be defined in a file named parking.C. As submitted, the program must print out the solution by listing the actions and configurations needed to reach the chosen goal configuration from the starting configuration. An action consists of one vehicle moving one square either forward or backward. For example, moving ahead 3 positions would be considered 3 actions.

Note that, in this problem unlike the others, there is a possibility that no solution exists. If that is the case for a particular input, just have the program print, "no solution exists" on standard out, and then exit.

If you have modified the design, you must submit an explanation of changes in a file named rationale.

Configuration Design Suggestions

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. In this case, a 2D matrix would be easier to work with. You could number your vehicles 1 through n, where vehicle n is the one that wants to get out. The locations of the vehicles are put into the matrix as vertical or horizontal sequences of identical integers. Unoccupied squares could have zeros in them.

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.

How To Submit

You must submit all the .C and .h files required to build the parking and farmer and clock programs. It must be possible to compile all three programs. You may submit custom.mk as before. Your design model must also be resubmitted, augmented with the classes for the parking problem. If your underlying design changed, include the rationale 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. )

If you submit your own custom.mk make file, invoking make without any arguments must produce three executables: one called clock, one called farmer, and an executable called parking that solves the parking problem described here.

Part 5

The last activity, due one day 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.

Grade Computation

Grade Breakdown:

Design Model: 20 points (submitted)
Code for abstract framework, plus the clock setting problem: 20 points (submitted)
Code for abstract framework, plus the farmer problem: 20 points (submitted)
Code for abstract framework, plus the parking lot problem: 40 points (submitted)
Team Evaluation: +/- 10? points (submitted)

Change History


$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