Equilibrium index

Equilibrium index
You are encouraged to solve this task according to the task description, using any language you may know.

An equilibrium index of a sequence is an index into the sequence such that the sum of elements at lower indices is equal to the sum of elements at higher indices. 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$.

Write a function that, given a sequence, returns its equilibrium indices (if any). Assume that the sequence may be very long.

Ada

Works with: Ada 2005

Generic solution that returns a Vector of Indices.

equilibrium.ads: <lang Ada>with Ada.Containers.Vectors;

generic

  type Index_Type is range <>;
  type Element_Type is private;
  Zero : Element_Type;
  with function "+" (Left, Right : Element_Type) return Element_Type is <>;
  with function "-" (Left, Right : Element_Type) return Element_Type is <>;
  with function "=" (Left, Right : Element_Type) return Boolean is <>;
  type Array_Type is private;
  with function Element (From : Array_Type; Key : Index_Type) return Element_Type is <>;

package Equilibrium is

  package Index_Vectors is new Ada.Containers.Vectors
     (Index_Type => Positive, Element_Type => Index_Type);

  function Get_Indices (From : Array_Type) return Index_Vectors.Vector;

end Equilibrium;</lang>

equilibrium.adb: <lang Ada>package body Equilibrium is

  function Get_Indices (From : Array_Type) return Index_Vectors.Vector is
     Result : Index_Vectors.Vector;
     Right_Sum, Left_Sum : Element_Type := Zero;
  begin
     for Index in Index_Type'Range loop
        Right_Sum := Right_Sum + Element (From, Index);
     end loop;
     for Index in Index_Type'Range loop
        Right_Sum := Right_Sum - Element (From, Index);
        if Left_Sum = Right_Sum then
           Index_Vectors.Append (Result, Index);
        end if;
        Left_Sum := Left_Sum + Element (From, Index);
     end loop;
     return Result;
  end Get_Indices;

end Equilibrium;</lang>

Test program using two different versions, one with vectors and one with arrays: <lang Ada>with Ada.Text_IO; with Equilibrium; with Ada.Containers.Vectors;

procedure Main is

  subtype Index_Type is Positive range 1 .. 7;
  package Vectors is new Ada.Containers.Vectors
     (Element_Type => Integer, Index_Type => Index_Type);
  type Plain_Array is array (Index_Type) of Integer;
  function Element (From : Plain_Array; Key : Index_Type) return Integer is
  begin
     return From (Key);
  end Element;

  package Vector_Equilibrium is new Equilibrium
     (Index_Type => Index_Type,
      Element_Type => Integer,
      Zero => 0,
      Array_Type => Vectors.Vector,
      Element => Vectors.Element);
  package Array_Equilibrium is new Equilibrium
     (Index_Type => Index_Type,
      Element_Type => Integer,
      Zero => 0,
      Array_Type => Plain_Array);

  My_Vector : Vectors.Vector;
  My_Array : Plain_Array := (-7, 1, 5, 2, -4, 3, 0);
  Vector_Result : Vector_Equilibrium.Index_Vectors.Vector;
  Array_Result : Array_Equilibrium.Index_Vectors.Vector :=
     Array_Equilibrium.Get_Indices (My_Array);

begin

  Vectors.Append (My_Vector, -7);
  Vectors.Append (My_Vector, 1);
  Vectors.Append (My_Vector, 5);
  Vectors.Append (My_Vector, 2);
  Vectors.Append (My_Vector, -4);
  Vectors.Append (My_Vector, 3);
  Vectors.Append (My_Vector, 0);
  Vector_Result := Vector_Equilibrium.Get_Indices (My_Vector);
  Ada.Text_IO.Put_Line ("Results:");
  Ada.Text_IO.Put ("Array: ");
  for I in Array_Result.First_Index .. Array_Result.Last_Index loop
     Ada.Text_IO.Put (Integer'Image (Array_Equilibrium.Index_Vectors.Element (Array_Result, I)));
  end loop;
  Ada.Text_IO.New_Line;
  Ada.Text_IO.Put ("Vector: ");
  for I in Vector_Result.First_Index .. Vector_Result.Last_Index loop
     Ada.Text_IO.Put (Integer'Image (Vector_Equilibrium.Index_Vectors.Element (Vector_Result, I)));
  end loop;
  Ada.Text_IO.New_Line;

end Main;</lang>

Output (Index_Type is based on 1):

Results:
Array:  4 7
Vector:  4 7

ALGOL 68

Translation of: C

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

<lang algol68>MODE YIELDINT = PROC(INT)VOID;

PROC gen equilibrium index = ([]INT arr, YIELDINT yield)VOID: (

   INT sum := 0;
   FOR i FROM LWB arr TO UPB arr DO
       sum +:= arr[i]
   OD;

   INT left:=0, right:=sum;
   FOR i FROM LWB arr TO UPB arr DO
       right -:= arr[i];
       IF left = right THEN yield(i) FI;
       left +:= arr[i]
   OD

);

test:(

 []INT arr = []INT(-7, 1, 5, 2, -4, 3, 0)[@0];

1. FOR INT index IN # gen equilibrium index(arr, # ) DO ( #
   1. (INT index)VOID:

    print(index)

1. OD # );

 print(new line)

)</lang> Output:

         +3         +6

C

<lang c>#include <stdio.h>

1. include <stdlib.h>

static int arr[] = {-7, 1, 5, 2, -4, 3, 0};

int main() {

   int i;
   int len = sizeof(arr) / sizeof(arr[0]);
   int sum = 0;
   int *res = NULL;
   int n = 0;
   int left, right;
   for (i = 0; i < len; i++)
   {
       sum += arr[i];
   }
   left = 0;
   right = sum;
   for (i = 0; i < len; i++)
   {
       right -= arr[i];
       if (left == right)
       {
           ++n;
           res = realloc(res, n * sizeof(int));
           res[n-1] = i;
       }
       left += arr[i];
   }
   printf("> Results:\n");
   for (i = 0; i < n; i++)
   {
       printf(" %d", res[i]);
   }
   printf("\n");
   return 0;

}</lang>

C#

<lang csharp>using System; using System.Collections.Generic; using System.Linq;

class Program {

   static IEnumerable<int> EquilibriumIndices(IEnumerable<int> sequence)
   {
       var left = 0;
       var right = sequence.Sum();
       var index = 0;
       foreach (var element in sequence)
       {
           right -= element;
           if (left == right)
           {
               yield return index;
           }
           left += element;
           index++;
       }
   }

   static void Main()
   {
       foreach (var index in EquilibriumIndices(new[] { -7, 1, 5, 2, -4, 3, 0 }))
       {
           Console.WriteLine(index);
       }
   }

}</lang> Output: <lang>3 6</lang>

Clojure

Translation of: Ocaml

<lang clojure> (defn equilibrium [lst]

 (loop [acc '(), i 0, left 0, right (apply + lst), lst lst]
    (if (empty? lst)

(reverse acc) (let [[x & xs] lst right (- right x) acc (if (= left right) (cons i acc) acc)] (recur acc (inc i) (+ left x) right xs))))) </lang>

> (equilibrium [-7, 1, 5, 2, -4, 3, 0])
(3 6)

D

Works with: D version 2.049

a bit functional style: <lang d>import std.stdio ; import std.algorithm ; import std.array ; import std.range ;

size_t[] eqIdx(T)(T[] s) {

   bool eqSplitSum(size_t i) {
       return reduce!"a + b"(0, s[0..i]) == reduce!"a + b"(0, s[i+1..s.length]) ;
   }
   return array(filter!eqSplitSum(iota(s.length))) ;

}

void main() {

   writefln("%s", eqIdx([-7, 1, 5, 2, -4, 3, 0])) ;

}</lang>

translated from PHP

<lang d>import std.algorithm ; size_t[] eqIdx(T)(T[] s) {

   size_t[] result ;
   T left = 0, right = reduce!"a + b"(0, s) ;

   foreach(i, e ; s) {
       right -= e ;
       if(right == left)
           result ~= i ;
       left += e ;
   }
   return result ;

}</lang>

Fortran

Works with: Fortran version 90 and later

Array indices are 1-based. <lang fortran>program Equilibrium

 implicit none
 
 integer :: array(7) = (/ -7, 1, 5, 2, -4, 3, 0 /)

 call equil_index(array)

contains

subroutine equil_index(a)

 integer, intent(in) :: a(:)
 integer :: i

 do i = 1, size(a)
   if(sum(a(1:i-1)) == sum(a(i+1:size(a)))) write(*,*) i
 end do

end subroutine end program</lang>

Haskell

<lang haskell>import Data.List import Control.Monad import Control.Arrow import System.Random

equilibr xs = elemIndices True. map (uncurry((.sum).(==). sum)).

 takeWhile(not.null.snd) $ map (flip (liftM2 (&&&) take (drop. pred)) xs) [1..]

langeSliert =

 replicateM 2000 (randomRIO (-15,15) :: IO Int)
  >>= print. equilibr</lang>

Small example <lang haskell>*Main> equilibr [-7, 1, 5, 2, -4, 3, 0] [3,6]</lang> Long random list in langeSliert (several tries for this one) <lang haskell>*Main> langeSliert [231,245,259,265,382,1480,1611,1612]</lang>

Icon and Unicon

<lang Icon>procedure main(arglist) L := if *arglist > 0 then arglist else [-7, 1, 5, 2, -4, 3, 0] # command line args or default every writes( "equilibrium indicies of [ " | (!L ||" ") | "] = " | (eqindex(L)||" ") | "\n" ) end

procedure eqindex(L) # generate equilibrium points in a list L or fail local s,l,i

every (s := 0, i := !L) do

  s +:= numeric(i) | fail              # sum and validate

every (l := 0, i := 1 to *L) do {

  if l = (s-L[i])/2 then suspend i     
  l +:= L[i]                           # sum of left side
  }

end</lang>

The Icon solution works in Unicon.

Sample Output:

equilibrium indicies of [ -7 1 5 2 -4 3 0 ] = 4 7

J

Solution <lang j>equilidx=: +/\ I.@:= +/\.</lang> Example <lang j> equilidx _7 1 5 2 _4 3 0 3 6</lang>

Java

<lang java>import java.util.Arrays; public class Equlibrium { private static int[] sequence = {-7, 1, 5, 2, -4, 3, 0}; public static void main(String[] args){ System.out.println("Equilibrium indices of " + Arrays.toString(sequence)+":"); for(int i = 0;i<sequence.length;i++){ int lSum = 0; int rSum = 0; for(int j = 0;j<sequence.length;j++){ if(j < i){ lSum += sequence[j]; } if(j > i){ rSum += sequence[j]; } } if(lSum == rSum){ System.out.println(i); } } } }</lang> Output:

Equilibrium indices of [-7, 1, 5, 2, -4, 3, 0]:
3
6

MATLAB

MATLAB arrays are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays. <lang MATLAB>function indicies = equilibriumIndex(list)

   indicies = [];

   for i = (1:numel(list))
       if ( sum(-list(1:i)) == sum(-list(i:end)) )
           indicies = [indicies i];
       end
   end

end</lang>

Output: <lang MATLAB>>> equilibriumIndex([-7 1 5 2 -4 3 0])

ans =

    4     7</lang>

OCaml

<lang ocaml>let lst = [ -7; 1; 5; 2; -4; 3; 0 ] let sum = List.fold_left ( + ) 0 lst

let () =

 let rec aux acc i left right = function
 | x::xs ->
     let right = right - x in
     let acc = if left = right then i::acc else acc in
     aux acc (succ i) (left + x) right xs
 | [] -> List.rev acc
 in
 let res = aux [] 0 0 sum lst in
 print_string "Results:";
 List.iter (Printf.printf " %d") res;
 print_newline()</lang>

PARI/GP

This uses 1-based vectors instead of 0-based arrays; subtract 1 from each index if you prefer the other style. <lang>equilib(v)={

 my(a=sum(i=2,#v,v[i]),b=0,u=[]);
 for(i=1,#v-1,
   if(a==b, u=concat(u,i));
   b+=v[i];
   a-=v[i+1]
 );
 if(b,u,concat(u,#v))

};</lang>

Perl

Translation of: Perl 6

<lang perl>sub eq_index {

   my ( $i, $sum, %sums ) = ( 0, 0 );

   for (@_) {
       push @{ $sums{ $sum * 2 + $_  } }, $i++;
       $sum += $_;
   }

   return join ' ', @{ $sums{$sum} || [] }, "\n";

}

print eq_index qw( -7 1 5 2 -4 3 0 ); # 3 6 print eq_index qw( 2 4 6 ); # (no eq point) print eq_index qw( 2 9 2 ); # 1 print eq_index qw( 1 -1 1 -1 1 -1 1 ); # 0 1 2 3 4 5 6</lang>

Perl 6

<lang perl6>sub equilibrium_index(@list) {

   my ($left,$right) = 0, [+] @list;

   gather for @list.kv -> $i, $x {
       $right -= $x;
       take $i if $left == $right;
       $left += $x;
   }

}

my @list = -7, 1, 5, 2, -4, 3, 0; .say for equilibrium_index(@list);</lang>

And here's an FP solution that manages to remain O(n):

<lang perl6>sub equilibrium_index(@list) {

   my @a := [\+] @list;
   my @b := reverse [\+] reverse @list;
   ^@list Zxx (@a »==« @b); 

}</lang> The [\+] is a reduction that returns a list of partial results. The »==« is a vectorized equality comparison; it returns a vector of true and false. The Zxx is a zip with the list replication operator, so we return only the elements of the left list where the right list is true (which is taken to mean 1 here). And the ^@list is just shorthand for 0 ..^ @list. We could just as easily have used @list.keys there.

Single-pass solution

The task can be restated in a way that removes the "right side" from the calculation.

C is the current element,
L is the sum of elements left of C,
R is the sum of elements right of C,
S is the sum of the entire list.

By definition, L + C + R == S for any choice of C, and L == R for any C that is an equilibrium point.
Therefore (by substituting L for R), L + C + L == S at all equilibrium points.
Restated, 2L + C == S.

<lang perl6>

1. Original example, with expanded calculations:

   0    1    2    3    4    5    6   # Index
  -7    1    5    2   -4    3    0   # C (Value at index)
   0   -7   -6   -1    1   -3    0   # L (Sum of left)
  -7  -13   -7    0   -2   -3    0   # 2L+C

</lang>

If we build a hash as we walk the list, with 2L+C as hash keys, and arrays of C-indexes as hash values, we get: <lang perl6> {

    -7 => [ 0, 2 ],
   -13 => [ 1    ],
     0 => [ 3, 6 ],
    -2 => [ 4    ],
    -3 => [ 5    ],

} </lang>

After we have finished walking the list, we will have the sum (S), which we look up in the hash. Here S=0, so the equilibrium points are 3 and 6.

Note: In the code below, it is more convenient to calculate 2L+C *after* L has already been incremented by C; the calculation is simply 2L-C, because each L has an extra C in it. 2(L-C)+C == 2L-C.

<lang perl6>sub eq_index ( *@list ) {

   my $sum = 0;

   my %h = @list.keys.classify: {
       $sum += @list[$_];
       $sum * 2 - @list[$_];
   };

   return %h{$sum} // [];

}

say eq_index < -7 1 5 2 -4 3 0 >; # 3 6 say eq_index < 2 4 6 >; # (no eq point) say eq_index < 2 9 2 >; # 1 say eq_index < 1 -1 1 -1 1 -1 1 >; # 0 1 2 3 4 5 6</lang>

The .classify method creates a hash, with its code block's return value as key. Each hash value is an Array of all the inputs that returned that key.

We could have used .pairs instead of .keys to save the cost of @list lookups, but that would change each %h value to an Array of Pairs, which would complicate the return line.

PHP

With foreach()

<lang php><?php $arr = array(-7, 1, 5, 2, -4, 3, 0);

function getEquilibriums($arr) {

   $right = array_sum($arr);
   $left = 0;
   $equilibriums = array();
   foreach($arr as $key => $value){
       $right -= $value;
       if($left == $right) $equilibriums[] = $key;
       $left += $value;
   }
   return $equilibriums;

}

echo "# results:\n"; foreach (getEquilibriums($arr) as $r) echo "$r, "; ?></lang>

With for()

<lang php><?php $arr = array(-7, 1, 5, 2, -4, 3, 0);

function getEquilibriums($arr) {

   $count = count($arr);
   $left = 0;
   $right = array_sum($arr);
   $equilibriums = array();
   for ($i = 0; $i < $count; $i++) {
       $right -= $arr[$i]; 
       if ($left == $right) $equilibriums[] = $i;
       $left += $arr[$i];
   }
   return $equilibriums;    

}

echo "# results:\n"; foreach (getEquilibriums($arr) as $r) echo "$r, "; ?></lang>

Output:

# results:
3, 6,

PicoLisp

<lang PicoLisp>(de equilibria (Lst)

  (make
     (let Sum 0
        (for ((I . L) Lst L (cdr L))
           (and (= Sum (sum prog (cdr L))) (link I))
           (inc 'Sum (car L)) ) ) ) )</lang>

Output:

: (equilibria (-7 1 5 2 -4 3 0))
-> (4 7)

: (equilibria (make (do 10000 (link (rand -10 10)))))
-> (4091 6174 6198 7104 7112 7754)

PureBasic

Translation of: Java

<lang PureBasic>If OpenConsole()

 Define i, c=CountProgramParameters()-1
 For i=0 To c
   Define j, LSum=0, RSum=0
   For j=0 To c
     If ji
       RSum+Val(ProgramParameter(j))
     EndIf
   Next j
   If LSum=RSum: PrintN(Str(i)): EndIf
 Next i

EndIf</lang>

> Equilibrium.exe -7 1 5 2 -4 3 0
3
6

Python

Two Pass

Uses an initial summation of the whole list then visits each item of the list adding it to the left-hand sum (after a delay); and subtracting the item from the right-hand sum. I think it should be quicker than algorithms that scan the list creating left and right sums for each index as it does ~2N add/subtractions rather than n*n. <lang python>def eqindex2Pass(data):

   "Two pass"
   suml, sumr, ddelayed = 0, sum(data), 0
   for i, d in enumerate(data):
       suml += ddelayed
       sumr -= d
       ddelayed = d
       if suml == sumr:
           yield i</lang>

Multi Pass

This is the version that does more summations, but may be faster for some sizes of input as the sum function is implemented in C internally: <lang python>def eqindexMultiPass(data):

   "Multi pass"
   for i in range(len(data)):
       suml, sumr = sum(data[:i]), sum(data[i+1:])
       if suml == sumr:
           yield i</lang>

One Pass

This routine would need careful evaluation against the two-pass solution above as, although it only runs through the data once, it may create a dict that is as long as the input data in its worst case of an input of say a simple 1, 2, 3, ... counting sequence. <lang python>from collections import defaultdict

def eqindex1Pass(data):

   "One pass"
   l, h = 0, defaultdict(list)
   for i, c in enumerate(data):
       l += c
       h[l * 2 - c].append(i)
   return h[l]</lang>

Tests

<lang python>f = (eqindex2Pass, eqindexMultiPass, eqindex1Pass) d = ([-7, 1, 5, 2, -4, 3, 0],

    [2, 4, 6],
    [2, 9, 2],
    [1, -1, 1, -1, 1, -1, 1])

for data in d:

   print("d = %r" % data)
   for func in f:
       print("  %16s(d) -> %r" % (func.__name__, list(func(data))))</lang>

Sample Output

d = [-7, 1, 5, 2, -4, 3, 0]
      eqindex2Pass(d) -> [3, 6]
  eqindexMultiPass(d) -> [3, 6]
      eqindex1Pass(d) -> [3, 6]
d = [2, 4, 6]
      eqindex2Pass(d) -> []
  eqindexMultiPass(d) -> []
      eqindex1Pass(d) -> []
d = [2, 9, 2]
      eqindex2Pass(d) -> [1]
  eqindexMultiPass(d) -> [1]
      eqindex1Pass(d) -> [1]
d = [1, -1, 1, -1, 1, -1, 1]
      eqindex2Pass(d) -> [0, 1, 2, 3, 4, 5, 6]
  eqindexMultiPass(d) -> [0, 1, 2, 3, 4, 5, 6]
      eqindex1Pass(d) -> [0, 1, 2, 3, 4, 5, 6]

Tcl

<lang tcl>proc listEquilibria {list} {

   set after 0
   foreach item $list {incr after $item}
   set result {}
   set idx 0
   set before 0
   foreach item $list {

incr after [expr {-$item}] if {$after == $before} { lappend result $idx } incr before $item incr idx

   }
   return $result

}</lang> Example of use: <lang tcl>set testData {-7 1 5 2 -4 3 0} puts Equilibria=[join [listEquilibria $testData] ", "]</lang> Example output:

Equilibria=3, 6

Ruby

List Processing Style <lang ruby>def eq_indicies *list

 len = list.size

 (0...len).select do |i|
   list[0, i].inject(0, &:+) == list[i + 1, len - i - 1].inject(0, &:+)
 end

end</lang>

Functional Style This one would be good if Ruby had a built-in linked list class and TCO: <lang ruby>def eq_indicies *list

 def eq_indicies_helper left, current, right, index, list
   if list == []
     left == 0 ? [index] : 0
   else
     (left == right ? [index] : []) +
       eq_indicies_helper(left + current, list.first, right - list.first, index + 1, list[1..-1])
   end
 end

 eq_indicies_helper 0, list.first, list.inject(&:+) - list.first, 0, list[1..-1]

end</lang>

Imperative Style (faster) <lang ruby>def eq_indicies *list

 left, right = 0, list.inject(0, &:+)
 equilibrium_indicies = []

 list.each_with_index do |val, i|
   right -= val

   equilibrium_indicies << i if right == left

   left += val
 end

 equilibrium_indicies

end</lang>

Output

eq_indicies -7, 1, 5, 2, -4, 3, 0  # => [3, 6]

Yorick

Yorick arrays are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays. <lang yorick>func equilibrium_indices(A) {

   return where(A(psum) == A(::-1)(psum)(::-1));

}</lang> Example interactive usage:

> equilibrium_indices([-7, 1, 5, 2, -4, 3, 0])
[4,7]