CS 503 - Advanced Programming I Programming Assignment 5

Programming Assignment 5 - Circuit Times

Advanced Programming I, Spring 2007

Due Date

This assignment is due by 5:30 p.m. on Tuesday, 3 April.

See the assignment turn-in page (last modified on 14 January 2006) for instructions on turning in your assignment.

A logic circuit is a directed, connected graph in which the nodes are either logic-circuit components or ports and the edges are wires. Wires carry only logical 0 (false) or logical 1 (true) values. A logic-circuit component can have one or more incoming wires and one or more outgoing wires, although particular logic-circuit components may have restrictions on the number of input or output wires. There are four kinds of components:

And logic-circuit components. An and component can have one or more input wires and one or more output wires. The values carried by the output wires is true if all the values in the input wires are true; otherwise, the value on the output wires is false.
Or logic-circuit components. An or component can have one or more input wires and one or more output wires. The values carried by the output wires is true if any of the values in the input wires are true; otherwise, the values on the output wires is false.
Not logic-circuit components. A not component has exactly one input wire and one output wire. The value carried by the output wires is true if the value in the input wires are false; otherwise, the value on the output wire is false.
Switch logic-circuit components. A switch component has exactly three input wires and one output wire. The value carried by the output wire is equal to the value carried by the second input wire if the first input wire carries true; otherwise the output wire carries the value of the third input wire.

A port can either be an input port or an output port. An input port has zero input wires and one or more output wires. An output port has one or more input wires and zero output wires. An output port with more than one input wire acts like an or component.

Each logic-circuit component has a propagation time, which is the amount of time it takes for input values to move across the component and become output values. For an logic-circuit component with multiple inputs and outputs, assume that all input values to the component show up at the same time and all output values are produced at the same time; also assume the number of inputs and outputs has no effect on the propagation time. The and, or, and not logic-circuit component have a propagation time of one unit; the switch logic-circuit component has a propagation time of two units. Ports and wires have a propagation time of zero units (that is, value transmission is instantaneous).

The Problem

Write a program that reads a logic-circuit description and zero or more sequences of input-port values and writes to std-out, for each input-port value sequence, the time it took for the values to show up at the output ports followed by the resulting sequence of output-port values.

Input

All input comes from std-in. Input is in two parts: a description of a logic circuit and of zero or more input-port values. The two parts are separated by one or more blank lines, which is a line containing only space characters.

Logic Circuit Input

A logic circuit is described the the wires it contains. Each wire is described by a pair of logic-circuit components c_o c_i where c_o is the logic-circuit component providing the value and c_i is the logic-circuit component to which the value is delivered. A logic-circuit component is described by a name followed by a number. Recognized names are

name representing

and and logic-circuit component

or or logic-circuit component

not not logic-circuit component

switch switch logic-circuit component

in input port

out output port

name	representing
`and`	and logic-circuit component
`or`	or logic-circuit component
`not`	not logic-circuit component
`switch`	switch logic-circuit component
`in`	input port
`out`	output port

A number is a sequence of one or more decimal digits.

For example, the input

in0 and0
in1 not0
in1 and0
in2 and1
not0 and1
and0 or0
and1 or0
or0 out0

describes the logic circuit

The first wire connected to a switch is the control signal (that is x₀ in the diagram above). The second wire connected to the same switch is the true signal, and the third is the false signal.

A switch should have three inputs; a not component should have one input. Switches or not components that don't have the proper number of inputs should result in an informative error message and the program should halt without further processing.

Input-Port Value Input

The input-port values follow the circuit description on std-in and are separated from it by at least one blank line. Each input-value set is a sequence of n zeros and ones b₁, b₂, ... b_n, where n is the number of input ports defined in the circuit and b_i is either 0 or 1. Placing the input-port names in alphabetical order, the ith input port is assigned the value b_i. Each input-value set appears on a single line, and each input line contains at most one input-value set.

Output

Reading in the circuit description should produce no normal output. Any errors detected while reading the circuit description should cause the program to print an informative error message on std-err and stop execution without further processing.

Each input-value set read should result in a single line of output. If no errors were detected, then the total propagation time for the values through the circuit followed by the output-value set should be written to std-out. The propagation time should be separated from the output-value set by at least one space character.

An output-value set has the same format as an input-value set: it's a sequence of n zeros and ones b₁, b₂, ... b_n, where n is the number of output ports defined in the circuit and b_i is either 0 or 1. Placing the output-port names in alphabetical order, the ith output port produced the value b_i.

Any errors detected while reading an input-value set should cause the program to print an informative error message on std-err and wait for the next input-value set.

Testing

You can use gen-input, available in the class assignment directory /export/home/class/cs-503/a5, to generate input for your program. When run, it writes an randomly generated logic-circuit description to std-out, followed by some randomly generated input-value sequences You can use it with your program like so:

$ ./gen-input | ./circuit-analysis

Because gen-input creates new input each time it's run, you might find it more convenient to save the input in a file to provide your program with consistent input:

$ ./gen-input > input

$ ./circuit-analysis < input

This page last modified on 13 April 2006.