Configuration Puzzles: Design Approaches

Although you are free to make your own design decisions, some suggested approaches are shown here that satisfy the requirement of a framework that adapts well to different "configuration/puzzle" problems. But first, let's ponder some general requirements.

Clearly, if the solver algorithm is going to work with different problems, the notion of configuration should somehow be viewed as an abstraction. This abstraction would contain operations for things like goal testing, finding neighboring configurations,  and display/printing.

Most students of a more pure object-oriented language like Java would immediately think of making Configuration an interface, or an abstract class. And indeed, that is one of the approaches upon which we will expound. However, consider the following peculiarities of C++.

  1. In order to determine if configurations have been seen before, they ones already seen probably need to be stored in a container of some kind (something based on a map or set for easy lookup comes to mind as a good choice). It is necessary to be able to compare configurations to keep the container from holding multiple identical configurations.
  2. Passing around and storing configurations around by pointer can therefore be problematic, since we would be comparing addresses of configuration objects rather than contents.
  3. To allow polymorphism, the configurations must be pointers! (This will be explained by week 4 of the lectures.)
  4. If we do use pointers, and therefore dynamic allocation, we must delete the allocated objects to avoid memory leaks, but it is hard to determine if no one is pointing to a configuration anymore, since several configurations could have the same one as a potential neighbor.

So the design choices presented here can be broken into two categories:

  1. If we stick with pointers to keep the idea of using an abstract class and polymorphism, how do we get them to work?
  2. If we abandon pointers, how do we maintain the extensibility of the solver? That is, what other abstraction techniques could we employ?

If you feel like the design descriptions are incomplete, that is intentional. We have to leave something left for you to do! Nevertheless, feel free to talk to your instructor about any of these ideas, or others that you have.

String/Configuration Map and Inheritance

Here we get around the C++ pointer's shortcomings by utilizing something else in place of it that will still allow us some kind of indirect reference to a configuration object. Instead of an address into the memory space at large, we use a string to reference an associative map.

Define a function that creates a unique string for each distinct configuration. Use this string as a key to the map of configurations. Whenever you want to determine if a new neighbor configuration has already been seen, just compute its key and see if it is in the map. If you want to include a "pointer" in your configuration, e.g., to find your path back to the initial configuration, just remember the string key of the other configuration instead.

The configurations stored in the map can now be pointers, since the unique keys will ensure that exactly one copy of any configuration considered will be kept there. This means that polymorphism of these objects is preserved. Cleaning up your memory usage becomes simply iterating over the map and deleting each pointed-to configuration.

Hint: You are already required to generate a string representation of the configuration's state. Do you know where? Can this functionality do double duty?

Smart Pointers and Inheritance

One solution to this problem is the idea of a smart pointer. A smart pointer is an object that contains a pointer to another object, but does additional operations that regular C++ pointers don't do. Our smart pointer would perform two important functions. First, when asked to compare itself with another instance, it would actually access the pointed-to objects and compare their contents. Second, it would keep track of how many other smart pointers are referencing it, so that it can delete the object it's pointing to when no one else needs it anymore.

By doing these two things we eliminate the drawbacks of using pointers, but introduce some additional complexity into the design.

So here is how it works: Wherever you would have declared a variable of type

Configuration *cp( new .... );

you now declare its type as

ConfigurationPointer cp( new .... );

It's as "simple" as that! The essence of such a class has been written for you. It can be found in ~cs4/pub/SmartPointer. There is also OnlineDoc for the class at ~cs4/pub/SmartPointer/doc.

Very Careful Tracking of Configurations and Appropriate Deallocation

If you are sure you want to use the inheritance/pointer approach, there are other ways you may think of to make sure that you deallocate every configuration that you allocate.

To see if your approach is successful, you may want to include as an attribute an instance of the Watcher class, found in the CS4 pub directory.

For the truly daring and ambitious, you could define your own memory manager and define custom versions of new and delete in your configuration class. See "Overloading New & Delete" in Chapter 13 of Volume 1.

Templates

C++ has a very powerful abstraction mechanism that is exercised during compilation of your program instead of at run-time. It is called templates, but is more generally known outside of C++ as generics or generic programming. You had a peek at a template class named list in the lab introducing you to our C++ development environment. We will eventually cover this more in class, but you can find information about templates in volume 2 of our text (on line).

We can follow the same abstraction approach by using templates. Your problem solver is now a template class that must be "instantiated" with a specific class that conforms to an interface for a configuration. But now, there is no parent class from which it must inherit; the compiler just makes sure it has the right operations. This eliminates the need for pointers, which eliminates the problems mentioned in pointer-based approaches.

To give you a better feel for this, let's compare the two approaches on a simpler problem. The goal is to order a pair of objects. All we know about these objects is that they can be compared.

Using Inheritance

If we were using a pointer/inheritance approach, we would need an abstraction for the comparable objects that would look something like this:

class Comparable {
public:
	virtual bool operator<( const Comparable &other ) = 0; // abstract
};

The holder for the pair of them that also puts them in order (the code is shown inline to save space) is shown next. Note that, to keep the polymorphism, we must use pointers throughout.

class Pair {
public:
	void order() {
		if ( *b < *a ) {
			Comparable *temp( a );
			a = b;
			b = temp;
		}
	}
private:
	Comparable *a, *b;
};

Then we would need to create a subclass for a specific type of thing, say an integer. (This class declaration is clearly incomplete.)

class Integer: public Comparable {
public:
	virtual bool operator<( const Comparable &other ); // concrete
private:
	int value;
};

An additional little gotcha here is the type of the argument to operator<() above. But we won't even get into that! The smart pointer solution attempts to fix this with a run-time assertion check.

Using Templates

The tempate approach is different. We no longer need the abstract base class. Integer could be done this way:

class Integer {
public:
	bool operator<( const Integer &other ); // concrete
private:
	int value;
};

The Pair class would be written as a template:

template < class Comp >
class Pair {
public:
	void order() {
		if ( b < a ) {
			Comp temp( a );
			a = b;
			b = temp;
		}
	}
private:
	Comp a, b;
};

How does this work? Well, when an instance of Pair is declared this way,

Pair< Integer > p;

The compiler will at some point attempt to regenerate the code for order() with Integer substituted for Comp. Since Integer defines operator<() the code compiles successfully. In fact, we could just use plain old int's, too!:

Pair< int > p;

Applying templates to this problem means that your configuration is now the template parameter, just like Comp, and the problem solver becomes the template class, like Pair.

If you are curious, UML represents template classes as parameterized classes.

By the way, Java is expected to have generics in their 1.5 release in early 2004.

A Universal Representation:
Vector of Integers

This approach works by "manually" implementing the polymorphism one needs by establishing a rule that all configurations will be represented by a single type, a vector of integers for example. The code specific to a certain problem being solved then interprets the contents of one of these objects in a unique way. The generic problem solver has no idea what the objects' contents describe. It just passes these vectors to objects that do and asks questions like, "Is this a goal?" and, "What configurations are neighbors of this one?"