10
\$\begingroup\$

Good Afternoon Golfers,

Our challenge for today is inspired by XKCD comics 356 and 370. We're going to write a program to calculate the resistance of a group of resistors. A forewarning that this is nearly tough enough to warrant being a code challenge, however I think that there is a certain art to writing slightly more complex programs in a golfed format. The lowest amount of characters wins.

Calculating the resistance relies on the following two formulas:

  • If the resistors are in series, the resistance is the sum of the each resistor's resistance
  • If the resistors are in parallel, the resistance is the inverse of the sum of the inverse of the resistance of each resistor

So - for example:

Example of calculating resistance

Your challenge is to, in the least amount of characters possible, calculate the resistance of a group of up to 64 resistors. My apologies for the complexity, particularly of the input rules. I've attempted to define them in such a way that every language will be usable.

  • Each resistor will be connected to 2 or more other resistors.

  • The input is guaranteed to be valid, with only one entry and one exit point, which will connect

  • The network will be series-parallel to prevent requiring more maths then what is presented

  • Input will be via file, argument or stdin, depending on what is appropriate for your language.

  • Input will consist of a series of newline or forward slashed separated statements consisting of an integer of the resistance of the resistor, and spaces separating the IDs of the resistors that one side of the resistor is connected to.

  • The ID of the first resistor will be 1, incrementing by one for each successive resistor

  • The start will always have an ID of 0

  • The final resistor will always have a resistance of 0 ohms, and only have the connections defined in its line

For example:

Example 2

Could be represented as

3 0
6 1
1 0
5 0
0 2 3 4
  • Output can be to stdout or file. It may be represented in one of the following ways:
    • A number with a minimum of 2 decimal places, followed by a newline
    • A fraction consisting of an integer (the numerator), a forward slash and another integer (the denominator), followed by a newline. The fraction does not need to be the to be in its lowest form - 4/4 or 10/8 are, for instance acceptable. The fraction must be accurate within 1/100. There is no bonus for being perfectly accurate - this is provided is a crutch to enable languages without fixed or floating point operations to compete.

I hope that covers all the points. Good luck!

\$\endgroup\$
  • \$\begingroup\$ / is not a backslash. Did you mean `\` or a forward slash? \$\endgroup\$ – John Dvorak Mar 9 '13 at 6:05
  • \$\begingroup\$ Are we allowed to produce incorrect results if the input is not a series-parallel network? \$\endgroup\$ – John Dvorak Mar 9 '13 at 6:07
  • 1
    \$\begingroup\$ the Wheatstone bridge is not series-parallel if you replace the center voltmeter with a resistor \$\endgroup\$ – John Dvorak Mar 9 '13 at 6:26
  • 1
    \$\begingroup\$ will resistors always wire into those with a lower ID or they may be input in any order? Is 1 2/1 0/0 1 valid? \$\endgroup\$ – John Dvorak Mar 9 '13 at 8:07
  • 9
    \$\begingroup\$ The parallel example is wrong. It should be 15/23, not 15/8. \$\endgroup\$ – Peter Taylor Mar 9 '13 at 9:42
6
\$\begingroup\$

APL 190

Index origin 1. First loop (s) combines all resistors wired in series, second (p) those wired in parallel and the repeat to first loop to combine any parallel resistors now in series. The specification of the final zero resistor appears to be redundant.

r←¯1↓⍎¨(c≠'/')⊂c        
o←⊃↑¨r                  
r←⊃1↓¨r                 
s:→(0=+/n←1=+/×r)/p     
n←↑n/i←⍳↑⍴r             
o[n-1]←+/o[n-0 1]       
o←(i←n≠i)/o             
r←i⌿r                   
r←r-r≥n                 
→s                      
p:n←1⍪2≠/r[;1]          
r←((⍴r),1)⍴r←¯1++\n~0   
o←∊1÷¨+/¨1÷¨n⎕penclose o
→(1<⍴o)/s               
3⍕o                     
' '  

Tested over the examples in the question plus a slightly more complicated one:

      Input: '5 0/3 1/1 2/0 2'
 9.000

      Input: '3 0/1 0/5 0/0 1 2 3'
 0.652

      Input: '3 0/6 1/1 0/5 0/0 2 3 4'
 0.763

      Input: '2 0/2 1/2 0/2 0/2 4/2 5/2 2 3 6/2 7/2 2 3 6/0 8 9'
 2.424
\$\endgroup\$
  • \$\begingroup\$ Always amazed by APL answers - they look absolutely insane. The final resistor was just to give something for the other resistors to connect to - a dummy end link. Well done! \$\endgroup\$ – lochok Mar 10 '13 at 21:32
  • \$\begingroup\$ I think you can save a couple of characters. Replace the first two lines with o←⊃↑¨r←¯1↓⍎¨(c≠'/')⊂c. This pattern is applicable in a couple of places. \$\endgroup\$ – FUZxxl Apr 7 '15 at 17:24
5
\$\begingroup\$

Python, 329 chars

import sys
N=[[1]]+[map(int,x.split())for x in sys.stdin]
N[-1][0]=1
n=len(N)
S=[set([i])for i in range(2*n)]
for x in range(n):
 C=S[2*x]
 for y in N[x][1:]:C|=S[2*y+1]
 for x in C:S[x]|=C
V=[0]*(2*n-1)+[1]
for k in range(999):
 for i in range(1,2*n-1):V[i]+=sum((V[j^1]-V[i])/N[j/2][0]for j in S[i])/9./len(S[i])
print 1/V[1]-2

Calculates the resistance by doing a voltage relaxation on the circuit. First it tacks on a 1 ohm resistor to the start and changes the last resistor from 0 ohm to 1 ohm. Then it sets the input voltage to 0 and the output voltage to 1 volt. After simulating current flow through the network, the network resistance is calculated using the voltage drop across the first 1 ohm resistor.

Each resistor is given two numbers, the number for its left terminal and the number for its right terminal. Resistor r's left terminal is 2*r and its right terminal is 2*r+1. The input is used to calculate S, the sets of terminals that are connected together. Each terminal is given a voltage V[t] and a relaxation is done by raising the voltage if current is net flowing into a terminal set and lowering the voltage if current is net flowing out.

\$\endgroup\$
2
\$\begingroup\$

(This is a comment, but I can't do ascii art in a real comment...)

How is something like this inputted?

    --1--     --3--
   /     \   /     \
---       ---       --0--
   \     /   \     /
    --2--     --4--

In particular, what are 3 and 4 connected to? 1 or 2, or both 1 and 2?

\$\endgroup\$
  • \$\begingroup\$ Both one and two \$\endgroup\$ – lochok Mar 10 '13 at 9:25

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.