Programming Assignment 5 - Functional, Faulty, Flakey

See the assignment turn-in page (last modified on 3 November 2003) for instructions on turning in your assignment.

One way to implement a reliable system using such computers is to include n > 0 of them in the system and have each computer check up on the others (and itself) and issue statements on what it believes the state of the system is. Each statement consists of one of two types. The first statement type has the form

where 0 < c <= n is one of the computers in the system, b is either not or empty, and S is one of functional, faulty, or flakey. The second statement type has the form

where T is either hot or cool. This is a statement about the environment. All computers in the same report are subject to the same environment.

A status report is the collection of statements made by the computers in a system. Not all computers may contribute a statement to the status report, and computers may contribute more than one statement to a report.

Here is an example of a status report:

1: Computer 1 is functional.

The number of the computer issuing a statement precedes the statement, followed by a colon; in the example above, Computer 1 is issuing the statement. Here's another status report:

1: Computer 2 is flakey.
2: Computer 1 is faulty.
1: Computer 2 is faulty.

Interpreting a status report requires a bit of logical thinking. For example, in the previous example, Computer 1 reports that Computer 2 is both flakey or faulty. This is wrong because Computer 2 can be either flakey or faulty but not both; Computer 1 must be non-functional. Because Computer 2 is neither flakey or faulty, it must be functional and its statement is correct. We can conclude from this report that Computer 1 is faulty and Computer 2 is functional.

It may not always be possible to deduce facts from a report. The first example,

1: Computer 1 is functional.

the given statement could be either correct or incorrect; we don't have enough information to decide. Such reports are known as inconclusive. Other reports are inconsistent, such as

1: Computer 1 is faulty.
1: It is hot.

If the first statement is correct, then Computer 1 has produced a correct statement, but a faulty computer never produces a correct statement. If the first statement is incorrect, and Computer 1 must be either be functional or flakey. Computer 1 cannot be functional, because a functional computer produces only correct statements, so Computer 1 must be flakey. But a flakey computer produces incorrect statements only when it's hot; because the second statement is incorrect, it's cool and Computer 1 should not be producing incorrect results.

Because whatever we assume about a statement can be shown to be wrong, the report is inconsistent and we can conclude nothing from it.

Each status report is a sequence of one or more statement types as described in the Background Section. Each statement is contained entirely within one line, and each line contains at most one statement. Any single space character in a report can be replaced by a sequence of one or space characters.

Each status report is independent from all other status reports. The statements made and conditions derived from a particular status report apply only to that report, and do not apply to any other status reports.

where 0 < c <= n is a computer and S is one of functional, faulty, flakey, or

T is either cool or hot. Facts derived from a report may be output in any order.

If a report contains verifiable statements, your program should output all verifiable statements in the report and ignore all other statements. If a report contains no verifiable statements but does contain inconsistent statements, your program should output "Inconsistent.". If a report contains neither verifiable nor inconsistent statements, your program should output "Indeterminate.". (Note that this description should not be taken as a suggested approach for solving the problem. On the other hand, you may be able to solve the problem taking the approach suggested in this description.)

If the status report is malformed, your program should print an informative error message to std-out and go on to the next status report, if any. An error message should start with "! " (that's bang space) and be one line long (that is, contain no newlines except for the one at the end of the message).

Given the two examples in the Background Section, your program might output

Inconclusive.

Computer 2 is functional.
Computer 1 is faulty.