10
\$\begingroup\$

Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A.

The idea is to create a program that given a sequence (array), returns its equilibrium index (any) or -1 if no equilibrium indexes exist.

\$\endgroup\$

12 Answers 12

6
\$\begingroup\$

Golfscript 17 16

Since the form of the input isn't specified, this takes a string in Golfscript array format from stdin.

~0\{1$+.@+\}/])?

So run as e.g.

golfscript.ry eqindex.gs <<<"[-7 1 5 2 -4 3 0]"

The idea is very simple: it takes an array of A_i and maps to an array of A_i + 2 SUM_{j<i} A_j and then looks for the first index which is equal to the sum of the whole array.


For @mellamokb's challenge I offer:

~0\{1$+.@+\}/:S;]:A,,{A=S=},`

for 29 chars.

\$\endgroup\$
  • \$\begingroup\$ Since you easily have the shortest solution, I proclaim you must return all of the indexes, not just the first one :) \$\endgroup\$ – mellamokb May 4 '11 at 17:30
  • \$\begingroup\$ @mellamokb, with my compliments. \$\endgroup\$ – Peter Taylor May 4 '11 at 22:29
  • \$\begingroup\$ Cool! Now I've got some more GolfScript learning to do... \$\endgroup\$ – mellamokb May 5 '11 at 2:27
5
\$\begingroup\$

Python - 72 chars

A=input()
print[i for i in range(len(A))if sum(A[:i])==sum(A[i+1:])]or-1

Takes comma separated input

\$\endgroup\$
  • \$\begingroup\$ Awesome... this one returns all the equilibrium indexes... really cool. \$\endgroup\$ – Cristian May 4 '11 at 13:58
  • \$\begingroup\$ @Christian: Mine does so, too. \$\endgroup\$ – FUZxxl May 4 '11 at 18:29
  • \$\begingroup\$ I see :) I actually don't know how to run haskell code... will have to study. \$\endgroup\$ – Cristian May 5 '11 at 4:08
  • \$\begingroup\$ Christian: There is ghc, a compiler and hugs, an interpreter. I'd suggest downloading hugs. It's better then downloading ghc, because hugs is about 7 MiB, while the whole ghc distribution is about 300 MiB. Using hugs, you can just type runhugs FILE.hs to run program FILE.hs. \$\endgroup\$ – FUZxxl May 6 '11 at 13:03
5
\$\begingroup\$

Haskell (95 83)

e l=[n|n<-[0..length l-1],sum(take n l)==sum(drop(n+1)l)]
main=interact$show.e.read

Reads a list in Haskell style from stdin, eg.

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

and returns a Haskell style list of the indices, eg.

[3,6]

The result is [], if there is no index.

Please tell me, if your spec wants a different behavior.

Edits:

  • (95 → 83): list comprehension is more breve
\$\endgroup\$
4
\$\begingroup\$

C - 96

a[99],*p=a,s;main(){for(;scanf("%d",p)>0;s+=*p++
);for(;p>a;s-=*p)(s-=*--p)||printf("%d\n",p-a);}

Note that this prints the equilibrium indices in reverse order.

Sample usage:

$ ./equilibrium <<< "-7 1 5 2 -4 3 0"
6
3
\$\endgroup\$
3
\$\begingroup\$

Ruby (83 77)

a=*$<.map(&:to_i)
p (0...a.size).select{|x|a[0..x].reduce(:+)==a[x..-1].reduce(:+)}

Edit: Shorter version as suggested by Ventero:

a=$<.map &:to_i
p (0...a.size).select{|x|eval"#{a[0..x]*?+}==#{a[x..-1]*?+}"}

Input is one number per line, output is comma separated list of indexes in square brackets.

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need the parentheses in the first line, and you can save a few chars by using join + eval to get the sums: p (0...a.size).select{|x|eval"#{a[0..x]*?+}==#{a[x..-1]*?+}"} (note that this is for Ruby 1.9, since it uses character literals as strings) \$\endgroup\$ – Ventero May 9 '11 at 17:57
  • \$\begingroup\$ Great suggestions, thanks! Kind of annoying that Array#sum isn't in Ruby core. \$\endgroup\$ – Lars Haugseth May 9 '11 at 20:48
  • \$\begingroup\$ If I remove the parantheses in the first line, I get: "SyntaxError: (irb):17: syntax error, unexpected tAMPER, expecting $end" \$\endgroup\$ – Lars Haugseth May 9 '11 at 20:54
  • \$\begingroup\$ There has to be a space between map and the ampersand. And you don't need the splat operator in front of the $< either, so all in all the line would look like this: a=$<.map &:to_i. ;) \$\endgroup\$ – Ventero May 9 '11 at 21:51
  • \$\begingroup\$ Ah, thanks again, it was the splat that ruined the syntax. \$\endgroup\$ – Lars Haugseth May 9 '11 at 22:42
2
\$\begingroup\$

JavaScript (161)

P=parseInt;L=prompt().split(',');S=function(A)A.reduce(function(a,b)P(a)+P(b),0);R=[i for(i in L)if(S(L.slice(0,i))==S(L.slice(P(i)+1)))];alert(R.length>0?R:-1);

http://jsfiddle.net/6qYQv/1/

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

scala, 108

val l=readline().split(" ").map(w=>w.toInt)
for(i<-0 to l.length-1
if l.take(i).sum==l.drop(i+1).sum)yield i
\$\endgroup\$
2
\$\begingroup\$

J (12 characters)

A monadic verb in tacit notation that returns a vector of equilibrium indices. Spaces inserted for legibility only.

[: I. +/\. = +/\

To explain this, first observe its explicit definition; y is the formal parameter:

3 : 'I. (+/\. y) = (+/\ y)'
  • + adds its arguments. / is an adverb that inserts the verb left of it between the members of its right argument, e.g. +/ 1 2 3 4 is the same as 1 + 2 + 3 + 4.
  • \ is an adverb that applies the verb to its left to all prefixes prefixes of its right argument. For instance, with < drawing a box around its argument, <\ 1 2 3 4 produces

    ┌─┬───┬─────┬───────┐
    │1│1 2│1 2 3│1 2 3 4│
    └─┴───┴─────┴───────┘
    
  • Thus, +/\ computes for each prefix of its right argument the sum.

  • \. is like \ but operates on suffixes instead of prefixes. Thus, +/\. computes a vector of sums of suffixes.
  • = performs item-wise comparison of its arguments. For instance, 1 1 3 3 = 1 2 3 4 yields 1 0 1 0.
  • Thus, (+/\. y) = (+/\ y) yields one for all indices at which the suffix sum is equal to the prefix sum, or, an equilibrium is created.
  • For vectors of zeroes and ones, I. returns a vector of the indices at which the vector contains a one.
\$\endgroup\$
1
\$\begingroup\$

Python 2, 70

A=input()
e=i=s=0
for x in A:e=[e,~i][s*2==sum(A)-x];s+=x;i+=1
print~e

The idea is to track the running sum s and check whether it is half of the sum of array without the current element, and therefore equal to the sum of the array after the current element. If so, we update the equilibrium index to the current index. The last equilibrium index is printed, or the initial value -1 if there's none.

Actually, we store the bit-complement of the equilibrium index so that we can initialize it to 0 instead.

\$\endgroup\$
0
\$\begingroup\$

Python - 114

i=map(lambda x:int(x),raw_input().split(" "));x=0
print map(lambda x:(sum(i[0:x])==sum(i[x+1::])),range(0,len(i)))

Python - 72

i=input()
print map(lambda x:sum(i[0:x])==sum(i[x+1::]),range(0,len(i)))

Prints whether or not the given index is an equilibrium index, does not print the integer indecies at which the array is balanced.

\$\endgroup\$
  • \$\begingroup\$ What do you mean it breaks? 6 is an equilibrium index because the items before it sum to zero, there are no items after it, and 50 is ignored. \$\endgroup\$ – Joey Adams May 4 '11 at 2:40
  • \$\begingroup\$ AH. Thanks for the clarification joey, I didn't realize that the value at x was supposed to be ignored. \$\endgroup\$ – arrdem May 4 '11 at 3:09
0
\$\begingroup\$

PHP, 134 chars

<?for($a=explode(",",fgets(STDIN));++$i<($c=count($a));$o.=$s==0?$i:"")for($n=$s=0;$n<$c;)$s+=$n<$i?$a[$n++]:-$a[++$n];echo$o?$o:"-1";

I have an itch that this is far from optimal PHP golfing, but just ran out of steam (brains). At least it's shorter than with array_sum and array_splice :-)

\$\endgroup\$
0
\$\begingroup\$

PHP (81)

for($i=count($a)-1,$c=0;$i+1&&$c!=(array_sum($a)-$a[$i])/2;$c+=$a[$i--]);echo $i;

http://3v4l.org/qJvhO

Since no input was specified, this needs to be initialised with the array as the variable $a.

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