7
1
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:
The number
N
, to denote how manySPT
s there are. (I will describe anSPT
below.)N
lines, each containing two numbersA
andB
representing numbered electrodes on a circuit board, followed by oneSPT
.One line containing two numbers
P
andQ
denoting which two electrodes to measure the resistance between.
An SPT
is a "series-parallel tree", a way to describe a series-parallel circuit in a tree format.
A valid SPT
is either:
The number 1, representing a single resistor.
S( )
, enclosing a number followed by zero or moreP( )
SPTs.P( )
, enclosing a number followed by zero or moreS( )
SPTs.
Examples of valid SPT
s:
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 SPT
s:
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.
Specifications
Your program must work for any numerator and denominator up to 150 000
.
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.
Testing data
The input
3 / 8
might return
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.
The input
5 / 6
might return:
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 1
through 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.
1This paper might interest you. This resistor network synthesis problem is closely related to a geometric [integer] tiling problem as well, tiling a rectangle with squares as explained in that paper. – Fizz – 2015-11-23T00:42:25.540
Most of your valid STPs are not valid according to your definition because of the presence of
2
and other illegal numbers (which seem to expand to a series of1
s). Also, what doS()
andP()
do? Interpreting them as 'series' and "parallel", they would be defined as the sum and 1/sum of their inputs respectively. And why the requirement of exactly one numeric input? Blah blah blah oh wait this question is three years old what am I doing. – CalculatorFeline – 2017-02-28T00:40:45.2832I don't understand the output format. Are you trying to give people an option between always outputting
1\n0 1 SPT\n0 1
vs a solution which only uses SPTs of the form1
? Can you give some test cases for people to use in development? – Peter Taylor – 2014-02-09T16:13:30.027Will do. I was kinda rushed this morning, so I left the bare spec there. I'll put in a few test cases now. – Joe Z. – 2014-02-09T19:19:07.633
This isn't a duplicate, but is the link to an earlier question intentional? – Peter Taylor – 2014-02-10T18:31:45.587
I don't see a link in the question. Do you mean a conceptual link? – Joe Z. – 2014-02-10T18:56:50.050
If it's the latter, though, yes, it did have a bit to do with the nontrivial resistance diagram evaluator problem. For example, to verify that your circuit does indeed have that sort of resistance, you'll most likely need an evaluator of that sort. – Joe Z. – 2014-02-10T18:58:28.467