Programming with
Data Structures and Algorithms

Circuit Analysis

Part 1

You work in the quality control department of a company that makes circuit boards. Your job is to check that every circuit board is printed correctly. For each circuit board you have to check, you are given a reference circuit diagram on which certain components are marked as pins, and certain connections between pins are indicated. You must ensure that all such required connections exist on the actual circuit board, and also that there are no erroneous connections. When the printed circuit does not match the specification, you must identify what is wrong with the circuit, which will help engineers detect whether a particular machine is consistently malfunctioning.

For this homework, we will simulate the above situation as follows:

Your input is

Two pixels are connected if there is a chain of orthogonally adjacent conductive pixels between them. Note that pins (blue pixels) are also conductive. Also note that diagonally adjacent conductive pixels are not connected.

We call a set of pins an island if every pair of pins in the set is connected.

The list of connections specifies connections that must be present in a working circuit. Creating these connections on a board will also create some other connections that might not be listed. Notice that connectivity is transitive; that is, if the list has the connections A-B and B-C, any satisfying circuit must also have the connection A-C. However, other unlisted connections that do not result from transitivity cannot be present in a working circuit.

An easy way to think of this is that the only allowed connections in a satisfying circuit are those that have to exist (by transitivity) after we make all the connections in the connection list.

Your program must output a list of faults in the input circuit. If the circuit satisfies the list of connections, this list will be empty.

Faults occur whenever pins in the circuit are connected when they shouldn't be or are not connected when they should be. An easy way to output faults would be to simply list all the pairs of pins that don't match the specification. But this would result in a great deal of redundancy. For example, suppose that A, B, C, D, E, and F are all supposed to be mutually connected according to the specification. The circuit 

A***B***C***D***E***F

clearly satisfies this. However, if we take away the middle connection, 

A***B***C   D***E***F

there are now nine pairs of pins (A-D, A-E, B-E, etc.) that are not connected with each other, even though only one change was made. We really want this to be one fault, not nine.

Therefore we will describe the faults in terms of islands in the input circuit.

  1. Open circuit
    An open circuit fault occurs when two islands in the circuit contain pins that should be connected.

  2. Short circuit
    A short circuit fault occurs when an island in the circuit contains pins that should be disconnected.

Your program must return a complete list of faults containing every open circuit and short circuit, together with representatives of the islands involved in these faults. You can use any pin contained in an island to represent it.

Build your list of faults using the following constructors:

The order of the list does not matter. It must contain only one element for every fault; no redundancies.

The following examples illustrate some possible inputs and outputs. Note that other outputs are possible, since there are several possible representative choices for each island. The circuits are enlarged versions of the sorts of images your program should accept as input (see support code below), and the output is in the format we expect.

Connection list: 

(list (make-connection (make-posn 0 2) (make-posn 2 2)))

Output: 

(list (make-open-circuit (make-posn 0 2) (make-posn 2 2))
      (make-short-circuit (make-posn 0 0)))

Connection list: 

(list (make-connection (make-posn 0 1) (make-posn 2 1))
      (make-connection (make-posn 2 1) (make-posn 0 2))
      (make-connection (make-posn 0 2) (make-posn 2 2)))

Output:
empty

Connection list: 

(list (make-connection (make-posn 0 0) (make-posn 3 2))
      (make-connection (make-posn 0 2) (make-posn 3 0)))

Output: 

(list (make-open-circuit (make-posn 0 2) (make-posn 3 2))
      (make-short-circuit (make-posn 0 2)))

Connection list: 

(list (make-connection (make-posn 0 0) (make-posn 4 0))
      (make-connection (make-posn 4 0) (make-posn 2 2))
      (make-connection (make-posn 6 0) (make-posn 4 2))
      (make-connection (make-posn 2 0) (make-posn 4 2)))

Output: 

(list (make-short-circuit (make-posn 2 0))
      (make-short-circuit (make-posn 2 2))
      (make-short-circuit (make-posn 4 0))
      (make-open-circuit (make-posn 2 0) (make-posn 4 0))
      (make-open-circuit (make-posn 6 0) (make-posn 2 2))
      (make-open-circuit (make-posn 2 0) (make-posn 4 2)))

Connection list: 

(list (make-connection (make-posn 0 0) (make-posn 1 2))
      (make-connection (make-posn 2 0) (make-posn 3 2))
      (make-connection (make-posn 4 0) (make-posn 1 2))
      (make-connection (make-posn 0 0) (make-pson 2 0)))

Output: 

(list (make-open-circuit (make-posn 0 0) (make-posn 2 0))
      (make-open-circuit (make-posn 0 0) (make-posn 4 0))
      (make-open-circuit (make-posn 0 0) (make-posn 1 2))
      (make-open-circuit (make-posn 0 0) (make-posn 3 2))
      (make-open-circuit (make-posn 2 0) (make-posn 4 0))
      (make-open-circuit (make-posn 2 0) (make-posn 1 2))
      (make-open-circuit (make-posn 2 0) (make-posn 3 2))
      (make-open-circuit (make-posn 4 0) (make-posn 1 2))
      (make-open-circuit (make-posn 4 0) (make-posn 3 2))
      (make-open-circuit (make-posn 1 2) (make-posn 3 2)))

We've provided some support code in the circuit-teach.ss teachpack that will help you manage the circuit images. The following structs and functions are defined in the support code: 

(define-struct posn (x y))
(define-struct circuit-node (color))
(define-struct connection (pin1 pin2))
(define-struct short-circuit (pin))
(define-struct open-circuit (pin1 pin2))

circuit-node is a struct used by the helper fuctions below. Its value is either 'black, 'white, or 'blue.

Here are a few test circuit board images:

alex_circuit.png
sparse_circuit.png
crowded_circuit.png
big_circuit.png

Answer the following questions in a readme file:

Part 2

Run your solution to part one on big_circuit.png and the list of connections defined as big-connections in the support code.

You've probably noticed that it's taking a while. Think about why this is.

Run your program on big_circuit.png again, but with a much smaller list of connections. Now remove many of the pins in big_circuit.png (using an image editor or circuit->image). Run your program again (with a correspondingly smaller connections list). Think about how these changes affect the program's overall runtime.

Give a big-O analysis of your program. Be sure to talk about each of the different parts of your code separately, and to clearly define any variables you use in your analysis.

Part 3

Do you think this problem can be solved more efficiently? Identify the bottlenecks in the strategy you use, and discuss possible strategies for improving them.

What to turn in: