21
\$\begingroup\$

In physics, like electric charges repel, and unlike charges attract.

The potential energy between two unit charges separated by a distance d is 1/d for like charges and -1/d for unlike charges. The potential energy of a system of charges is the sum of the potential energies between all pairs of charges.

Challenge

Determine the potential energy of a system of unit charges represented by a string.

This is , so the shortest solution in bytes wins.


Input

A nonempty multiline string, consisting of only +, -, and newlines, with each line a constant width. The + and - represent charges of +1 and -1 respectively. For example, the following string:

    + -
 +     

(considering the top-left to be the origin) represents a system with positive charges at (4,0) and (1,-1) and a negative charge at (6,0).

Alternatively, you may take input as a list of lines.

Output

A signed real number representing the potential energy of the system of charges. Output should be correct to four significant figures or 10-4, whichever is looser.

Test cases:

   - 
     

Should output 0. There are no pairs of charges to repel or attract, and the whitespace doesn't change anything.

+  
  -

There are only two charges; they are 1 unit away in the vertical direction and 2 units away in the horizontal direction, so their distance is sqrt(5). Output should be -1/sqrt(5)=-0.447213595.

+       -
-       +

Should give -2.001930531.

 - -- -+ - - -+-++-+
 +-- + +-- + ++-++ -
---++-+-+- -+- - +- 
-- - -++-+  --+  +  
-   + --+ ++-+  +-  
--  ++- + +  -+--+  
+ +++-+--+ +--+++ + 
-+- +-+-+-+  -+ +--+
- +-+- +      ---+  
-     - ++ -+- --+--

Should give -22.030557890.

---+--- ++-+++- -+ +
-+ ---+++-+- +- +  +
---+-+ - ----  +-- -
 -   + +--+ -++- - -
--+ - --- - -+---+ -
+---+----++ -   +  +
-+ - ++-- ++-  -+++ 
 +----+-   ++-+-+  -
++- -+ -+---+  -- -+
+-+++ ++-+-+ -+- +- 

Should give 26.231088767.

\$\endgroup\$
  • 1
    \$\begingroup\$ Plus points for implementing periodic boundary conditions and computing the Madelung energy. \$\endgroup\$ – Andras Deak Dec 30 '15 at 11:15
  • 1
    \$\begingroup\$ @AndrasDeak That would be interesting. \$\endgroup\$ – lirtosiast Dec 30 '15 at 21:53
3
\$\begingroup\$

Pyth, 34 bytes

smc*FhMd.atMd.cs.e+RkCUBxL" +"b.z2

Demonstration

First, we convert each character to +1 for +, -1 for -, and 0 for . Then, each number is annotated with its position in the matrix. At this point, we have a matrix that looks like:

[[[-1, 0, 0], [-1, 1, 0], [-1, 2, 0], [1, 3, 0], [-1, 4, 0], [-1, 5, 0], [-1, 6, 0]],
 [[1, 0, 1], [1, 1, 1], [-1, 2, 1], [-1, 3, 1], [0, 4, 1], [1, 5, 1], [0, 6, 1]]]

The code that reaches this point is .e+RkCUBxL" +"b.z

Then, we flatten this matrix into a list and take all possible pairs, with .cs ... 2.

Then, he find the distance between the pair with .atMd, and the sign of the potential with *FhMd, divide, and sum.

\$\endgroup\$
6
\$\begingroup\$

CJam, 51 chars

Counting all pairs, filtering Inf/NaN out and dividing by two:

q_N#:L;N-" +"f#ee2m*{z~:*\Lfmd2/:.-:mh/}%{zL<},:+2/

Alternatively, filtering coordinates first so we count each pair once and don't run into Inf/NaN:

q_N#:L;N-" +"f#ee2m*{0f=:<},{z~:*\Lfmd2/:.-:mh/}%:+

Explanation (old)

q                        Get all input.
 _N#:L;                  Store the line width in L.
       N-                Flatten it into one long line.
         :i              Get all ASCII values.
           :(3f%:(       Map space to 0, + to 1, - to -1.
                  ee     Enumerate: list of [index, sign] pairs.
                    2m*  Get all possible pairs.

{                        }%     For each pair:
 e_~                              i1 s1 i2 s2
    @*                            i1 i2 s        (multiply signs)
      \aa@aa+                     s [[i2] [i1]]  (put indices in nested list)
             Lffmd                s [[x2 y2] [x1 y1]]  (divmod by L)
                  :.-             s [xD yD]      (point diff)
                     :mh          s d            (Euclidean dist.)
                        /         s/d            (divide)

{zL<},                   Filter out infinite results.
      :+2/               Sum all charges, and divide by two.
                           (We counted each pair twice.)
\$\endgroup\$
  • 3
    \$\begingroup\$ So explanation is TBA? :P \$\endgroup\$ – Rɪᴋᴇʀ Dec 29 '15 at 17:05
  • 2
    \$\begingroup\$ Did you write this while it was sandboxed, or are you just really fast? \$\endgroup\$ – lirtosiast Dec 29 '15 at 17:41
  • \$\begingroup\$ I'm quite fast :) The first version was "the simplest thing that worked", which took me only a couple of minutes to write, so I immediately posted that, then golfed it down over the next half hour. \$\endgroup\$ – Lynn Dec 29 '15 at 17:46
4
\$\begingroup\$

Haskell, 149 144 bytes

z=zip[0..]
g n|f<-[(x,y,c)|(y,r)<-z$lines n,(x,c)<-z r,c>' ']=sum[c%d/sqrt((x-i)^2+(y-j)^2)|a@(x,y,c)<-f,b@(i,j,d)<-f,a/=b]/2
c%d|c==d=1|1<2= -1

Usage example:

*Main> g " - -- -+ - - -+-++-+\n +-- + +-- + ++-++ -\n---++-+-+- -+- - +- \n-- - -++-+  --+  +  \n-   + --+ ++-+  +-  \n--  ++- + +  -+--+  \n+ +++-+--+ +--+++ + \n-+- +-+-+-+  -+ +--+\n- +-+- +      ---+  \n-     - ++ -+- --+--"
-22.030557889699853

f is a list of all triples (x-coord, y-coord, unit charge). g calculates the potential energy for all combinations of two such triples which are not equal, sums them and divides the result by 2.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 133

->n{t=i=j=0.0
c=[]
n.tr(' ',?,).bytes{|e|e-=44
z="#{j}+#{i}i".to_c
i+=1
e<-1?i=0*j+=1:(c.map{|d|t+=d[0]*e/(d[1]-z).abs};c<<[e,z])}
t}

Maintains an array of previous charges in the form of tuples [charge, location(complex number)] and compares each new charge with this list, before appending it to the list.

All spaces in the input are replaced with commas. This enables the following assignment by subtracting 44 from their ascii code:

symbol  charge (internal representation)
+        -1
,         0
-        +1

The fact that the program considers + to be -1 and - to be +1 makes no difference to the final result. The fact that the program goes to the effort of calculating the influence of the charges of 0 for the spaces makes no difference, apart from slowing it down a bit :-)

Ungolfed in test program

g=->n{
  t=i=j=0.0                           #t=total potential; i and j are coordinates of charge.
  c=[]                                #array to store tuples: charge + location (complex number).
  n.tr(' ',?,).bytes{|e|              #replace all spaces with commas, then iterate through characters.
    e-=44                             #subtract 44 from ascii code: + -> -1; comma -> 0; - -> 1
    z="#{j}+#{i}i".to_c               #position of current character as complex number
    i+=1                              #advance x coordinate to next character.
    e<-1?i=0*j+=1:                    #if current character is newline, set i to zero and advance j instead,
    (c.map{|d|t+=d[0]*e/(d[1]-z).abs};#else add up the contribution for interaction of the current charge with all previous charges, 
    c<<[e,z])}                        #and append the current charge to the list of previous charges.
t}                                    #return t

p g[
'+       -
-       +'
]

p g[
' - -- -+ - - -+-++-+
 +-- + +-- + ++-++ -
---++-+-+- -+- - +- 
-- - -++-+  --+  +  
-   + --+ ++-+  +-  
--  ++- + +  -+--+  
+ +++-+--+ +--+++ + 
-+- +-+-+-+  -+ +--+
- +-+- +      ---+  
-     - ++ -+- --+--'
]
\$\endgroup\$
3
\$\begingroup\$

MATL, 39 42 bytes

`jt]N$v'- +'FT#m2-I#fbbhtZPwt!**1w/XRss

Works in current release (5.1.0). The compiler runs on Matlab or Octave.

Each line is a separate input. End is signalled by inputting an empty line.

Examples

>> matl
 > `jt]N$v'- +'FT#m2-I#fbbhtZPwt!**1w/XRss
 > 
> +       -
> -       +
> 
-2.001930530821583

>> matl
 > `jt]N$v'- +'FT#m2-I#fbbhtZPwt!**1w/XRss
 > 
>  - -- -+ - - -+-++-+
>  +-- + +-- + ++-++ -
> ---++-+-+- -+- - +- 
> -- - -++-+  --+  +  
> -   + --+ ++-+  +-  
> --  ++- + +  -+--+  
> + +++-+--+ +--+++ + 
> -+- +-+-+-+  -+ +--+
> - +-+- +      ---+  
> -     - ++ -+- --+--
> 
-22.03055788969994

Explanation

`jt]           % keep inputting lines until an empty one is found
N$v            % concatenate all inputs vertically. This removes the last empty line
'- +'FT#m      % replace '-', ' ', '+'  by numbers 1, 2, 3
2-             % transform into -1, 0, 1 for '-', ' ', '+'
I#f            % find rows, columnss and values of nonzeros
bbh            % concatenate rows and columns into 2-col matrix or coordinates
tZP            % compute pair-wise distances for those coordinates
wt!*           % generate matrix of signs depending on signs of charges
*              % multiply distances by signs, element-wise
1w/            % invert element-wise
XR             % keep part over the diagonal
ss             % sum along colums, then rows
               % (output is implicitly printed)
\$\endgroup\$
3
\$\begingroup\$

Lua, 293 255 246 228 Bytes

e=0l={}p={}i=1while l[i-1]~=""do l[i]=io.read()for k=1,#l[i]do c=l[i]:sub(k,k)if(c>" ")then for h,v in ipairs(p)do e=e+(v.s==c and 1 or-1)/math.sqrt((v.y-i)^2+(v.x-k)^2)end table.insert(p,{s=c,x=k,y=i})end end i=i+1 end print(e)

Ouch, 228 bytes...I can probably golf this significantly, but I'll post it here for now. Probably update it later tonight with a few more musings and (hopefully) some improvements to the length.

Ungolfed

e=0l={}p={}i=1
while l[i-1]~=""do 
    l[i]=io.read()
    for k=1,#l[i]do
        c=l[i]:sub(k,k)
        if(c>" ")then
            for h,v in ipairs(p) do
                e=e+(v.s==c and 1 or-1)/math.sqrt((v.y-i)^2+(v.x-k)^2)
            end
            table.insert(p,{s=c,x=k,y=i})
        end
    end
    i=i+1 
end

print(e)

Update 255 Bytes: Removed old bottom two for loops, processing is now done as strings are added to string array.

Update 246 Bytes: Replaced c=="+"or"-"==c with c>" " as per nimi's suggestion. Great idea, thanks!

Update 228 Bytes: If statement could be removed completely by inserting in table after the for loop, saving quite a few bytes.

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

Mathematica 223 bytes

Still golfing to do.

f[{{c1_,p1_},{c2_,p2_}}]:=N[(c1 c2)/EuclideanDistance[p1,p2],13];
h[charges_]:=Tr[f/@Subsets[DeleteCases[Flatten[Array[{r[[#,#2]],{#,#2}}&,Dimensions[r=Replace[Characters[charges],{"+"-> 1,"-"->-1," "->0},2]]],1],{0,_}],{2}]]

Last test case:

h[{" - -- -+ - - -+-++-+", " +-- + +-- + ++-++ -", 
  "---++-+-+- -+- - +- ", "-- - -++-+  --+  +  ", 
  "-   + --+ ++-+  +-  ", "--  ++- + +  -+--+  ", 
  "+ +++-+--+ +--+++ + ", "-+- +-+-+-+  -+ +--+", 
  "- +-+- +      ---+  ", "-     - ++ -+- --+--"}]

-22.030557890

\$\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.