Computer Science 4 - Project 1

Configuration Puzzles

copyright RIT 2005, 2007
$Id: writeup.xml,v 1.12 2007/03/16 18:24:43 cs4 Exp cs4 $

Due Dates:

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.

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

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

Making Change

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 Sliding Block Puzzle

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.

A Mystery Problem - the limited clock

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.

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:

Mapping the Abstraction

Let's see how the sliding block puzzle maps to this abstraction.

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

What To Do

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
        

Shared Programming Responsibility

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

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:

These integers are to be provided on the command line in the order shown above. Remember that in C++ command line arguments are strings (arrays of chars) and must be converted to ints before they can be used in your program. You may use 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.

How To Submit

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

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.

Configuration Design Suggestions

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.

How To Submit

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

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.

Input

Your program will need to be told the initial configuration. The slide program will take two arguments:

If you get the wrong number of arguments or you have difficulty opening, reading, or writing any files you should report an error on standard error and quit.

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:

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:


A Graphical Representation of slide1.in

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


A Graphical Representation of slide2.in

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


A Graphical Representation of slide4.in

The object of this puzzle is to move the big square to the bottom center of the box.

Submission Details

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.

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

How To Submit

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

Part 4 is due on 18 May 2007.

Details will be announced after the third submission.

Grade Computation

Grade Breakdown:


Change History

$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