extra/rosetta-code/equilibrium-index/equilibrium-index.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math.statistics math.vectors sequences ;
   4 IN: rosetta-code.equilibrium-index
   5
   6 ! http://rosettacode.org/wiki/Equilibrium_index
   7
   8 ! An equilibrium index of a sequence is an index into the
   9 ! sequence such that the sum of elements at lower indices is
  10 ! equal to the sum of elements at higher indices. For example,
  11 ! in a sequence A:
  12 !   A0 = − 7
  13 !   A1 = 1
  14 !   A2 = 5
  15 !   A3 = 2
  16 !   A4 = − 4
  17 !   A5 = 3
  18 !   A6 = 0
  19
  20 ! 3 is an equilibrium index, because:
  21 !   A0 + A1 + A2 = A4 + A5 + A6
  22
  23 ! 6 is also an equilibrium index, because:
  24 !   A0 + A1 + A2 + A3 + A4 + A5 = 0
  25 !   (sum of zero elements is zero)
  26
  27 ! 7 is not an equilibrium index, because it is not a valid index
  28 ! of sequence A.
  29
  30 ! Write a function that, given a sequence, returns its
  31 ! equilibrium indices (if any). Assume that the sequence may be
  32 ! very long.
  33
  34 : equilibrium-indices ( seq -- indices )
  35     [ cum-sum0 ] [ <reversed> cum-sum0 <reversed> ] bi
  36     v= t swap indices ;