7
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ I 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? \$\endgroup\$ – Peter Taylor Feb 9 '14 at 16:13
  • \$\begingroup\$ Will do. I was kinda rushed this morning, so I left the bare spec there. I'll put in a few test cases now. \$\endgroup\$ – Joe Z. Feb 9 '14 at 19:19
  • \$\begingroup\$ This isn't a duplicate, but is the link to an earlier question intentional? \$\endgroup\$ – Peter Taylor Feb 10 '14 at 18:31
  • \$\begingroup\$ I don't see a link in the question. Do you mean a conceptual link? \$\endgroup\$ – Joe Z. Feb 10 '14 at 18:56
  • 1
    \$\begingroup\$ This 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. \$\endgroup\$ – Fizz Nov 23 '15 at 0:42
3
\$\begingroup\$

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'
\$\endgroup\$
  • \$\begingroup\$ Hmm. I had no idea the "link" you were talking about was in fact the Stern-Brocot tree. \$\endgroup\$ – Joe Z. Feb 10 '14 at 20:57
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.