You are a contractor for a company who designs electrical circuits for the various products they make. One day, the company accidentally gets a huge shipment of one-ohm resistors and absolutely nothing else, and give you the task of putting them to good use in the newest products they're making.
Your task is to build a program that takes a positive rational number as input, in the following form:
a / b
and return a resistor diagram with the exact given resistance, that uses as few one-ohm resistors as possible.
Your resistor diagram will consist of:
N, to denote how many
SPTs there are. (I will describe an
Nlines, each containing two numbers
Brepresenting numbered electrodes on a circuit board, followed by one
One line containing two numbers
Qdenoting which two electrodes to measure the resistance between.
SPT is a "series-parallel tree", a way to describe a series-parallel circuit in a tree format.
SPT is either:
The number 1, representing a single resistor.
S( ), enclosing a number followed by zero or more
P( ), enclosing a number followed by zero or more
Examples of valid
1 <- has a resistance of 1 S(1) <- equivalent to 1 and P(1) S(2, P(3)) <- has a resistance of 7/3, using 5 resistors P(1, S(2), S(3), S(4, P(2))) <- has a resistance of 18/37, using 12 resistors
Examples of invalid
2 <- the two resistors are in an unknown configuration. Use P(2) or S(2) instead. P(2, P(1)) <- use P(3) instead. P(4, P(1, S(3), S(2))) <- use P(5, S(3), S(2)) instead.
Your program must work for any numerator and denominator up to
Your program's source code, excluding any imported standard or third-party libraries, must not exceed one megabyte (1,048,576 bytes) total.
Your program will be tested on a specific, randomly chosen set of 10,000 fractions (to be determined at a later date), and scored on how few resistors it requires to build all 10,000 circuits. The program that uses the fewest resistors is the winner.
3 / 8
1 1 2 S(0, P(8), P(4)) 1 2
to represent a series of 8 resistors and then 4 resistors in parallel. This may not be the optimal solution; but for the purposes of this problem, it is valid output.
5 / 6
12 1 2 1 1 3 1 1 5 1 2 4 1 2 6 1 3 4 1 3 7 1 4 8 1 5 6 1 5 7 1 6 8 1 7 8 1 1 8
to represent a cube of one-ohm resistors with vertices numbered
8, having its resistance measured between opposite corners. Of course it is possible to just do
S(P(2), P(3)) using just five resistors, but this is an example of how the notation is used to represent non-series-parallel diagrams.