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

Question

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.

Answer 1

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'

Answer 2

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.