Build a program that creates a minimal one-ohm resistor diagram for a given resistance

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 many SPTs there are. (I will describe an SPT below.)

  • N lines, each containing two numbers A and B representing numbered electrodes on a circuit board, followed by one SPT.

  • One line containing two numbers P and Q 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 more P( ) SPTs.

  • P( ), enclosing a number followed by zero or more S( ) SPTs.

Examples of valid SPTs:

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

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.

Joe Z.

Posted 2014-02-09T15:37:57.627

Reputation: 30 589

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 of 1s). Also, what do S() and P() 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.283

2I 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 form 1? Can you give some test cases for people to use in development? – Peter Taylor – 2014-02-09T16:13:30.027

Will 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

Answers

3

For series-parallel circuits with few resistors, the resistances which can be created with n resistors but not with fewer are the numbers on the nth level of the Stern-Brocot tree. (This breaks later on, with 5/6 = 1/2 + 1/3 apparently a minimal counterexample).

Instead of mapping from position in the Stern-Brocot tree to an S-P expression, it turns out to be much more convenient to use the Calkin-Wilf tree; its nodes at a given depth are permutations of the Stern-Brocot tree's nodes at that depth, but it has a different parent-child relationship: the left child of m/n is m/(m+n) = (1^-1 + (m/n)^-1)^-1 = P(1, m/n), and the right child of m/n is (m+n)/n = 1 + m/n = S(1, m/n).

GolfScript

# Parse input
'/'/' '*~
# Stack: numerator denominator
{
    # numerator denominator
    1$1$<{
        # n/d is less than 1, so parent is n/(d − n) and we're looking at Parallel
        ', P('@@.2$/@@1$%
        # ', P(' d/n n d%n
    }{
        # n/d >= 1, so parent is (n - d)/d and we're looking at Series
        ', S('@@1$1$/@2$%@
        # ', S(' n/d n%d d
    }if
    # Loop until we get to 0/1 or 1/0
    1$1$*
}do;;
# Stringify
]''*
# Trim leading ', '
2>.
# Close the parentheses
'('/,(')'*+
# Add the boilerplate
'1
0 1 '\'
0 1'

Peter Taylor

Posted 2014-02-09T15:37:57.627

Reputation: 41 901

Hmm. I had no idea the "link" you were talking about was in fact the Stern-Brocot tree. – Joe Z. – 2014-02-10T20:57:20.117

0

Python

As a last-place reference solution, here is a naïve solution that always works:

frac = raw_input().split(" / ")
num = int(frac[0])
den = int(frac[1])
print 1
print 1, 2,

pstr = ""
for x in range(den):
    pstr += "S(%s), " % num
pstr = pstr[:-2]

print "P(%s)" % pstr

print 1, 2

Always creates n parallel of m resistor series for the resistance m/n, using mn resistors each time.

Joe Z.

Posted 2014-02-09T15:37:57.627

Reputation: 30 589