CS 261 Lab J - Mind Reading

Due Wed Apr 17 at 9:00am

Overview

In this lab, you will program the computer to read the user's mind. (Why didn't software developers do this a long time ago?) Your program will guess in advance whether the user will choose heads or tails, then get the actual response from the user. If your program guesses correctly, it gets a point; otherwise the user gets a point. The first one to 15 points wins. The interface should look something like this:

Welcome to MindReader.
****************************
I've made my prediction about what you will enter. Input 'h' or 't' below. 
Enter 'h' or 't': h
Drat. My prediction was wrong.
Score is now human 1, computer 0
****************************
I've made my prediction about what you will enter. Input 'h' or 't' below. 
Enter 'h' or 't': t
I was right!
Score is now human 1, computer 1
****************************
I've made my prediction about what you will enter. Input 'h' or 't' below. 
Enter 'h' or 't': t
I was right!
Score is now human 1, computer 2

Underneath the hood, your program will be using a hashmap to track the user's responses and use that to predict its guesses The "mind reading" will be implemented by remembering the last four responses and the last response that followed such a "response history". Humans are not very good at producing genuinely random output, and this simple method is surprisingly effective considering how simple it is.

This lab will be completed in pairs. Review the pair programming guidelines!

Objectives

To practice with HashMaps
To practice with queue-like data structures.

Necessary Files

None! You are on your own here.

Details

You will be making three classes for this program:

MindReaderUI This class controls the main interaction (perhaps in a playGame() method) using a while loop. Use System.out.println() and the Scanner on System.in for input and output. Inside the loop: use the makeGuess() method of the MindReader class to have the computer pick a guess, ask the user for a guess, compare them, print the appropriate response, and then update the MindReader for the next round.
MindReaderUI The MindReader class will, unsurprisingly, contain the core mind reading logic. It will have a ResponseBuffer instance variable and a HashMap that maps response histories to responses (you are welcome to use the java.util.HashMap class). Its only two methods (other than a zero-parameter constructor, which will do appropriate initialization) are:
- public String makeGuess() This method returns the program's guess for the user's next response: "h" or "t". If the response buffer is not full (see below) or the current response history is not in the HashMap, you should just randomly return "h" or "t". Otherwise, this method should look up the current response history in the HashMap and return the value associated to it.
- public void update(String response) After MindReaderUI has solicited a response from the user, it will call this method with the response. If the ResponseBuffer is full, the method will add the current response history and response to the HashMap (as key and value, respectively). A simple "semi-hashing" algorithm for this is to convert the response history to a String and used that as a key; however, making a copy of the ResponseBuffer object and using that as a key, overriding the .equals() method to be able to compare them, might be slick.
ResponseBuffer. This class is a wrapper around a Queue-like data structure with a size limit--if the queue is full, you dequeue the head in order to make room for the new item. You will need to implement an enqueue() (or add()) method to support this functionality. The java.util.LinkedList would be an appropriate underlying data structure to use.
- You will also likely want an isFull() method, to easily check if the buffer has been filled.
- Overriding the toString() method would make it easy to "hash" the buffer into a String.
I recommend implementing ResponseBuffer first, then MindReader, and then the UI class. Make testers as necessary as you go along.

Submitting

Submit all of your classes to the LabJ submission folder on hedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

Remember to fill out your lab partner evaluation!

Extensions

Right now, you just record the user's last response and use that in the hashmap. Make this a bit more sophisticated: Record a pair of values that represent the number of times the user followed that history with 'h', and the number of times the user followed that history with 't'. So your hashmap might have entries like:

"hthh": (3, 5)

which says that "hthh" was followed by 'h' three times, and 't' five times. So you would return 'h' as the computer's guess with probability 3/8, and 't' with probability 5/8.

You can use a Point, a two-element array, or another private class with two instance variables to store this pair of responses. You could even store the pair of values as a hashmap with keys 'h' and 't', and with the counts as values. So you would have a HashMap whose values are HashMaps. The idea here is to track the distribution of responses that followed a given history, instead of just the last response, and to make guesses according to that distribution.

Further refinements may be possible. How accurate can you make your mind reader?

Grading

This assignment will be graded based on approximately the following criteria:

MindReaderUI class with appropriate logic and instance variables [10%]
Working MindReader.makeGuess() method [20%]
Working MindReader.update() method [20%]
ResponseBuffer has appropriate data structure to record guesses [5%]
Working ResponseBuffer.add() method [20%]
Working ResponseBuffer.isFull() method [5%]
Working ResponseBuffer.toString() (or other appropriate accessor) method [5%]
Well-documented code in good style [10%]
You completed your lab partner evaluation [5%]