Patterns Lab
Admissions
Calculator (Decorator Pattern)
The University of Northern California admissions calculators use the Strategy Pattern to determine if an application should be accepted or not. Here's a class diagram showing the current system:
Unfortunately, the GPAEvaluator is
far too limited for many applications. For example, applicants applying to the
medical school must include their score on the MCAT test, applicants to the law
school must include their score on the LSAT test. Applicants to the graduate
school (which includes Law and Medicine) must include their score on the GRE
test. Foreign applicants must include their score on the TOEFL exam.
Furthermore, requirements aren't as strict for
Redesign the system using the Decorator Pattern.
Submit a UML class diagram of your design, an implementation of all classes and interfaces in your diagram, and working test code.
Maze Challenge
A player moves from room to room through a seemingly endless maze, desperately seeking the exit before he runs out of time.
The maze is an N x M array of rooms:
class Maze ... {
int MAX_ROW, MAX_COL;
Room[][] maze;
Two special rooms are marked:
int playerRow, playerCol;
// current position of the player
int exitRow, exitCol; // position of exit
A counter counts the number of player moves:
int playerMoves = 0;
Of course there are setters and getters associated with each of these fields (except no setters for MAX_ROW and MAX_COL).
For now a room is an empty object:
class Room { }
Here's a sketch of a maze controller:
class MazeController {
private Maze myMaze;
void execute(String command) throws
Exception {
}
}
In particular, a maze controller executes the following commands for moving the player around the maze:
NORTH, EAST, WEST, SOUTH, RESET
For example:
else if (command.equals("SOUTH")) {
int col = myMaze.getPlayerCol();
int moves = myMaze.getPlayerMoves();
col = (col + 1) % myMaze.getMAX_COL();
myMaze.setPlayerCol(col);
myMaze.setPlayerMoves(moves + 1);
}
(i)
Implement and test Maze and MazeController.
Here is the GUI for Maze Challenge (ignore the File menu for now):
(ii) Draw a UML class diagram showing how you would implement Maze Challenge. Your design should incorporate the following patterns:
Model-View-Controller
Publisher-Subscriber
Adapter
Use the adapter pattern to create a listener that adapts a maze controller to the ActionListener interface.
Use the Publisher-Subscriber pattern to update the GUI each time one of the maze fields changes.
(iii) Implement and test Maze Challenge.
Your GUI should pop up dialog boxes when the number of moves left reaches 0 or when the player reaches the exit. For example:
Hint: use JOptionPane for this.
Circuit Simulator
(Composite and Publisher-Subscriber Patterns)
A wire encapsulates a single boolean value.
A digital component has an array of n input wires, and an array of m output wires (n and m are set by the constructor).
There are two types of digital components: gates and circuits.
There are three types of gates: AND, OR, and NOT gates. Each has a single output wire. A NOT gate has a single input wire while OR and AND gates can have 2 or more input wires. When the value of an input wire changes, the gate changes the value of its output wire (if necessary).
A circuit is simply a collection of wires and components.
Here is the circuit diagram for a 1-bit half-adder, which is a type of digital circuit:
Note that s0 = a0 + b0 and cout is the carry out.
Design and implement a toolkit for modeling digital components. Use the Composite Design Pattern and the Publisher-Subscriber Pattern. Wires are publishers and components are subscribers. A component subscribes to all of its input wires. When a wire changes value, it notifies all of its subscriber components, which call their eval methods.
Test your kit by implementing and testing the half-adder above.
Extra Credit Ideas
Our circuits are all combinational circuits—circuits with no feeds back loops. A sequential circuit uses feedback loops to "remember" previous inputs. The simplest example is the S-R flip-flop:
In this circuit S = 1 & R = 0 sets Q = 1 & Q' = 0. S = 0 & R = 1 sets Q = 0 & Q' = 1. S = 0 & R = 0 keeps Q and Q' the same (i.e. Q remembers the previous value of S.) S = 1 & R = 1 isn't allowed.
Unfortunately, our Publisher-Subscriber pattern will cause a stack overflow with this circuit.
There are two solutions as I see it.
The first solution is to implement each gate as a thread. In the example above NOR1 sets the value of its output wire. This calls update of NOR0. But the trick is that update must get NOR0 to run eval in NOR0's thread, not NOR1's thread. More work might need to be done. For example gates may need to delay before updating their output wires. I don't know, that's why it's extra credit.
The second idea is to simulate time. Instead of setting an output wire, a gate creates an event that says "at time now + delta the value of wire w should be set to false". This event is stored in a priority queue ordered by time. A scheduler component removes events, if the time of the event is passed the time of the clock, then the clock is updated. Finally, the event is executed. For an example of this sort of thing see my Sim Framework in http://www.cs.sjsu.edu/faculty/pearce/jutil/.
Prisoner's Dilemma Tournaments
(The Strategy Pattern)
In a Prisoner's Dilemma Tournament agents repeatedly compete with each other by playing Prisoner's Dilemma (PD). Different agents use different strategies. An agent's fitness is his total score divided by the maximum possible score the agent could have achieved given the number of games he has played:
Recall that in PD two agents independently decide if they will cooperate with each other. If both choose to cooperate, then each is awarded 3 points. If neither cooperates, then each is awarded 1 point. If one cooperates and the other doesn't, then the non-cooperative agent is awarded 5 points while the cooperative agent gets nothing!
There are several possible strategies:
Random: cooperate randomly
Selfish: never cooperate
Naive: always cooperate
Tit4Tat: cooperate with competitor only if competitor cooperated in the previous encounter
Unforgiving: cooperate only if competitor cooperated in all previous encounters
Note that these last two strategies require that each agent has some sort of memory about previous encounters with every other agent in the tournament.
Implement the PDTournament. At the conclusion of a tournament statistics should be generated showing which strategy is the best.
Extra Credit Ideas
Genetic Programming
Suppose each agent remembers what his opponent did the last N times they encountered each other. (For example N = 3.) A strategy is simply a list consisting of 2N entries, one for each possible history. Each entry is either true (cooperate) or false (defect). The agent converts the history of his opponent to an index, then uses this index to look into his strategy list to decide what to do. For example, if N = 3 and the opponent's history is 0 (Defect), 1 (Cooperate), 1 (Cooperate), then treating this as the binary number 011, the agent consults entry 3 in his strategy list. If this is 0, then he defects otherwise he cooperates. Initially the values in the list are totally random.
When the tournament is over, the fittest agents pair up, mate, then die. A new tournament begins with their offspring. When mating, the strategies of the two mates are spliced together at a random point. For example, if the strategy of agent 1 is 11111111 and agent 2 is 00000000, then the strategy of their offspring might be 11100000, where the length of the prefix is random. Finally, on entry in the sequence is mutated with a small probability p.
What do the strategies look like after hundreds of tournaments?
Strong Reciprocity
Here's another idea. Assume each agent has a randomly distributed attribute called vindictiveness. Assume this is a number between 0 and 1. Each time an agent defects, it selects k random agents (k = 1 or 2) and asks each one if it wants to punish it for cheating. If a selected agent decides to penalize a defector, then the defector's fitness is decremented by 10 and the punisher's fitness is decremented by 2. (Of course these numbers can be modified.) Notice that punishing a defector isn't free. There are lots of dead heroes out there. An agent decides to punish a defector by picking a random number between 0 and 1. If the number is less than the agent's vindictiveness, then he punishes, otherwise he does not punish. How does average vindictiveness correlate to average fitness for each of the five strategies.
At the end of the tournament the fittest agents mate. This time the offspring's vindictiveness will be the average of the parents' vindictiveness. The strategy will be the strategy of the fittest parent. Break ties randomly. What happens to the average vindictiveness after hundreds of tournaments? What strategies dominate?