Lab #7: More Progress on the Project

Get the various points in this lab checked off by a TA by the last lab of 
Tuesday, 30 October.  It would be good, of course, to have them done the 
FIRST week!  

We suggest you strive to get this
done during the week of 22 October.  It's not as important that you
work on it all in lab, so much as that it be done!

1. Implement PuzzleParser.java.  This turns lines into Assertions and
   Questions.  There is a temptation to create a huge mass of code full
   of 'if' statements, but perhaps you can do better by solving a more
   general problem: does this line match this pattern?  If you did
   PuzzleLineSet as we suggested, then you have a bunch a Strings with
   just enough whitespace, so that things are very clean and regular.  
   The patterns called for in the project are things like
	"Who is the *?"
   or
	"* does not live in the * house."
   where the asterisks each match a single string containing no
   blanks.  You could imagine (for example) designing a method that takes 
   a pattern like this and a String, and returns a list of matches for 
   the variable parts, or null in the absence of any match.  Then 
   your program is clean:

	L = matches (oneLine, "The * lives in the * house.")
	if (L != null) { ... }
	L = matches (oneLine, "* is the *.")
	if (L != null) { ... }

   You can actually do better than this.

2. Write the User-Manual.

3. What are you going to use as a representation for the solver part?  
   As the problem is set up, you want something that 

   * is capable of remembering that "X is not connected to Y" and "X
     MIGHT BE connected to Y" (where "connected to" means "lives in"
     or "does" or "is lived in by" or "is done by", as appropriate).
   * is capable of remembering all the names, occupations, and colors.
   * can be copied (so that you can save the current set of connections,
     try a tentative solution, and get back to the current set of 
     connections if that doesn't work).
     
   With this, you can solve any puzzle by 

   1. Making a first pass through the data finding all names, colors,
      and occupations (and making up dummy ones to get the same number
      of each).

   2. Make another pass filling in connections.  A POSITIVE assertion
      (Peter is the plumber) translates into a bunch of NEGATIVE 
      assertions (Peter is not anything else; the plumber is nobody
      else than Peter).  

   3. To see if there is a contradiction, try assigning occupations 
      and colors to each name, perhaps like this:

      ItIsPossible?:
	if (all names have a unique occupation and color)
	   return SUCCESS: It is not impossible;
        if (any name has no occupation or no color, or if
	    any occupation has no color)
	   return FAILURE: It is impossible;
	for some N that may have more than one possible occupation or color {
	   for each occupation, O {
	     for each color, C {
	       if it is possible to make N the O and live in C {
		  let tmp be a copy of the current PuzzleSolver.
		  In tmp, connect N, O, and C together 
		    (i.e., as if the assertions "N is the O" and 
		     "N lives in the C house" had been made);
   		  if (tmp.ItIsPossible? () )
		    return SUCCESS: It is not impossible
               }
             }
	   }
	   // If we get here, then no O or C works for some N, so....
	   return FAILURE: It is impossible
         }
   
4. You can adapt the ItIsPossible? pseudo-method above to finding
   out whether there is MORE than one solution for a certain
   name, or to actually return SOME solution.

5. So the question is: what data structure allows you to do the basic steps
   here: remembering connections and saving state?  Keep it simple.  Many
   people go for 3D arrays; nothing so fancy is needed.  How might you 
   use the Java Map and Collection classes, for example? Be ready to
   describe your scheme to the TA in some detail.  In fact, put your
   description into INTERNALS.