Programming with
Data Structures and Algorithms

Circuit Analysis

Part 1

You work in the quality control department of a microchip factory and your job is to help identify which machines are creating erroneous circuit boards so that those machines can be fixed or replaced. The circuit boards your company produces are made up of three components: the board itself, pins, and wires which connect pins to each other. To help you identify erroneous circuits, you are given a reference sheet for each board that the factory prints which tells you which pins must be connected to ensure that it will function properly.

In this assignment, your input is:

Two points on the circuit board are considered connected if electricity can flow between the points. This is true only if both of the following conditions are met:

Please note that diagonally adjacent conductive pixels are not necessarily connected. Also note that connections are transitive. In other words, if connections A-B and B-C exist, then connection A-C is implicitly present as well. Therefore, there may be connections which are necessary for the circuit to function that only appear implicitly on the reference sheet. However, connections which are neither implicitly nor explicitly specified by the reference sheet will cause an error.

Your program should output all errors which exist in the circuit board. Faults occur whenever pins in the circuit are connected when they should not be or are not connected when they should be. Although it would be simple to output a list of pairs which do not match the specification, this would result in a great deal of redundancy. Consider the case where pins A, B, C, D, E, and F are all supposed to be mutually connected. The circuit

A-B-C-D-E-F

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

A-B-C D-E-F

now has nine pairs of pins (A-D, A-E, A-F, B-D, etc.) that are not connected with each other, even though only one wire was removed. This should really only be one fault, not nine.

At this point, it will be useful to notice that the set of pins on a board can be separated into groups based on their connections. For instance, in the board above, the specification sheet said that the pins should all be in one group (A,B,C,D,E,F), whereas the board had them split into groups (A,B,C) and (D,E,F). These groups of mutually connected pins will be referred to as islands.

We will describe each type of fault in terms of islands in the circuit we are verifying:

To clarify, here is a brief example displaying both types of faults. This picture shows how the pins should be grouped based on their reference sheet (the boxes show islands):

and this picture shows how they are actually connected in the manufactured circuit:

In this example, there is an open circuit between the island containing pin A and the island containing pin B because A and B should be be connected, and there is a short circuit in the island containing C because pins C and D should not be connected. There are no other faults in this example.

Your program must return a complete list of faults containing every open and short circuit exactly once. You can use any pin contained in an island to represent it (we arbitrarily chose A, B, and C above). You should build your list of faults using the following constructors:

The order of the list of faults does not matter, but it must contain exactly only one element for each fault.

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. It would be worthwhile to ensure your solution outputs similar results for all of the following examples, since if it doesn't you are not adhering to the spec and will lose points.


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-posn 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 have provided some support code in the circuit-support.rkt file. If you download and then require it, it 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 color is either 'black, 'white, or 'blue.

Note that while the contracts below follow the contracts built into the cs019 lang, the signatures (Posn$, CircuitNode$, etc) are not defined by the support code. It is your responsibility to define these.

The entry point to your program should have the following signature:

analyze-circuit-image : (Image$ (Listof: Connection$) -> (Listof: (or: OpenCircuit$ ShortCircuit$))

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 have probably noticed that it is 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 overall runtime of the program.

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: