Nick Brettel's eight puzzle design
Contents |
Intro
My project is on my Cosc411 experiment. This experiment was exploring whether people can solve a problem-solving task quicker when collaborating. Participants would solve #The Eight Puzzle five times, either individually or in pairs (training phase), then solve it five times alone (testing phase). The experiment was mostly automated (so they'd just read instructions, click next, etc.). Their performance was logged.
This introduced a few design challenges:
- Single partipants and pairs of participants can solve the puzzle in the training phase, so pairs and individuals need to be treated the same, but (for logging) produce different output
- The whole experiment follows a rigid process, so we need a nice way to define what we show and when.
- Moreover, participants can take one of three paths. Individual, Collaborative, or Collaborative-resume (when the pair splits up after training, one person can continue, the other jumps to the same stage).
- Individuals or Pairs need to get slightly different instructions, but they are very similar.
- The experiment is largely GUI based, but we want to separate the GUI out as much as possible.
Furthermore, I would like to be able to provide a framework from which one can easily extend the experiment if needed in the future. For example:
- can add participants who train in groups of three
- can solve a different puzzle
- can add an extra slide of instructions
All the code was written this semester (while taking Cosc427) and I tried to make a good design following the ideas we were taught. So effectively, I started with nothing. However, after the experiment was run I decided to move into a refactoring stage (specifically for this 427 project) with two goals:
- to further improve the design (duh)
- to refactor the design such that (in a hypothetical situation) it could be easily extended for future similar collaboration experiments
You can see the design as it was before refactoring at #Old Design.
Contents
- #Tour Of The Design (Go here first! A nice introduction to my design)
- #Big Picture (A view of the entire design)
- #Design Patterns (My project in regards to design patterns that were used)
- #Design Maxims (An overview of a number of design maxims, whether applied or ignored)
Code
The code is written in Java 5.0 (stupid version numbers), and you can get it here: media:427projectCode.tgz.
To run it, run `java ExperimentGui`. You can run collaborative mode with `-c` or collaborative resume with `-cr` flags.
The Eight Puzzle
The eight-puzzle is a simple game where there are 8 tiles and one blank arranged in a 3x3 grid. A tile can be moved if it is adjacent to the blank, as if it is being slid across (left, right, up or down). There is a similar fifteen-puzzle where the pieces are in a 4x4 grid.
In fact, a version of the puzzle appeared on the original Macintosh System, thanks to Andy Hertzfeld, and remained on the OS for a long time following. Anyways, I digress. You can see a screenshot of the puzzle below.
See wikipedia for more details...
Old Design
This is what my design looked like when the program was actually used to run the experiment. After this, I put on a refactoring hat for the purposes of this Cosc427 assignment. I've shown it here so I can talk about some of the changes made in design.
Firstly, let me apologise that it is so big, and that you have to scroll sideways :).
And here it is:
Tour of the Design
Here, you get a step-by-step tour through the design. This is the logical journey that digests the design in small bites. Just click the links below, in order, for a look at the main parts of the design. It'll be built up bit-by-bit, and then looking at the ../BigPicture should make more sense. Note this is not necessarily a chronological order of how it was designed, only the final design is shown, built up piecewise, in the sequence that (I think) is easiest to comprehend.
Logging Participants
The experiment tested the performance of participants who trained collaboratively, or individually. After training, all participants worked individually for testing. This introduced the first design challenge. Single partipants or pairs of participants can solve the puzzle in the training phase, so pairs and individuals need to be treated the same, but (for logging) produce different output. Furthermore, a pair becomes (*alarm bells*) a single participant once training is complete. This is my proposed design to model participants:
To clarify the UML, Phase (seen in the diagram in the Participant class) is an enum (see Enum Idiom) that takes one of two values: TRAINING or TESTING. The variable currPhase stores the current phase (ie if the participant is training or testing). The bottom region of a class shows the "properties" (anything for which there is a getWhatever() method). The two properties in Participant (currRole and time) signify there are corresponding getters, but neither of them are actually stored as variable: they are derived attributes.
As you can see, the Participant class models one or more people taking part in the experiment, and they have two Roles: a trainingRole and a testingRole (the singular class name Participant may be misleading - it can model more than one person if they are working together - however, making it plural is more confusing). The ParticipantRole handles how the log data is output, as defined by the printData() method. A PairRole will print out data for both of the participants, while an IndividualRole will print it out for the single individual. Also, an individual has a single "name" (not meant literally - just some identifier), while pairs have a couple of names, one per person. The reason why an IndividualRole stores a wasCollaborative variable is because pairs may split into individuals, but we still need to know they were previously pairs, for the log output.
Observant readers will recognise this is strikingly similar to the Strategy pattern - or is it State pattern? Hmmm. I originally was of the opinion it was Strategy Pattern. Each different implementation of the printData() algorithm is encapsulated in its own class, and thus is interchangeable. This means we can vary the number of people working on the experiment together, and still output data for each person. However this varies from the typical Strategy. The roles don't just encapsulate an algorithm, they also store additional data about the "role" - ie the name(s) and wasCollaborative for individuals (see below), and there's the addName() method (more on that soon). However, considering the fact that some participants change from being pairs to singles, perhaps it is a State pattern. When changing state from a single to a pair, the behaviour changes, like when changing class. Although the trainingRole or testingRole attributes never change class, this is just due to the currPhase variable - conceptually we are still changing state. Thanks to Phil, Blair and Greg for pointing this out at our late-night (err early-morning) discussion session :).
The main advantages of this approach (regardless of whether it is State or Strategy) are that we treat single participants and pairs uniformally, although they have slightly different behaviour, we Avoid becomes, and its easy to extend this design if we needed, say, a TripleRole for groups of three. Additionally, as an added bonus, the data about each participants two roles are stored like a history. For more design pattern discussion, see #Design patterns.
[[Tell, don't ask and Law of Demeter are followed - the Participant wraps up calls to the role. To do this Recursion introduction is used: the participant just relays calls to printData() and addName() to methods in one of its roles (of the same name), depending on the currPhase. In this situation I think applying these maxims is definitely beneficial. The ParticipantRole becomes transparent so we don't even need to know that a participant has a role, as far as anyone using a Participant is concerned, it can addName() and printData(), and we don't care how. It is effectively InformationHiding. The alternative, something like participant.getCurrentRole().addName(), requires the client to know that the participant has a role, it has a getter to access it, it stores the names, and we can change them using the method addName()...
So what is this addName() method? I needed some way to set a participants name. However, to set a pair's names, we would need two names, as opposed to the one required to set an individual's name. But if IndividualRole and PairRole have different setName() methods (with a different number of arguments), then a Participant could only setName() if it knew whether its role is training or testing. A Participant shouldn't need to know the types of its roles, just that it has roles, and what their interface is. Simply put, I want to Program to the interface not the implementation. To do this, a uniform way to set name(s) is required, even though we don't know how many names. I choose to do this by using a common interface: an addName() method sets one name, and it can just be called a couple of times to set a couple of names (for pairs). I noticed later that this was a similar idea to the Builder pattern (I don't think I can go so far as to say this is an application of the pattern) - we add parts (names) until we have built a product, and then we normally get the product (in my case, we change the product by adding parts, so there is no need to get it - we already had it). An alternative approach would have been to pass in a Collection of names. However, I decided this was not as good, as the number of items in the collection would be very small (and a majority of the time participants are individual), so there would be a lot of unnecessary Collections, and they do seem like overkill.
Slide Show
The experiment consists of pages of instruction, and the task to perform. Displaying these instructions, and the task itself, is analagous to a slide show. We have a number of slides (or "cards", thinking like Java's CardLayout) and for each, we show it, then move on. A key abstraction that was identified in the refactoring process, was that all panels that are displayed to the user abide by the same interface. Namely, all my panels follow a simple process - they show a card, until they are done. I decided a Card abstract class was necessary that captured this common behaviour.
The entire experiment application is controlled by the ExperimentGUI. This is also the main JFrame that contains any JPanel that is displayed. It keeps track of all the instruction Cards that can be displayed, plus the EightPuzzlePanel card that contains the gui by which someone solves the puzzle.
As you can see above, by providing a Card abstraction, the coupling is less tight - the ExperimentGUI depends on the abstraction rather than the specific panels. The abstract Card also gives us a uniform way to tell the ExperimentGUI to move to the next slide. The Card stores the ExperimentGUI and uses it in the (concrete) done() method. This method just calls the panelDone() method in ExperimentGUI.
What the instruction Cards are themselves is not very important. ExplanationPanel is just a generic panel, with a text box and a next button, for displaying any textual instructions to the user. The abstract StartPanel and StartTestingPanel classes are also shown. These, much as the name suggests, are panels for instructions when the experiment begins, and just before testing, respectively. We'll look at StartPanel a bit more later on.
To create a new Card, all that is needed is to provide implementations for the abstract method show() (for any behaviour when the Card is first displayed) and call the done() method when finished.
Dependency Inversion Principle, applied
How I ended up with this design deserves some explanation. You can see what I had prior to refactoring at #Old Design. I was concerned with the three two-way dependencies - each panel was tightly coupled to the ExperimentGUI. Firstly I considered using the Observer pattern. I said at the time:
- '...I could make each "card" observable, to decrease the coupling between ExperimentGUI and a card. This doesn't fit the ObserverPattern that well: there is only one object doing the observing, and many being observed. However, it would get rid of an owner reference. Is it really worth it when there's only one Observer, ExperimentGUI? I think so. Observer pattern may make things a bit more complicated, but that's better than having the unnecesary owner reference: a card doesn't need to know its owner, only how to say "I'm done".'
Then I realised, there had to be a better way. Strike one.
My next thoughts were that I could use the Mediator pattern. I thought the interactions between the GUI and the Panels is well-defined (e.g. GUI says "show this panel", a panel says "I'm done"). But then, is the State really a state of the gui? Or a state of the Mediator? Upon further examination, I realised that the Mediator pattern also didn't really fit. Strike 2. The interactions between objects are well-defined, but not very complex. Applying mediator in its entirity would be overkill to the extreme, but looking at how the Mediator pattern was a good idea helped me to see the solution.
Finally, I realised, the ExperimentGUI was depending on the low-level details of each Card. What I needed, was to listen to Bob Martin and follow the Dependency inversion principle. He states that what is needed is a dependency inversion, so in my case, the ExperimentGUI would no longer depend on the panels, but on the Card abstraction, and the panels would also depend on this Card abstraction. Thus, the dependency is inverted. This gives us our design above!
ExperimentGUI still depends on EightPuzzlePanel :-/
You can see, however, that there is still one dependency to a subclass of the Card hierarchy - the ExperimentGUI must have an EightPuzzlePanel. This is due to the fact the EightPuzzlePanel is in charge of looking after the Participant. You could move the Participant to the ExperimentGUI controller class - but I think it makes more logical sense where it is. The EightPuzzlePanel is the only thing that needs to know about the participant - as they do the experiment (by using the panel) data about the participant is recorded. Here again we have an object (ExperimentGUI) depending on the low-level details (EightPuzzlePanel), which doesn't fit with the Dependency inversion principle. This would not be too difficult to fix. We need to represent the fact that we require some TaskCard (if you like) that is a card that represents the task to be completed by the Participant(s). A TaskCard would require a startTesting() method and a addName( method. I considered doing this, but didn't for two reasons. Firstly, it really isn't necessary yet. Do the simplest thing that could possibly work, Keep it simple and You ain't gonna need it were begging me not to. It would make more sense only to do it once a different puzzle was actually required to be plugged in, instead of the eight-puzzle. Secondly, I just ran out of time :) But hopefully you can see it would be easy to refactor, when necessary, and the goal of making the experiment extensible would still be possible.
Rigid Procedure
The process of participating in my experiment followed a rigid process. First you were presented with some starting instructions. Then you would go into a training phase. In the training phase you would, n times repeatedly, be presented with a "get ready screen" then the eight-puzzle itself. And the process continues. You can see that there are various stages of the experiment, and you step through them, so they could be represented as states. I decided to use the State pattern for modelling this.
The merit of using the State pattern here is dubious. I have often weighed up whether, in this case, it is beneficial, and I've decided that marginally, yes, with some costs. The first thing to consider, is what behaviour is changing as you go through the states. Basically, the only thing is what Card is shown, and what state you go to next.
Using a state pattern definitely does get around a big ugly method containing many if-elses, and we should Beware value switches. Also, we can store additional information about each state (e.g. iteration) in the state class itself, following Keep behaviour with data. And, as the Gang of four say, it localises state-specific behaviour and partitions behaviour for different states. However, it also results in distributing the logic, relating to the one function, across many classes. As a result, the design is a lot less compact (as Martin Grenfell said, it's fat). Adding new states may make maintenance difficult. Also, ExperimentGUI coordinates all the functionality (the states just call methods on it, using an owner reference), so ExperimentGUI becomes bigger.
Weighing up all these pros and cons, I decided to use it.
Varied Instructions
When users start the experiment, they are presented with instructions. However, the instructions vary slightly for the individual or collaborative groups. For example, both groups get a welcome message, but the collaborative group needs a specific message saying how they will be working collaboratively. To achieve this, I used the Template method pattern.
The idea behind using this pattern was to create a general structure for the instructions, but allowing them to vary. Again this allows us to follow the Open closed principle. We are open to extend StartPanel, but we can only extend specific aspects of the instructions (namely the "enter name" message and the "process" message). We are closed to modifying any other instructions, the order of the instructions, or what the "welcome" and "process" messages are.
Again the question arises, is it really worth it? We could have an arguably simpler design where instead we have, say, a setInstructions() method and some constant Strings to make use of, e.g.
public static const String WELCOME_STRING="Welcome to my experiment\n";
Instructions could then be set by (something like):
setInstructions(WELCOME_STRING + "bla bla bla\n" + PROCESS_MESSAGE_STRING);
Using a Template method pattern is a lot more rigid - the order of instructions is clearly defined, and the common behaviour is factored out, so all StartPanels (ever) must have the fundamental welcome and process messages. In fact, the welcome and process messages are made private to ensure to subclasses can't override them.
The Big Picture
Here you can view the entire design, in all its glory. Note that the title was meant literally - the design is a very big picture size-wise. #Tour Of The Design gives a walk-through of the design if it doesn't seem to make sense. This diaagram is just to get an idea of where everything fits in. Also, this design is often referred to, so feel free to print it off :).
Design Patterns
The following design patterns are present in my design.
Template Method Pattern
A Template method pattern is used to vary instructions depending on the participant's collaboration condition, but still following a uniform structure. It is discussed more at #Varied Instructions.
Participants:
| AbstractClass | StartPanel |
| concrete templateMethod() | getInstructions() |
| abstract primitiveOperation1() | getEnterNameMessage() |
| abstract primitiveOperation2() | getConditionMessage() |
| ConcreteClass1 | IndividualStartPanel |
| ConcreteClass2 | CollaborativeStartPanel |
| ConcreteClass3 | CollaborativeTestingStartPanel |
State Pattern Number 1
A Participant has a ParticipantRole that follows the State pattern. This allows participants to be individuals or pairs, behave differently depending on which, and change from one to the other. This could easily be considered a Strategy pattern however - this and related discussion is at #Logging Participants.
Participants:
| Context | Participant |
| State | ParticipantRole |
| abstract handle() | printData() |
| ConcreteState1 subclass | IndividualRole |
| ConcreteState2 subclass | PairRole |
addName() could be considered a second handle() method, but I won't describe it here. I think it is more like a Builder pattern below...
State Pattern Number 2
A State pattern is also used for the various stages of the experiment.
Participants:
| `Context` | `ExperimentGUI` |
| `State` | `ExperimentState` |
| abstract `handle()` | `showNextCard()` |
| `ConcreteState1` subclass | `TrainingInstructionsState` |
| `ConcreteState2` subclass | `GetReadyState` |
| `ConcreteState3` subclass | `FinishState` |
| ... | ... |
This is discussed further at #Rigid Procedure.
Singleton Pattern
The states in the second state pattern (above) are all singletons. Fairly trivial.
Marginal
These, strictly speaking, are probably not quite design patterns, but they are very close, and follow similar ideas.
Builder Pattern
A Builder pattern-like idea is used to addName()s to participants, whether they are collaborative or individual. See #Logging Participants.
Strategy Pattern
You might think, looking at state pattern number 1 (above) that it is a strategy. This idea is discussed at #Logging Participants.
Alternatives
Various other design patterns were considered during design. A few of these, and why they were not included, are discussed below.
Composite Pattern
To model a pair of participants, or individual participants, I initially thought to use Composite pattern. However, this is no good - containment is too general (we have an exact number of participants each time).
Factory Method Pattern
Factory method pattern was considered to cope with the different panels when there are pairs or individuals. This refactoring could still be done in the future, but at this stage it is not necessary, and instead I've decided to Keep it simple, stupid.
Observer Pattern / Mediator Pattern
I considered using Observer pattern and Mediator pattern at one time, also. See #Slide Show.
