# 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:

• an image of the circuit board, where blue pixels represent pin locations and black (and blue) pixels represent conductive material.

• a list of connections, where each connection is represented by a struct containing two pins. Pins are identified by posn structs corresponding to their position on the circuit. `(make-posn 0 0)` is the upper left corner of the image. There may be pins on the board which are not included in any connection in the connentions list.

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:

• `(make-open-circuit pin1 pin2)`
creates a fault for an open circuit between the islands containing the given pins. Note that `pin1` and `pin2` do not need to be the pins that should be connected, so long as the pins that should be connected are in the same islands as `pin1` and `pin2`, respectively.
• `(make-short-circuit pin)`
creates a fault for a short circuit within the island containing the given pin.

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`.

• `ternary->circuit: (list-of (list-of int)) → (list-of (list-of circuit-node))`
Converts a ternary representation of a circuit into a circuit-node represenation by changing `2` to `'blue`, `1` to `'black`, and `0` to `'white`. This function should be helpful when creating your own test circuits.

• `image->circuit: image → (list-of (list-of circuit-node))`
Converts a circuit board image to a list of lists of circuit-nodes.

• `bigimage->circuit: image → (list-of (list-of circuit-node))`
Converts a magnified circuit board image (where every 10x10px square represents a single pixel) to a list of list of circuit-nodes.

• `circuit->image: (list-of (list-of circuit-node)) → image`
Takes a circuit and generates a circuit board image.

• `circuit->bigimage: (list-of (list-of circuit-node)) → image`
Takes a circuit and generates a magnified circuit board image. This function is very helpful if you want to be able to see the circuit board images you are working with.

• `random-circuit: int int number number → (list-of (list-of circuit-node))`
Generates a random circuit with height and width specified by the first two arguments. The third argument specifies the probability (between 0 and 1) that each pixel is conducting, and the fourth specifies the probability (between 0 and 1) that each conducting pixel contains a pin.

Here are a few test circuit board images:

• How do you find islands?
• How do you detect open circuits?
• How do you detect short circuits?

### 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:

• A Scheme file, `circuit-analysis.ss`, containing your full solution to part 1.
• A file, `readme.[txt,pdf,doc]`, containing answers to the questions in part 1.
• A file, `analysis.[txt,pdf,doc`] with your answers for Parts 2 and 3.
As always, these files must be in plain text, pdf, or, if you really must, Word format. If you use Word, we will accept only Word 2003 (`.doc`) files. If you are using Word 2007, you should export to a pdf. We will not accept Word 2007 (`.docx`) files because we cannot read them.