BackgroundInputOutputCommand optionsWhat to Turn InAdviceExamplesCS61B, Fall 2001 Project #2: Puzzle Solver∗P. N. HilfingerDue: 2 November 20011 BackgroundYou’ve probably seen those puzzles in which you are given clues such as “The plumber lives inthe green house” and “Joe is not the archdeacon” and you are supposed to figure out everyone’soccupation and taste in exterior latex enamel. In this project, you are to write a general-purposesolver for this type of problem.The ground rules are that there is a row of houses, all of different colors, each occupied by oneperson. The people all have a single occupation (all different) and each lives in a single house. Itis assumed that all questions and information in the input refer only to these people, houses, andoccupations. It is also assumed that the numbers of houses, people, and occupations are equal tothe number of specific houses mentioned, of specific people mentioned, or of specific occupationsmentioned, whichever is largest. Thus, if a problem mentions only John, Mary, a plumber, a tailor,an architect, and a blue house, you may assume there are three people (one of whose names youdon’t know), and three houses (two of whose colors you don’t know). For example, we want yourprogram to take input such as this:The plumber lives in the blue house. Tom is not the carpenter.John lives in the yellow house. John is not the carpenter. Mary does notlive in the blue house. The architect does not live in the blue house.What do you know about John?What do you know about Mary?Who is the plumber?and print in responseJohn is the architect and lives in the yellow house.Mary is the carpenter.Tom is the plumber.[I suggest you pause and figure out why these must be true under the ground rules.]Sometimes, the questions can’t be answered. For example,Jack lives in the white house. Jack is the carpenter.Jill is the clerk. The carpenter lives in the yellow house.What do you know about Jack?to which the only response possible isThat’s impossible.Also, there can be several possible answers:Jack lives in the blue house. Mary does not live in the bluehouse. The mechanic lives in the red house.There is a green house.The architect lives around here. Who is the architect?∗This project is adapted from a problem in the 1996 Annual Berkeley Programming Contest.1Project #2: Puzzle Solver 2to which we can only sayI don’t know.2 InputThe input consists of a set of sentences followed by a set of questions. All input is (as in theexamples) in free format, meaning simply that words are separated by any amount of whitespace(blanks, tabs, newlines). The forms of the possible sentences and questions are actually open-ended, but we will test the following:Sentence:Person-Designator House-Relation the Color house.Name Occupation-Relation the Occupation.Person-Designator lives around here.There is a Color house.Question:What do you know about Person-Designator?What do you know about the Color house?Who is the Occupation?Who lives in the Color house?What does the occupant of the Color house do?What does Name do?Where does Person-Designator live?Person-Designator:Namethe OccupationHouse-Relation:lives indoes not live inOccupation-Relation:isis notName:any capitalized word other than a keywordOccupation:any lower-case word other than a keywordColor:any lower-case word other than a keywordThe notation above is a variety of Backus-Naur Form (BNF), and is described in Chapter 1 ofProgramming Into Java. As you can see, the specification is very loose about what constitutes acolor, occupation, or name, so that “Blah lives in the xyzzy house” or “The glorplefitzer lives inthe green house” are perfectly acceptable. However, we don’t allow any of the keywords (literalwords that appear in the syntax) as a color, occupation, or name. Nobody, for example, can benamed “Who” or “There,” and “occupant” cannot be an occupation. Also, no word may be usedfor two different things: nobody works as a “green if there is a green house. Words are separatedby whitespace (blanks, tabs, newlines). The trailing commas and periods appear immediatelyafter their words (no space). The word “the” in Person-Designator is capitalized at the beginningof a sentence, both in the input and in the output (see §3).Project #2: Puzzle Solver 3Most of the sentences and questions should be self-explanatory. The last two kinds of sentenceserve merely to introduce new names, occupations, or colors into the problem without sayinganything about them. All such new terms must be mentioned in the sentences (before the firstquestion), or the input is erroneous. That is, you can’t use a name, color, or occupation for thefirst time in a question; the inputMary is the carpenter. Who lives in the red house?is illegal.3 OutputThe output depends on the command options (see §4 below). Here, I’ll describe the normal(default) output. First, your program should print out the original input, not including thequestions, as a sequence of numbered sentences, each on one line (see the first example in §7).In this echo of the original input, you should remove extra blanks, converting all stretches ofwhitespace to a single blank.Following that, if the data are contradictory, then rather than answer any of the questions,just print out the lineThat’s impossible.and stop.Otherwise, print out each question on one line (again with whitespace compressed) followedby its answer on the next, as in this example:Q: Who is the innkeeper?A: Aloysius is the innkeeper.Answers to questions have the forms shown in Table 1 (that is, print out the appropriate choicefrom the responses listed).Errors. If the input to your program is faulty, you must, as usual, exit gracefully, using System.exit(1)to indicate that an error occurred. Our only other requirement in these situations is that you out-put a line containing the word “error” (in any combination of cases) somewhere. In the absenceof any errors in the input, exit using System.exit(0).4 Command optionsA user of your program starts it with a command having one of the following forms (things insquare brackets are optional; ‘. . . ’ means “one or more”):java solve -hjava solve [ -q ] [ FILE ... ]The first form means to print a concise, helpful description of the program and how to use it andthen exit. The second means to use the specified FILE names as input (that is, to use contentsof all the files, as if concatenated together in order,
View Full Document
Unlocking...