Equilibrium index: Difference between revisions
(→{{header|Ruby}}: use sum method) |
(Added Easylang) |
||
(42 intermediate revisions by 22 users not shown) | |||
Line 35: | Line 35: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F eqindex(arr) |
||
R (0 .< arr.len).filter(i -> sum(@arr[0.<i]) == sum(@arr[i+1..])) |
R (0 .< arr.len).filter(i -> sum(@arr[0.<i]) == sum(@arr[i+1..])) |
||
print(eqindex([-7, 1, 5, 2, -4, 3, 0]))</ |
print(eqindex([-7, 1, 5, 2, -4, 3, 0]))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 44: | Line 44: | ||
=={{header|ABAP}}== |
=={{header|ABAP}}== |
||
< |
<syntaxhighlight lang="abap">REPORT equilibrium_index. |
||
TYPES: y_i TYPE STANDARD TABLE OF i WITH EMPTY KEY. |
TYPES: y_i TYPE STANDARD TABLE OF i WITH EMPTY KEY. |
||
Line 57: | Line 57: | ||
LET z = sequences[ i ] IN |
LET z = sequences[ i ] IN |
||
NEXT x = COND #( WHEN y = ( total_sum - y - z ) THEN VALUE y_i( BASE x ( i - 1 ) ) ELSE x ) |
NEXT x = COND #( WHEN y = ( total_sum - y - z ) THEN VALUE y_i( BASE x ( i - 1 ) ) ELSE x ) |
||
y = y + z ) ).</ |
y = y + z ) ).</syntaxhighlight> |
||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size) |
|||
INT i |
|||
Put('[) |
|||
FOR i=0 TO size-1 |
|||
DO |
|||
IF i>0 THEN Put(' ) FI |
|||
PrintI(a(i)) |
|||
OD |
|||
Put(']) PutE() |
|||
RETURN |
|||
INT FUNC SumRange(INT ARRAY a INT first,last) |
|||
INT sum |
|||
INT i |
|||
sum=0 |
|||
FOR i=first TO last |
|||
DO |
|||
sum==+a(i) |
|||
OD |
|||
RETURN(sum) |
|||
PROC EquilibriumIndices(INT ARRAY a INT size |
|||
INT ARRAY indices INT POINTER indSize) |
|||
INT i,left,right |
|||
indSize^=0 |
|||
FOR i=0 TO size-1 |
|||
DO |
|||
left=SumRange(a,0,i-1) |
|||
right=SumRange(a,i+1,size-1) |
|||
IF left=right THEN |
|||
indices(indSize^)=i |
|||
indSize^==+1 |
|||
FI |
|||
OD |
|||
RETURN |
|||
PROC Test(INT ARRAY a INT size) |
|||
INT ARRAY indices(100) |
|||
INT indSize |
|||
EquilibriumIndices(a,size,indices,@indSize) |
|||
Print("Array=") PrintArray(a,size) |
|||
Print("Equilibrium indices=") PrintArray(indices,indSize) |
|||
PutE() |
|||
RETURN |
|||
PROC Main() |
|||
INT ARRAY a=[65529 1 5 2 65532 3 0] |
|||
INT ARRAY b=[65535 1 65535 1 65535 1 65535] |
|||
INT ARRAY c=[1 2 3 4 5 6 7 8 9] |
|||
INT ARRAY d=[0] |
|||
Test(a,7) |
|||
Test(b,7) |
|||
Test(c,9) |
|||
Test(d,1) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Equilibrium_index.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Array=[-7 1 5 2 -4 3 0] |
|||
Equilibrium indices=[3 6] |
|||
Array=[-1 1 -1 1 -1 1 -1] |
|||
Equilibrium indices=[0 1 2 3 4 5 6] |
|||
Array=[1 2 3 4 5 6 7 8 9] |
|||
Equilibrium indices=[] |
|||
Array=[0] |
|||
Equilibrium indices=[0] |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
Line 64: | Line 141: | ||
equilibrium.ads: |
equilibrium.ads: |
||
< |
<syntaxhighlight lang="ada">with Ada.Containers.Vectors; |
||
generic |
generic |
||
Line 81: | Line 158: | ||
function Get_Indices (From : Array_Type) return Index_Vectors.Vector; |
function Get_Indices (From : Array_Type) return Index_Vectors.Vector; |
||
end Equilibrium;</ |
end Equilibrium;</syntaxhighlight> |
||
equilibrium.adb: |
equilibrium.adb: |
||
< |
<syntaxhighlight lang="ada">package body Equilibrium is |
||
function Get_Indices (From : Array_Type) return Index_Vectors.Vector is |
function Get_Indices (From : Array_Type) return Index_Vectors.Vector is |
||
Line 102: | Line 179: | ||
end Get_Indices; |
end Get_Indices; |
||
end Equilibrium;</ |
end Equilibrium;</syntaxhighlight> |
||
Test program using two different versions, one with vectors and one with arrays: |
Test program using two different versions, one with vectors and one with arrays: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
with Equilibrium; |
with Equilibrium; |
||
with Ada.Containers.Vectors; |
with Ada.Containers.Vectors; |
||
Line 155: | Line 232: | ||
end loop; |
end loop; |
||
Ada.Text_IO.New_Line; |
Ada.Text_IO.New_Line; |
||
end Main;</ |
end Main;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
(Index_Type is based on 1): |
(Index_Type is based on 1): |
||
Line 166: | Line 243: | ||
{{works with|Ada 2005}} |
{{works with|Ada 2005}} |
||
equilibrium.adb: |
equilibrium.adb: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
procedure Equilibrium is |
procedure Equilibrium is |
||
Line 233: | Line 310: | ||
Ada.Text_IO.Put_Line ("X4:" & Seq_Img (X4)); |
Ada.Text_IO.Put_Line ("X4:" & Seq_Img (X4)); |
||
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X4_Result)); |
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X4_Result)); |
||
end Equilibrium;</ |
end Equilibrium;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Results: |
<pre>Results: |
||
Line 250: | Line 327: | ||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
< |
<syntaxhighlight lang="aime">list |
||
eqindex(list l) |
eqindex(list l) |
||
{ |
{ |
||
Line 274: | Line 351: | ||
0; |
0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 281: | Line 358: | ||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} |
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} |
||
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}} |
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}} |
||
< |
<syntaxhighlight lang="algol68">MODE YIELDINT = PROC(INT)VOID; |
||
PROC gen equilibrium index = ([]INT arr, YIELDINT yield)VOID: |
PROC gen equilibrium index = ([]INT arr, YIELDINT yield)VOID: |
||
Line 305: | Line 382: | ||
# OD # ); |
# OD # ); |
||
print(new line) |
print(new line) |
||
)</ |
)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 312: | Line 389: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
===Functional=== |
|||
{{Trans|JavaScript}}(ES6 version) |
{{Trans|JavaScript}}(ES6 version) |
||
< |
<syntaxhighlight lang="applescript">-- equilibriumIndices :: [Int] -> [Int] |
||
on equilibriumIndices(xs) |
on equilibriumIndices(xs) |
||
Line 490: | Line 568: | ||
end repeat |
end repeat |
||
return lst |
return lst |
||
end zip</ |
end zip</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>{{3, 6}, {}, {1}, {0, 1, 2, 3, 4, 5, 6}, {0}, {}}</pre> |
<pre>{{3, 6}, {}, {1}, {0, 1, 2, 3, 4, 5, 6}, {0}, {}}</pre> |
||
---- |
|||
===Straightforward=== |
|||
<syntaxhighlight lang="applescript">on equilibriumIndices(sequence) |
|||
script o |
|||
property seq : sequence |
|||
property output : {} |
|||
end script |
|||
set loSum to 0 |
|||
set hiSum to 0 |
|||
repeat with value in o's seq |
|||
set hiSum to hiSum + value |
|||
end repeat |
|||
repeat with i from 1 to (count o's seq) |
|||
set value to o's seq's item i |
|||
set hiSum to hiSum - value |
|||
if (hiSum = loSum) then set o's output's end to i |
|||
set loSum to loSum + value |
|||
end repeat |
|||
return o's output |
|||
end equilibriumIndices |
|||
equilibriumIndices({-7, 1, 5, 2, -4, 3, 0})</syntaxhighlight> |
|||
{{output}} |
|||
AppleScript uses 1-based indices. |
|||
<syntaxhighlight lang="applescript">{4, 7}</syntaxhighlight> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">eqIndex: function [row][ |
|||
suml: 0 |
|||
delayed: 0 |
|||
sumr: sum row |
|||
result: new [] |
|||
loop.with:'i row 'r [ |
|||
suml: suml + delayed |
|||
sumr: sumr - r |
|||
delayed: r |
|||
if suml = sumr -> 'result ++ i |
|||
] |
|||
return result |
|||
] |
|||
data: @[ |
|||
@[neg 7, 1, 5, 2, neg 4, 3, 0] |
|||
@[2 4 6] |
|||
@[2 9 2] |
|||
@[1 neg 1 1 neg 1 1 neg 1 1] |
|||
] |
|||
loop data 'd -> |
|||
print [pad.right join.with:", " to [:string] d 25 "=> equilibrium index:" eqIndex d]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>-7, 1, 5, 2, -4, 3, 0 => equilibrium index: [3 6] |
|||
2, 4, 6 => equilibrium index: [] |
|||
2, 9, 2 => equilibrium index: [1] |
|||
1, -1, 1, -1, 1, -1, 1 => equilibrium index: [0 1 2 3 4 5 6]</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">Equilibrium_index(list, BaseIndex=0){ |
||
StringSplit, A, list, `, |
StringSplit, A, list, `, |
||
Loop % A0 { |
Loop % A0 { |
||
Line 508: | Line 647: | ||
} |
} |
||
return Res |
return Res |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">list = -7, 1, 5, 2, -4, 3, 0 |
||
MsgBox % Equilibrium_index(list)</ |
MsgBox % Equilibrium_index(list)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3, 6</pre> |
<pre>3, 6</pre> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f EQUILIBRIUM_INDEX.AWK |
# syntax: GAWK -f EQUILIBRIUM_INDEX.AWK |
||
BEGIN { |
BEGIN { |
||
Line 543: | Line 682: | ||
return(str) |
return(str) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<p>Output:</p> |
<p>Output:</p> |
||
<pre> |
<pre> |
||
Line 558: | Line 697: | ||
indices: 1 2 3 4 5 6 7 |
indices: 1 2 3 4 5 6 7 |
||
</pre> |
</pre> |
||
=={{header|BASIC}}== |
|||
==={{header|BASIC256}}=== |
|||
{{trans|Ring}} |
|||
<syntaxhighlight lang="vb">arraybase 1 |
|||
dim list = {-7, 1, 5, 2, -4, 3, 0} |
|||
print "equilibrium indices are : "; equilibrium(list) |
|||
end |
|||
function equilibrium (l) |
|||
r = 0: s = 0 |
|||
e$ = "" |
|||
for n = 1 to l[?] |
|||
s += l[n] |
|||
next |
|||
for i = 1 to l[?] |
|||
if r = s - r - l[i] then e$ += string(i-1) + " " |
|||
r += l[i] |
|||
next |
|||
e$ = left(e$, length(e$)-1) |
|||
return e$ |
|||
end function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>The equilibrium indices are : 3 6</pre> |
|||
=={{header|Batch File}}== |
=={{header|Batch File}}== |
||
< |
<syntaxhighlight lang="dos">@echo off |
||
setlocal enabledelayedexpansion |
setlocal enabledelayedexpansion |
||
Line 601: | Line 765: | ||
echo [!equilms!] |
echo [!equilms!] |
||
goto :EOF |
goto :EOF |
||
%==/The Function ==%</ |
%==/The Function ==%</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[3 6] |
<pre>[3 6] |
||
Line 610: | Line 774: | ||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
BBC BASIC's '''SUM''' function is useful for this task. |
BBC BASIC's '''SUM''' function is useful for this task. |
||
< |
<syntaxhighlight lang="bbcbasic"> DIM list(6) |
||
list() = -7, 1, 5, 2, -4, 3, 0 |
list() = -7, 1, 5, 2, -4, 3, 0 |
||
PRINT "Equilibrium indices are " FNequilibrium(list()) |
PRINT "Equilibrium indices are " FNequilibrium(list()) |
||
Line 622: | Line 786: | ||
r += l(i%) |
r += l(i%) |
||
NEXT |
NEXT |
||
= LEFT$(e$)</ |
= LEFT$(e$)</syntaxhighlight> |
||
'''Output:''' |
'''Output:''' |
||
<pre> |
<pre> |
||
Line 629: | Line 793: | ||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 672: | Line 836: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 705: | Line 869: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<lang>3 |
<syntaxhighlight lang="text">3 |
||
6</ |
6</syntaxhighlight> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iostream> |
#include <iostream> |
||
#include <numeric> |
#include <numeric> |
||
Line 750: | Line 914: | ||
std::for_each(indices.begin(), indices.end(), print<size_t>); |
std::for_each(indices.begin(), indices.end(), print<size_t>); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 759: | Line 923: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
{{trans|Ocaml}} |
{{trans|Ocaml}} |
||
< |
<syntaxhighlight lang="clojure">(defn equilibrium [lst] |
||
(loop [acc '(), i 0, left 0, right (apply + lst), lst lst] |
(loop [acc '(), i 0, left 0, right (apply + lst), lst lst] |
||
(if (empty? lst) |
(if (empty? lst) |
||
Line 766: | Line 930: | ||
right (- right x) |
right (- right x) |
||
acc (if (= left right) (cons i acc) acc)] |
acc (if (= left right) (cons i acc) acc)] |
||
(recur acc (inc i) (+ left x) right xs)))))</ |
(recur acc (inc i) (+ left x) right xs)))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 774: | Line 938: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun dflt-on-nil (v dflt) |
||
(if v v dflt)) |
(if v v dflt)) |
||
Line 788: | Line 952: | ||
(if (eql lsum rsum) (push i stack)) |
(if (eql lsum rsum) (push i stack)) |
||
(setf lsum (+ lsum (car rest))) |
(setf lsum (+ lsum (car rest))) |
||
(setf rsum (- rsum (dflt-on-nil (cadr rest) 0)))))</ |
(setf rsum (- rsum (dflt-on-nil (cadr rest) 0)))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<lang>(eq-index '(-7 1 5 2 -4 3 0)) |
<syntaxhighlight lang="text">(eq-index '(-7 1 5 2 -4 3 0)) |
||
(3 6)</ |
(3 6)</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
===More Functional Style=== |
===More Functional Style=== |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.functional; |
||
auto equilibrium(Range)(Range r) pure nothrow @safe /*@nogc*/ { |
auto equilibrium(Range)(Range r) pure nothrow @safe /*@nogc*/ { |
||
Line 803: | Line 967: | ||
void main() { |
void main() { |
||
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln; |
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[3, 6]</pre> |
<pre>[3, 6]</pre> |
||
Line 810: | Line 974: | ||
{{trans|PHP}} |
{{trans|PHP}} |
||
Same output. |
Same output. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm; |
||
size_t[] equilibrium(T)(in T[] items) @safe pure nothrow { |
size_t[] equilibrium(T)(in T[] items) @safe pure nothrow { |
||
Line 827: | Line 991: | ||
void main() { |
void main() { |
||
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln; |
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Delphi}}== |
|||
See [https://rosettacode.org/wiki/Equilibrium_index#Pascal Pascal]. |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
func[] equind a[] . |
|||
for v in a[] |
|||
sumr += v |
|||
. |
|||
for i to len a[] |
|||
sumr -= a[i] |
|||
if suml = sumr |
|||
r[] &= i |
|||
. |
|||
suml += a[i] |
|||
. |
|||
return r[] |
|||
. |
|||
print equind [ -7 1 5 2 -4 3 0 ] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 4 7 ] |
|||
</pre> |
|||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
ELENA |
ELENA 6.x : |
||
< |
<syntaxhighlight lang="elena">import extensions; |
||
import system'routines; |
import system'routines; |
||
import system'collections; |
import system'collections; |
||
Line 862: | Line 1,050: | ||
while(en.next()) |
while(en.next()) |
||
{ |
{ |
||
var element := en |
var element := *en; |
||
right -= element; |
right -= element; |
||
bool found := (left == right); |
bool found := (left == right); |
||
Line 889: | Line 1,077: | ||
} |
} |
||
get() = index; |
get Value() = index; |
||
enumerable() => en; |
enumerable() => en; |
||
Line 897: | Line 1,085: | ||
{ |
{ |
||
EquilibriumEnumerator.new(new int[]{ -7, 1, 5, 2, -4, 3, 0 }) |
EquilibriumEnumerator.new(new int[]{ -7, 1, 5, 2, -4, 3, 0 }) |
||
.forEach |
.forEach(printingLn) |
||
}</ |
}</syntaxhighlight> |
||
<pre> |
<pre> |
||
3 |
3 |
||
Line 907: | Line 1,095: | ||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
computes either side each time. |
computes either side each time. |
||
< |
<syntaxhighlight lang="elixir">defmodule Equilibrium do |
||
def index(list) do |
def index(list) do |
||
last = length(list) |
last = length(list) |
||
Line 914: | Line 1,102: | ||
end) |
end) |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
faster version: |
faster version: |
||
< |
<syntaxhighlight lang="elixir">defmodule Equilibrium do |
||
def index(list), do: index(list,0,0,Enum.sum(list),[]) |
def index(list), do: index(list,0,0,Enum.sum(list),[]) |
||
Line 923: | Line 1,111: | ||
defp index([h|t],i,left,right,acc) when left==right-h, do: index(t,i+1,left+h,right-h,[i|acc]) |
defp index([h|t],i,left,right,acc) when left==right-h, do: index(t,i+1,left+h,right-h,[i|acc]) |
||
defp index([h|t],i,left,right,acc) , do: index(t,i+1,left+h,right-h,acc) |
defp index([h|t],i,left,right,acc) , do: index(t,i+1,left+h,right-h,acc) |
||
end</ |
end</syntaxhighlight> |
||
'''Test:''' |
'''Test:''' |
||
< |
<syntaxhighlight lang="elixir">indices = [ |
||
[-7, 1, 5, 2,-4, 3, 0], |
[-7, 1, 5, 2,-4, 3, 0], |
||
[2, 4, 6], |
[2, 4, 6], |
||
Line 934: | Line 1,122: | ||
Enum.each(indices, fn list -> |
Enum.each(indices, fn list -> |
||
IO.puts "#{inspect list} => #{inspect Equilibrium.index(list)}" |
IO.puts "#{inspect list} => #{inspect Equilibrium.index(list)}" |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 945: | Line 1,133: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
<syntaxhighlight lang="erre"> |
|||
<lang ERRE> |
|||
PROGRAM EQUILIBRIUM |
PROGRAM EQUILIBRIUM |
||
Line 967: | Line 1,155: | ||
PRINT("Equilibrium indices are";RES$) |
PRINT("Equilibrium indices are";RES$) |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Output:''' |
'''Output:''' |
||
<pre> |
<pre> |
||
Line 974: | Line 1,162: | ||
=={{header|Euphoria}}== |
=={{header|Euphoria}}== |
||
< |
<syntaxhighlight lang="euphoria">function equilibrium(sequence s) |
||
integer lower_sum, higher_sum |
integer lower_sum, higher_sum |
||
sequence indices |
sequence indices |
||
Line 993: | Line 1,181: | ||
end function |
end function |
||
? equilibrium({-7,1,5,2,-4,3,0})</ |
? equilibrium({-7,1,5,2,-4,3,0})</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
''(Remember that indices are 1-based in Euphoria)'' |
''(Remember that indices are 1-based in Euphoria)'' |
||
Line 1,000: | Line 1,188: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
Executed in the listener. Note that <code>accum-left</code> and <code>accum-right</code> have different outputs than <code>accumulate</code> as they drop the final result. |
Executed in the listener. Note that <code>accum-left</code> and <code>accum-right</code> have different outputs than <code>accumulate</code> as they drop the final result. |
||
< |
<syntaxhighlight lang="factor">USE: math.vectors |
||
: accum-left ( seq id quot -- seq ) accumulate nip ; inline |
: accum-left ( seq id quot -- seq ) accumulate nip ; inline |
||
: accum-right ( seq id quot -- seq ) [ <reversed> ] 2dip accum-left <reversed> ; inline |
: accum-right ( seq id quot -- seq ) [ <reversed> ] 2dip accum-left <reversed> ; inline |
||
: equilibrium-indices ( seq -- inds ) |
: equilibrium-indices ( seq -- inds ) |
||
0 [ + ] [ accum-left ] [ accum-right ] 3bi [ = ] 2map |
0 [ + ] [ accum-left ] [ accum-right ] 3bi [ = ] 2map |
||
V{ } swap dup length iota [ [ suffix ] curry [ ] if ] 2each ;</ |
V{ } swap dup length iota [ [ suffix ] curry [ ] if ] 2each ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="factor">( scratchpad ) { -7 1 5 2 -4 3 0 } equilibrium-indices . |
||
V{ 3 6 }</ |
V{ 3 6 }</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
Array indices are 1-based. |
Array indices are 1-based. |
||
< |
<syntaxhighlight lang="fortran">program Equilibrium |
||
implicit none |
implicit none |
||
Line 1,031: | Line 1,219: | ||
end subroutine |
end subroutine |
||
end program</ |
end program</syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
Sub equilibriumIndices (a() As Integer, b() As Integer) |
Sub equilibriumIndices (a() As Integer, b() As Integer) |
||
Line 1,069: | Line 1,257: | ||
Print |
Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,079: | Line 1,267: | ||
=={{header|Fōrmulæ}}== |
=={{header|Fōrmulæ}}== |
||
{{FormulaeEntry|page=https://formulae.org/?script=examples/Equilibrium_index}} |
|||
'''Solution''' |
|||
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition. |
|||
[[File:Fōrmulæ - Equilibrium index 01.png]] |
|||
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code. |
|||
In Fōrmulæ, indices are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays. |
|||
'''Test cases''' |
|||
[[File:Fōrmulæ - Equilibrium index 02.png]] |
|||
[[File:Fōrmulæ - Equilibrium index 03.png]] |
|||
[[File:Fōrmulæ - Equilibrium index 04.png]] |
|||
[[File:Fōrmulæ - Equilibrium index 05.png]] |
|||
[[File:Fōrmulæ - Equilibrium index 06.png]] |
|||
[[File:Fōrmulæ - Equilibrium index 07.png]] |
|||
[[File:Fōrmulæ - Equilibrium index 08.png]] |
|||
[[File:Fōrmulæ - Equilibrium index 09.png]] |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,121: | Line 1,329: | ||
} |
} |
||
return |
return |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,129: | Line 1,337: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import System.Random (randomRIO) |
||
import Data.List ( |
import Data.List (findIndices, takeWhile) |
||
import Control.Monad (replicateM) |
import Control.Monad (replicateM) |
||
import Control.Arrow ((&&&)) |
import Control.Arrow ((&&&)) |
||
equilibr xs = |
equilibr xs = |
||
findIndices (\(a, b) -> sum a == sum b) . takeWhile (not . null . snd) $ |
|||
elemIndices True . |
|||
map (\(a, b) -> sum a == sum b) . takeWhile (not . null . snd) $ |
|||
flip ((&&&) <$> take <*> (drop . pred)) xs <$> [1 ..] |
flip ((&&&) <$> take <*> (drop . pred)) xs <$> [1 ..] |
||
langeSliert = replicateM 2000 (randomRIO (-15, 15) :: IO Int) >>= print . equilibr</ |
langeSliert = replicateM 2000 (randomRIO (-15, 15) :: IO Int) >>= print . equilibr</syntaxhighlight> |
||
Small example |
Small example |
||
< |
<syntaxhighlight lang="haskell">*Main> equilibr [-7, 1, 5, 2, -4, 3, 0] |
||
[3,6]</ |
[3,6]</syntaxhighlight> |
||
Long random list in langeSliert (several tries for this one) |
Long random list in langeSliert (several tries for this one) |
||
< |
<syntaxhighlight lang="haskell">*Main> langeSliert |
||
[231,245,259,265,382,1480,1611,1612]</ |
[231,245,259,265,382,1480,1611,1612]</syntaxhighlight> |
||
Or, using default Prelude functions: |
Or, using default Prelude functions: |
||
< |
<syntaxhighlight lang="haskell">equilibriumIndices :: [Int] -> [Int] |
||
equilibriumIndices xs = |
equilibriumIndices xs = |
||
zip3 |
|||
let matchIndex (x, y, i) a |
|||
(scanl1 (+) xs) -- Sums from the left |
|||
(scanr1 (+) xs) -- Sums from the right |
|||
[0 ..] -- Indices |
|||
in foldr |
|||
>>= (\(x, y, i) -> [i | x == y]) |
|||
matchIndex |
|||
[] |
|||
(zip3 |
|||
(scanl1 (+) xs) -- Sums from the left |
|||
(scanr1 (+) xs) -- Sums from the right |
|||
[0 ..] -- Indices |
|||
) |
|||
---------------------------TEST |
--------------------------- TEST ------------------------- |
||
main :: IO () |
main :: IO () |
||
main = |
main = |
||
mapM_ |
mapM_ |
||
print |
print |
||
$ equilibriumIndices |
|||
(equilibriumIndices <$> |
|||
[ [-7, 1, 5, 2, -4, 3, 0] |
<$> [ [-7, 1, 5, 2, -4, 3, 0], |
||
[2, 4, 6], |
|||
[2, 9, 2], |
|||
[1, -1, 1, -1, 1, -1, 1], |
|||
[1], |
|||
[] |
|||
] |
]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[3,6] |
<pre>[3,6] |
||
Line 1,186: | Line 1,387: | ||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
< |
<syntaxhighlight lang="icon">procedure main(arglist) |
||
L := if *arglist > 0 then arglist else [-7, 1, 5, 2, -4, 3, 0] # command line args or default |
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" ) |
every writes( "equilibrium indicies of [ " | (!L ||" ") | "] = " | (eqindex(L)||" ") | "\n" ) |
||
Line 1,201: | Line 1,402: | ||
l +:= L[i] # sum of left side |
l +:= L[i] # sum of left side |
||
} |
} |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>equilibrium indicies of [ -7 1 5 2 -4 3 0 ] = 4 7</pre> |
<pre>equilibrium indicies of [ -7 1 5 2 -4 3 0 ] = 4 7</pre> |
||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j">equilidx=: +/\ I.@:= +/\.</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
< |
<syntaxhighlight lang="j"> equilidx _7 1 5 2 _4 3 0 |
||
3 6</ |
3 6</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
< |
<syntaxhighlight lang="java5"> |
||
public class Equlibrium { |
public class Equlibrium { |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
Line 1,237: | Line 1,438: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,247: | Line 1,448: | ||
===ES5=== |
===ES5=== |
||
< |
<syntaxhighlight lang="javascript">function equilibrium(a) { |
||
var N = a.length, i, l = [], r = [], e = [] |
var N = a.length, i, l = [], r = [], e = [] |
||
for (l[0] = a[0], r[N - 1] = a[N - 1], i = 1; i<N; i++) |
for (l[0] = a[0], r[N - 1] = a[N - 1], i = 1; i<N; i++) |
||
Line 1,265: | Line 1,466: | ||
].forEach(function(x) { |
].forEach(function(x) { |
||
console.log(equilibrium(x)) |
console.log(equilibrium(x)) |
||
});</ |
});</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">[[3,6],[],[1],[0,1,2,3,4,5,6],[0],[]]</syntaxhighlight> |
||
===ES6 Procedural=== |
===ES6 Procedural=== |
||
Two pass O(n), returning only the first equilibrium index. |
Two pass O(n), returning only the first equilibrium index. |
||
< |
<syntaxhighlight lang="javascript">function equilibrium(arr) { |
||
let sum = arr.reduce((a, b) => a + b); |
let sum = arr.reduce((a, b) => a + b); |
||
let leftSum = 0; |
let leftSum = 0; |
||
Line 1,287: | Line 1,488: | ||
return -1; |
return -1; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">3, -1, 1, 0, 0</syntaxhighlight> |
||
===ES6 Functional=== |
===ES6 Functional=== |
||
A composition of pure generic functions, returning all equilibrium indices. |
A composition of pure generic functions, returning '''all''' equilibrium indices. |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
"use strict"; |
|||
// ------------- ALL EQUILIBRIUM INDICES ------------- |
|||
// equilibriumIndices :: [Int] -> [Int] |
// equilibriumIndices :: [Int] -> [Int] |
||
const equilibriumIndices = xs => |
const equilibriumIndices = xs => |
||
zip |
zip( |
||
scanl1(add)(xs) |
|||
)( |
|||
scanr1(add)(xs) |
scanr1(add)(xs) |
||
) |
) |
||
.reduceRight( |
|||
(a, xy, i) => xy[0] === xy[1] ? ( |
|||
[i, ...a] |
[i, ...a] |
||
) : a, [] |
) : a, [] |
||
); |
|||
// ------------------------TEST------------------------ |
|||
// ---------------------- TEST ----------------------- |
|||
const main = () => { |
|||
const main = () => [ |
|||
console.log(JSON.stringify([ |
|||
[-7, 1, 5, 2, -4, 3, 0], |
[-7, 1, 5, 2, -4, 3, 0], |
||
[2, 4, 6], |
[2, 4, 6], |
||
Line 1,316: | Line 1,523: | ||
[1], |
[1], |
||
[] |
[] |
||
].map( |
].map(compose( |
||
JSON.stringify, |
|||
// -> [[3, 6], [], [1], [0, 1, 2, 3, 4, 5, 6], [0], []] |
|||
equilibriumIndices |
|||
}; |
|||
)) |
|||
.join("\n"); |
|||
// -> [[3, 6], [], [1], [0, 1, 2, 3, 4, 5, 6], [0], []] |
|||
// ---------------- |
// ---------------- GENERIC FUNCTIONS ---------------- |
||
// Tuple (,) :: a -> b -> (a, b) |
|||
const Tuple = a => |
|||
b => ({ |
|||
type: 'Tuple', |
|||
'0': a, |
|||
'1': b, |
|||
length: 2 |
|||
}); |
|||
// add (+) :: Num a => a -> a -> a |
// add (+) :: Num a => a -> a -> a |
||
Line 1,336: | Line 1,537: | ||
// Curried addition. |
// Curried addition. |
||
b => a + b; |
b => a + b; |
||
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c |
|||
const compose = (...fs) => |
|||
// A function defined by the right-to-left |
|||
// composition of all the functions in fs. |
|||
fs.reduce( |
|||
(f, g) => x => f(g(x)), |
|||
x => x |
|||
); |
|||
// scanl :: (b -> a -> b) -> b -> [a] -> [b] |
// scanl :: (b -> a -> b) -> b -> [a] -> [b] |
||
const scanl = f => |
const scanl = f => startValue => xs => |
||
// |
// The series of interim values arising |
||
// |
// from a catamorphism. Parallel to foldl. |
||
xs.reduce((a, x) => { |
|||
v => xs => xs.reduce((a, x) => { |
|||
const v = f(a[0])(x); |
const v = f(a[0])(x); |
||
return Tuple(v)(a[1].concat(v)); |
|||
}, Tuple(v)([v]))[1]; |
|||
return [v, a[1].concat(v)]; |
|||
}, [startValue, [startValue]])[1]; |
|||
const scanr = f => |
|||
// scanr is like foldr or reduceRight, but |
|||
// returns a succession of intermediate |
|||
// values, building from the right. |
|||
v => xs => xs.reduceRight((a, x) => { |
|||
const v = f(x)(a[0]); |
|||
return Tuple(v)([v].concat(a[1])); |
|||
}, Tuple(v)([v]))[1]; |
|||
// scanl1 :: (a -> a -> a) -> [a] -> [a] |
// scanl1 :: (a -> a -> a) -> [a] -> [a] |
||
const scanl1 = f => |
const scanl1 = f => |
||
// scanl1 is a variant of scanl that has no |
// scanl1 is a variant of scanl that has no |
||
// |
// starting value argument. |
||
// xs is not empty. |
|||
xs => xs.length > 0 ? ( |
xs => xs.length > 0 ? ( |
||
scanl(f)( |
scanl(f)( |
||
Line 1,367: | Line 1,569: | ||
)(xs.slice(1)) |
)(xs.slice(1)) |
||
) : []; |
) : []; |
||
// scanr :: (a -> b -> b) -> b -> [a] -> [b] |
|||
const scanr = f => |
|||
startValue => xs => xs.reduceRight( |
|||
(a, x) => { |
|||
const v = f(x)(a[0]); |
|||
return [v, [v].concat(a[1])]; |
|||
}, [startValue, [startValue]] |
|||
)[1]; |
|||
// scanr1 :: (a -> a -> a) -> [a] -> [a] |
// scanr1 :: (a -> a -> a) -> [a] -> [a] |
||
Line 1,378: | Line 1,592: | ||
)(xs.slice(0, -1)) |
)(xs.slice(0, -1)) |
||
) : []; |
) : []; |
||
// zip :: [a] -> [b] -> [(a, b)] |
// zip :: [a] -> [b] -> [(a, b)] |
||
const zip = xs => |
const zip = xs => |
||
// The paired members of xs and ys, up to |
|||
// the length of the shorter of the two lists. |
|||
ys => Array.from({ |
ys => Array.from({ |
||
length: Math.min(xs.length, ys.length) |
length: Math.min(xs.length, ys.length) |
||
}, (_, i) => |
}, (_, i) => [xs[i], ys[i]]); |
||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre>[3,6] |
||
[] |
|||
[1] |
|||
[0,1,2,3,4,5,6] |
|||
[0] |
|||
[]</pre> |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
{{works with | jq}} |
|||
The following implementation will work with jq 1.4 but for input |
|||
''Also works with gojq, the Go implementation of jq, and jaq'' |
|||
arrays larger than 1e4 in length, a version of jq with tail-call |
|||
optimization (TCO) should probably be used. |
|||
`equilibrium_indices` is defined as a 0-arity filter that emits answers as a stream, as is idiomatic in jq. |
|||
Since the task description indicates that the array might be very long: |
|||
* the implementation uses a 0-arity inner function to do the heavy lifting; |
|||
* the algorithm walks along the array so as to minimize both memory requirements and the number of arithmetic operations; |
|||
* the answers are emitted as a stream. |
|||
<syntaxhighlight lang="jq"># The index origin is 0 in jq. |
|||
The top-level function is defined as a 0-arity filter that emits answers as a stream, as is idiomatic in jq. |
|||
<lang jq># The index origin is 0 in jq. |
|||
def equilibrium_indices: |
def equilibrium_indices: |
||
. as $in |
|||
def indices(a; mx): |
|||
| add as $add |
|||
def report: # [i, headsum, tailsum] |
|||
| foreach range(0;length) as $i ( |
|||
[0, 0, $add]; # [before, pivot, after] |
|||
$in[$i] as $x | [.[0]+.[1], $x, .[2] - $x]; |
|||
if .[0] == .[2] then $i else empty end) ; |
|||
</syntaxhighlight> |
|||
| (if $h == $t then $i else empty end), |
|||
( [ $i + 1, $h + a[$i], $t ] | report ) |
|||
end; |
|||
[0, 0, (a|add)] | report; |
|||
. as $in | indices($in; $in|length);</lang> |
|||
'''Example 1:''' |
'''Example 1:''' |
||
< |
<syntaxhighlight lang="jq">[-7, 1, 5, 2, -4, 3, 0] | equilibrium_indices</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
$ jq -M -n -f equilibrium_indices.jq |
$ jq -M -n -f equilibrium_indices.jq |
||
Line 1,422: | Line 1,636: | ||
6 |
6 |
||
'''Example 2:''' |
'''Example 2:''' |
||
< |
<syntaxhighlight lang="jq">def count(g): reduce g as $i (0; .+1); |
||
# Create an array of length n with "init" elements: |
# Create an array of length n with "init" elements: |
||
def array(n;init): reduce range(0;n) as $i ([]; . + [0]); |
def array(n;init): reduce range(0;n) as $i ([]; . + [0]); |
||
count( array( |
count( array(10000;0) | equilibrium_indices )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
$ jq -M -n -f equilibrium_indices.jq |
$ jq -M -n -f equilibrium_indices.jq |
||
Line 1,435: | Line 1,649: | ||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">function equindex2pass(data::Array) |
||
rst = Vector{Int}(0) |
rst = Vector{Int}(0) |
||
suml, sumr, ddelayed = 0, sum(data), 0 |
suml, sumr, ddelayed = 0, sum(data), 0 |
||
Line 1,451: | Line 1,665: | ||
@show equindex2pass([1, -1, 1, -1, 1, -1, 1]) |
@show equindex2pass([1, -1, 1, -1, 1, -1, 1]) |
||
@show equindex2pass([1, 2, 2, 1]) |
@show equindex2pass([1, 2, 2, 1]) |
||
@show equindex2pass([-7, 1, 5, 2, -4, 3, 0])</ |
@show equindex2pass([-7, 1, 5, 2, -4, 3, 0])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,459: | Line 1,673: | ||
=={{header|K}}== |
=={{header|K}}== |
||
< |
<syntaxhighlight lang="k"> f:{&{(+/y# x)=+/(y+1)_x}[x]'!#x} |
||
f -7 1 5 2 -4 3 0 |
f -7 1 5 2 -4 3 0 |
||
Line 1,471: | Line 1,685: | ||
f 1 -1 1 -1 1 -1 1 |
f 1 -1 1 -1 1 -1 1 |
||
0 1 2 3 4 5 6</ |
0 1 2 3 4 5 6</syntaxhighlight> |
||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1 |
||
fun equilibriumIndices(a: IntArray): MutableList<Int> { |
fun equilibriumIndices(a: IntArray): MutableList<Int> { |
||
Line 1,498: | Line 1,712: | ||
else -> println("The equilibrium indices are : ${ei.joinToString(", ")}") |
else -> println("The equilibrium indices are : ${ei.joinToString(", ")}") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,506: | Line 1,720: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
<syntaxhighlight lang="lb"> |
|||
<lang lb> |
|||
a(0)=-7 |
a(0)=-7 |
||
a(1)=1 |
a(1)=1 |
||
Line 1,533: | Line 1,747: | ||
if len(EQindex$)>0 then EQindex$=mid$(EQindex$, 1, len(EQindex$)-2) 'remove last ", " |
if len(EQindex$)>0 then EQindex$=mid$(EQindex$, 1, len(EQindex$)-2) 'remove last ", " |
||
end function |
end function |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>EQ Indices are 3, 6 </pre> |
<pre>EQ Indices are 3, 6 </pre> |
||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
< |
<syntaxhighlight lang="logo">to equilibrium.iter :i :before :after :tail :ret |
||
if equal? :before :after [make "ret lput :i :ret] |
if equal? :before :after [make "ret lput :i :ret] |
||
if empty? butfirst :tail [output :ret] |
if empty? butfirst :tail [output :ret] |
||
Line 1,547: | Line 1,761: | ||
end |
end |
||
show equilibrium_index [-7 1 5 2 -4 3 0] ; [4 7]</ |
show equilibrium_index [-7 1 5 2 -4 3 0] ; [4 7]</syntaxhighlight> |
||
=={{header|Lua}}== |
|||
<syntaxhighlight lang="lua"> |
|||
function array_sum(t) |
|||
assert(type(t) == "table", "t must be a table!") |
|||
local sum = 0 |
|||
for i=1, #t do sum = sum + t[i] end |
|||
return sum |
|||
end |
|||
function equilibrium_index(t) |
|||
assert(type(t) == "table", "t must be a table!") |
|||
local left, right, ret = 0, array_sum(t), -1 |
|||
for i,j in pairs(t) do |
|||
right = right - j |
|||
if left == right then |
|||
ret = i |
|||
break |
|||
end |
|||
left = left + j |
|||
end |
|||
return ret |
|||
end |
|||
print(equilibrium_index({-7, 1, 5, 2, -4, 3, 0})) |
|||
</syntaxhighlight> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
Mathematica indexes are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays. |
Mathematica indexes are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays. |
||
< |
<syntaxhighlight lang="mathematica">equilibriumIndex[data_]:=Reap[ |
||
Do[If[Total[data[[;; n - 1]]] == Total[data[[n + 1 ;;]]],Sow[n]], |
Do[If[Total[data[[;; n - 1]]] == Total[data[[n + 1 ;;]]],Sow[n]], |
||
{n, Length[data]}]][[2, 1]]</ |
{n, Length[data]}]][[2, 1]]</syntaxhighlight> |
||
{{out|Usage}} |
{{out|Usage}} |
||
<pre>equilibriumIndex[{-7 , 1, 5 , 2, -4 , 3, 0}] |
<pre>equilibriumIndex[{-7 , 1, 5 , 2, -4 , 3, 0}] |
||
Line 1,560: | Line 1,800: | ||
=={{header|MATLAB}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="matlab">function indicies = equilibriumIndex(list) |
||
indicies = []; |
indicies = []; |
||
Line 1,570: | Line 1,810: | ||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="matlab">>> equilibriumIndex([-7 1 5 2 -4 3 0]) |
||
ans = |
ans = |
||
4 7</ |
4 7</syntaxhighlight> |
||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="netrexx">/* NetRexx */ |
||
options replace format comments java crossref symbols nobinary |
options replace format comments java crossref symbols nobinary |
||
Line 1,617: | Line 1,857: | ||
return |
return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,629: | Line 1,869: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="nim">import math, sequtils, strutils |
||
iterator eqindex(data) = |
iterator eqindex(data: openArray[int]): int = |
||
var suml, ddelayed = 0 |
var suml, ddelayed = 0 |
||
var sumr = sum(data) |
var sumr = sum(data) |
||
Line 1,640: | Line 1,880: | ||
if suml == sumr: |
if suml == sumr: |
||
yield i |
yield i |
||
const d = @[@[-7, 1, 5, 2, -4, 3, 0], |
const d = @[@[-7, 1, 5, 2, -4, 3, 0], |
||
@[2, 4, 6], |
@[2, 4, 6], |
||
@[2, 9, 2], |
@[2, 9, 2], |
||
@[1, -1, 1, -1, 1, -1, 1]] |
@[1, -1, 1, -1, 1, -1, 1]] |
||
for data in d: |
for data in d: |
||
echo "d = ", data |
echo "d = [", data.join(", "), ']' |
||
echo "eqIndex(d) -> ", toSeq(eqindex(data))</ |
echo "eqIndex(d) -> [", toSeq(eqindex(data)).join(", "), ']'</syntaxhighlight> |
||
{{out}} |
|||
<pre>d = [-7, 1, 5, 2, -4, 3, 0] |
|||
eqIndex(d) -> [3, 6] |
|||
d = [2, 4, 6] |
|||
eqIndex(d) -> [] |
|||
d = [2, 9, 2] |
|||
eqIndex(d) -> [1] |
|||
d = [1, -1, 1, -1, 1, -1, 1] |
|||
eqIndex(d) -> [0, 1, 2, 3, 4, 5, 6]</pre> |
|||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{Trans|Java}} |
{{Trans|Java}} |
||
< |
<syntaxhighlight lang="objeck">class Rosetta { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
sequence := [-7, 1, 5, 2, -4, 3, 0]; |
sequence := [-7, 1, 5, 2, -4, 3, 0]; |
||
Line 1,675: | Line 1,925: | ||
}; |
}; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,684: | Line 1,934: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang="ocaml">let lst = [ -7; 1; 5; 2; -4; 3; 0 ] |
||
let sum = List.fold_left ( + ) 0 lst |
let sum = List.fold_left ( + ) 0 lst |
||
Line 1,698: | Line 1,948: | ||
print_string "Results:"; |
print_string "Results:"; |
||
List.iter (Printf.printf " %d") res; |
List.iter (Printf.printf " %d") res; |
||
print_newline()</ |
print_newline ()</syntaxhighlight> |
||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
Line 1,704: | Line 1,954: | ||
Oforth collections are 1-based |
Oforth collections are 1-based |
||
< |
<syntaxhighlight lang="oforth">: equilibrium(l) |
||
| ls rs i e | |
| ls rs i e | |
||
0 ->ls |
0 ->ls |
||
Line 1,712: | Line 1,962: | ||
rs e - dup ->rs ls == ifTrue: [ i over add ] |
rs e - dup ->rs ls == ifTrue: [ i over add ] |
||
ls e + ->ls |
ls e + ->ls |
||
] ;</ |
] ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,722: | Line 1,972: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
This uses 1-based vectors instead of 0-based arrays; subtract 1 from each index if you prefer the other style. |
This uses 1-based vectors instead of 0-based arrays; subtract 1 from each index if you prefer the other style. |
||
< |
<syntaxhighlight lang="parigp">equilib(v)={ |
||
my(a=sum(i=2,#v,v[i]),b=0,u=[]); |
my(a=sum(i=2,#v,v[i]),b=0,u=[]); |
||
for(i=1,#v-1, |
for(i=1,#v-1, |
||
Line 1,730: | Line 1,980: | ||
); |
); |
||
if(b,u,concat(u,#v)) |
if(b,u,concat(u,#v)) |
||
};</ |
};</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang="pascal">Program EquilibriumIndexDemo(output); |
||
{$IFDEF FPC}{$Mode delphi}{$ENDIF} |
|||
function ArraySum(list: array of integer; first, last: integer): integer; |
function ArraySum(list: array of integer; first, last: integer): integer; |
||
Line 1,739: | Line 1,991: | ||
i: integer; |
i: integer; |
||
begin |
begin |
||
Result := 0; |
|||
for i := first to last do // not taken if first > last |
for i := first to last do // not taken if first > last |
||
Result := Result + list[i]; |
|||
end; |
end; |
||
Line 1,766: | Line 2,018: | ||
EquilibriumIndex(numbers, low(numbers)); |
EquilibriumIndex(numbers, low(numbers)); |
||
writeln; |
writeln; |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>:> ./EquilibriumIndex |
<pre>:> ./EquilibriumIndex |
||
Line 1,775: | Line 2,027: | ||
slightly modified.Calculating the sum only once.Using a zero-based array type.Data type could be any type of signed integer or float. |
slightly modified.Calculating the sum only once.Using a zero-based array type.Data type could be any type of signed integer or float. |
||
But beware, that during building the sum, the limits of the data type mustn't be violated. |
But beware, that during building the sum, the limits of the data type mustn't be violated. |
||
< |
<syntaxhighlight lang="pascal">Program EquilibriumIndexDemo(output); |
||
{$IFDEF FPC}{$Mode delphi}{$ENDIF} |
{$IFDEF FPC}{$Mode delphi}{$ENDIF} |
||
type |
type |
||
Line 1,860: | Line 2,112: | ||
numbers[i]:= 0; |
numbers[i]:= 0; |
||
TestRun(numbers); |
TestRun(numbers); |
||
end.</ |
end.</syntaxhighlight>{{out}}<pre>List of numbers: -7 1 5 2 -4 3 0 |
||
Equilibirum indices: 3 6 |
Equilibirum indices: 3 6 |
||
Line 1,868: | Line 2,120: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">sub eq_index { |
||
my ( $i, $sum, %sums ) = ( 0, 0 ); |
my ( $i, $sum, %sums ) = ( 0, 0 ); |
||
Line 1,882: | Line 2,134: | ||
print eq_index qw( 2 4 6 ); # (no eq point) |
print eq_index qw( 2 4 6 ); # (no eq point) |
||
print eq_index qw( 2 9 2 ); # 1 |
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</ |
print eq_index qw( 1 -1 1 -1 1 -1 1 ); # 0 1 2 3 4 5 6</syntaxhighlight> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function equilibrium(sequence s) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
atom lower_sum = 0 |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">equilibrium</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
atom higher_sum = sum(s) |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">lower_sum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> |
|||
sequence res = {} |
|||
<span style="color: #000000;">higher_sum</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to length(s) do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
higher_sum -= s[i] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
if lower_sum=higher_sum then |
|||
<span style="color: #000000;">higher_sum</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
res &= i |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">lower_sum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">higher_sum</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span> |
|||
lower_sum += s[i] |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #000000;">lower_sum</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
return res |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
? equilibrium({-7,1,5,2,-4,3,0})</lang> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">equilibrium</span><span style="color: #0000FF;">({-</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
(Remember that indices are 1-based in Phix) |
(Remember that indices are 1-based in Phix) |
||
Line 1,907: | Line 2,162: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php"><?php |
||
$arr = array(-7, 1, 5, 2, -4, 3, 0); |
$arr = array(-7, 1, 5, 2, -4, 3, 0); |
||
Line 1,924: | Line 2,179: | ||
echo "# results:\n"; |
echo "# results:\n"; |
||
foreach (getEquilibriums($arr) as $r) echo "$r, "; |
foreach (getEquilibriums($arr) as $r) echo "$r, "; |
||
?></ |
?></syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,930: | Line 2,185: | ||
3, 6, |
3, 6, |
||
</pre> |
</pre> |
||
=={{header|Picat}}== |
|||
Note: Picat is 1-based. |
|||
===Prolog-style=== |
|||
{{trans|Prolog}} |
|||
<syntaxhighlight lang="picat">equilibrium_index1(A, Ix) => |
|||
append(Front, [_|Back], A), |
|||
sum(Front) = sum(Back), |
|||
Ix = length(Front)+1. % give 1 based index</syntaxhighlight> |
|||
===Loop approach=== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="picat">equilibrium_index2(A, Ix) => |
|||
Len = A.length, |
|||
Ix1 = [], |
|||
TotalSum = sum(A), |
|||
RunningSum = 0, |
|||
foreach(I in 1..Len) |
|||
AI = A[I], |
|||
if TotalSum - RunningSum - AI == RunningSum then |
|||
Ix1 := Ix1 ++ [I] |
|||
end, |
|||
RunningSum := RunningSum + AI |
|||
end, |
|||
Ix = Ix1.</syntaxhighlight> |
|||
Test the approaches. |
|||
<syntaxhighlight lang="picat">go => |
|||
As = [ |
|||
[-7, 1, 5, 2, -4, 3, 0], % 4 7 |
|||
[ 2, 4, 6], % (no equilibrium point) |
|||
[ 0, 2, 4, 0, 6, 0], % 4 |
|||
[ 2, 9, 2], % 2 |
|||
[ 1, -1, 1, -1, 1, -1, 1] % 1 2 3 4 5 6 7 |
|||
], |
|||
foreach(A in As) |
|||
println(a=A), |
|||
All1 = findall(Ix1, equilibrium_index1(A,Ix1)), |
|||
println(all1=All1), |
|||
equilibrium_index2(A,All2), |
|||
println(all2=All2), |
|||
nl |
|||
end, |
|||
% A larger random instance |
|||
print("A larger random instance:"), |
|||
_ = random2(), |
|||
N = 5001, |
|||
Random = [random(-10,10) : _ in 1..N], |
|||
% println(Random), |
|||
time(R1 = findall(IxR1, equilibrium_index1(Random,IxR1))), |
|||
println(r1=R1), |
|||
time(equilibrium_index2(Random,R2)), |
|||
println(r2=R2), |
|||
nl.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>a = [-7,1,5,2,-4,3,0] |
|||
all1 = [4,7] |
|||
all2 = [4,7] |
|||
a = [2,4,6] |
|||
all1 = [] |
|||
all2 = [] |
|||
a = [0,2,4,0,6,0] |
|||
all1 = [4] |
|||
all2 = [4] |
|||
a = [2,9,2] |
|||
all1 = [2] |
|||
all2 = [2] |
|||
a = [1,-1,1,-1,1,-1,1] |
|||
all1 = [1,2,3,4,5,6,7] |
|||
all2 = [1,2,3,4,5,6,7] |
|||
A larger random instance: |
|||
CPU time 0.113 seconds. |
|||
r1 = [115,372,4082,4254,4258,4261] |
|||
CPU time 0.019 seconds. |
|||
r2 = [115,372,4082,4254,4258,4261]</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de equilibria (Lst) |
||
(make |
(make |
||
(let Sum 0 |
(let Sum 0 |
||
(for ((I . L) Lst L (cdr L)) |
(for ((I . L) Lst L (cdr L)) |
||
(and (= Sum (sum prog (cdr L))) (link I)) |
(and (= Sum (sum prog (cdr L))) (link I)) |
||
(inc 'Sum (car L)) ) ) ) )</ |
(inc 'Sum (car L)) ) ) ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>: (equilibria (-7 1 5 2 -4 3 0)) |
<pre>: (equilibria (-7 1 5 2 -4 3 0)) |
||
Line 1,948: | Line 2,294: | ||
{{works with|PowerShell|2}} |
{{works with|PowerShell|2}} |
||
In real life in PowerShell, one would likely leverage pipelines, ForEach-Object, Where-Object, and Measure-Object for tasks such as this. Normally in PowerShell, speed is an important, but not primary consideration, and the advantages of pipelines tend to outweigh the overhead incurred. However, for this particular task, keeping in mind that “the sequence may be very long,” this code was optimized primarly for speed. |
In real life in PowerShell, one would likely leverage pipelines, ForEach-Object, Where-Object, and Measure-Object for tasks such as this. Normally in PowerShell, speed is an important, but not primary consideration, and the advantages of pipelines tend to outweigh the overhead incurred. However, for this particular task, keeping in mind that “the sequence may be very long,” this code was optimized primarly for speed. |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function Get-EquilibriumIndex ( $Sequence ) |
function Get-EquilibriumIndex ( $Sequence ) |
||
{ |
{ |
||
Line 1,971: | Line 2,317: | ||
return $EqulibriumIndex |
return $EqulibriumIndex |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
Get-EquilibriumIndex -7, 1, 5, 2, -4, 3, 0 |
Get-EquilibriumIndex -7, 1, 5, 2, -4, 3, 0 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,983: | Line 2,329: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
< |
<syntaxhighlight lang="prolog">equilibrium_index(List, Index) :- |
||
append(Front, [_|Back], List), |
append(Front, [_|Back], List), |
||
sumlist(Front, Sum), |
sumlist(Front, Sum), |
||
sumlist(Back, Sum), |
sumlist(Back, Sum), |
||
length(Front, Len), |
length(Front, Len), |
||
Index is Len.</ |
Index is Len.</syntaxhighlight> |
||
Example: |
Example: |
||
< |
<syntaxhighlight lang="prolog">?- equilibrium_index([-7, 1, 5, 2, -4, 3, 0], Index). |
||
Index = 3 ; |
Index = 3 ; |
||
Index = 6 ; |
Index = 6 ; |
||
false.</ |
false.</syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="purebasic">If OpenConsole() |
||
Define i, c=CountProgramParameters()-1 |
Define i, c=CountProgramParameters()-1 |
||
For i=0 To c |
For i=0 To c |
||
Line 2,012: | Line 2,358: | ||
If LSum=RSum: PrintN(Str(i)): EndIf |
If LSum=RSum: PrintN(Str(i)): EndIf |
||
Next i |
Next i |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>> Equilibrium.exe -7 1 5 2 -4 3 0 |
<pre>> Equilibrium.exe -7 1 5 2 -4 3 0 |
||
Line 2,021: | Line 2,367: | ||
===Two Pass=== |
===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. |
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. |
||
< |
<syntaxhighlight lang="python">def eqindex2Pass(data): |
||
"Two pass" |
"Two pass" |
||
suml, sumr, ddelayed = 0, sum(data), 0 |
suml, sumr, ddelayed = 0, sum(data), 0 |
||
Line 2,029: | Line 2,375: | ||
ddelayed = d |
ddelayed = d |
||
if suml == sumr: |
if suml == sumr: |
||
yield i</ |
yield i</syntaxhighlight> |
||
===Multi Pass=== |
===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: |
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: |
||
< |
<syntaxhighlight lang="python">def eqindexMultiPass(data): |
||
"Multi pass" |
"Multi pass" |
||
for i in range(len(data)): |
for i in range(len(data)): |
||
suml, sumr = sum(data[:i]), sum(data[i+1:]) |
suml, sumr = sum(data[:i]), sum(data[i+1:]) |
||
if suml == sumr: |
if suml == sumr: |
||
yield i</ |
yield i</syntaxhighlight> |
||
Shorter alternative: |
Shorter alternative: |
||
< |
<syntaxhighlight lang="python">def eqindexMultiPass(s): |
||
return [i for i in xrange(len(s)) if sum(s[:i]) == sum(s[i+1:])] |
return [i for i in xrange(len(s)) if sum(s[:i]) == sum(s[i+1:])] |
||
print eqindexMultiPass([-7, 1, 5, 2, -4, 3, 0])</ |
print eqindexMultiPass([-7, 1, 5, 2, -4, 3, 0])</syntaxhighlight> |
||
===One Pass=== |
===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. |
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. |
||
< |
<syntaxhighlight lang="python">from collections import defaultdict |
||
def eqindex1Pass(data): |
def eqindex1Pass(data): |
||
Line 2,053: | Line 2,399: | ||
l += c |
l += c |
||
h[l * 2 - c].append(i) |
h[l * 2 - c].append(i) |
||
return h[l]</ |
return h[l]</syntaxhighlight> |
||
===Tests=== |
===Tests=== |
||
< |
<syntaxhighlight lang="python">f = (eqindex2Pass, eqindexMultiPass, eqindex1Pass) |
||
d = ([-7, 1, 5, 2, -4, 3, 0], |
d = ([-7, 1, 5, 2, -4, 3, 0], |
||
[2, 4, 6], |
[2, 4, 6], |
||
Line 2,064: | Line 2,410: | ||
print("d = %r" % data) |
print("d = %r" % data) |
||
for func in f: |
for func in f: |
||
print(" %16s(d) -> %r" % (func.__name__, list(func(data))))</ |
print(" %16s(d) -> %r" % (func.__name__, list(func(data))))</syntaxhighlight> |
||
{{out|Sample output}} |
{{out|Sample output}} |
||
<pre>d = [-7, 1, 5, 2, -4, 3, 0] |
<pre>d = [-7, 1, 5, 2, -4, 3, 0] |
||
Line 2,088: | Line 2,434: | ||
The ''right'' scan can be derived from the left as a map or equivalent list comprehension: |
The ''right'' scan can be derived from the left as a map or equivalent list comprehension: |
||
< |
<syntaxhighlight lang="python">"""Equilibrium index""" |
||
from itertools import (accumulate) |
from itertools import (accumulate) |
||
Line 2,096: | Line 2,442: | ||
def equilibriumIndices(xs): |
def equilibriumIndices(xs): |
||
'''List indices at which the sum of values to the left |
'''List indices at which the sum of values to the left |
||
equals the sum of values to the right. |
equals the sum of values to the right. |
||
''' |
|||
def go(xs): |
def go(xs): |
||
'''Left scan from accumulate, |
'''Left scan from accumulate, |
||
right scan derived from left |
|||
''' |
|||
ls = list(accumulate(xs)) |
ls = list(accumulate(xs)) |
||
n = ls[-1] |
n = ls[-1] |
||
return [ |
return [ |
||
i for (i, (x, y)) in enumerate(zip( |
|||
ls, |
|||
[n] + [n - x for x in ls[0:-1]] |
|||
)) if x == y |
|||
] |
|||
return go(xs) if xs else [] |
return go(xs) if xs else [] |
||
# |
# ------------------------- TEST ------------------------- |
||
# main :: IO () |
# main :: IO () |
||
def main(): |
def main(): |
||
Line 2,126: | Line 2,477: | ||
# |
# ----------------------- GENERIC ------------------------ |
||
# tabulated :: String -> (a -> b) -> [a] -> String |
# tabulated :: String -> (a -> b) -> [a] -> String |
||
def tabulated(s): |
def tabulated(s): |
||
'''heading -> function -> input List |
'''heading -> function -> input List |
||
-> tabulated output string |
|||
def go(f, xs): |
|||
''' |
|||
def go(f): |
|||
def width(x): |
def width(x): |
||
return len(str(x)) |
return len(str(x)) |
||
def cols(xs): |
|||
w = width(max(xs, key=width)) |
|||
return s + '\n' + '\n'.join([ |
|||
str(x).rjust(w, ' ') + ' -> ' + str(f(x)) |
|||
]) |
|||
for x in xs |
|||
]) |
|||
return cols |
|||
return go |
|||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Equilibrium indices: |
<pre>Equilibrium indices: |
||
Line 2,153: | Line 2,508: | ||
[1] -> [0] |
[1] -> [0] |
||
[] -> []</pre> |
[] -> []</pre> |
||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="Quackery"> [ dip [ [] [] 0 ] |
|||
witheach |
|||
[ + dup dip join ] |
|||
over [] swap |
|||
witheach |
|||
[ dip over - join ] |
|||
join |
|||
-1 split drop |
|||
witheach |
|||
[ over i^ peek = if |
|||
[ dip [ i^ join ] ] ] |
|||
drop ] is equilibria ( [ --> [ ) |
|||
' [ -7 1 5 2 -4 3 0 ] equilibria echo</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 3 6 ]</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(define (subsums xs) |
(define (subsums xs) |
||
Line 2,171: | Line 2,547: | ||
(equivilibrium '(-7 1 5 2 -4 3 0)) |
(equivilibrium '(-7 1 5 2 -4 3 0)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="racket"> |
||
'(3 6) |
'(3 6) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
<lang |
<syntaxhighlight lang="raku" line>sub equilibrium_index(@list) { |
||
my ($left,$right) = 0, [+] @list; |
my ($left,$right) = 0, [+] @list; |
||
Line 2,190: | Line 2,566: | ||
my @list = -7, 1, 5, 2, -4, 3, 0; |
my @list = -7, 1, 5, 2, -4, 3, 0; |
||
.say for equilibrium_index(@list).grep(/\d/);</ |
.say for equilibrium_index(@list).grep(/\d/);</syntaxhighlight> |
||
And here's an FP solution that manages to remain O(n): |
And here's an FP solution that manages to remain O(n): |
||
<lang |
<syntaxhighlight lang="raku" line>sub equilibrium_index(@list) { |
||
my @a = [\+] @list; |
my @a = [\+] @list; |
||
my @b = reverse [\+] reverse @list; |
my @b = reverse [\+] reverse @list; |
||
^@list Zxx (@a »==« @b); |
^@list Zxx (@a »==« @b); |
||
}</ |
}</syntaxhighlight> |
||
The <tt>[\+]</tt> is a reduction that returns a list of partial results. The <tt>»==«</tt> is a vectorized equality comparison; it returns a vector of true and false. The <tt>Zxx</tt> 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 <tt>^@list</tt> is just shorthand for <tt>0 ..^ @list</tt>. We could just as easily have used <tt>@list.keys</tt> there. |
The <tt>[\+]</tt> is a reduction that returns a list of partial results. The <tt>»==«</tt> is a vectorized equality comparison; it returns a vector of true and false. The <tt>Zxx</tt> 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 <tt>^@list</tt> is just shorthand for <tt>0 ..^ @list</tt>. We could just as easily have used <tt>@list.keys</tt> there. |
||
=== Single-pass solution === |
=== Single-pass solution === |
||
Line 2,209: | Line 2,585: | ||
Therefore (by substituting L for R), L + C + L == S at all equilibrium points.<br> |
Therefore (by substituting L for R), L + C + L == S at all equilibrium points.<br> |
||
Restated, 2L + C == S. |
Restated, 2L + C == S. |
||
<lang |
<syntaxhighlight lang="raku" line># Original example, with expanded calculations: |
||
0 1 2 3 4 5 6 # Index |
0 1 2 3 4 5 6 # Index |
||
-7 1 5 2 -4 3 0 # C (Value at index) |
-7 1 5 2 -4 3 0 # C (Value at index) |
||
0 -7 -6 -1 1 -3 0 # L (Sum of left) |
0 -7 -6 -1 1 -3 0 # L (Sum of left) |
||
-7 -13 -7 0 -2 -3 0 # 2L+C</ |
-7 -13 -7 0 -2 -3 0 # 2L+C</syntaxhighlight> |
||
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: |
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 |
<syntaxhighlight lang="raku" line>{ |
||
-7 => [ 0, 2 ], |
-7 => [ 0, 2 ], |
||
-13 => [ 1 ], |
-13 => [ 1 ], |
||
Line 2,221: | Line 2,597: | ||
-2 => [ 4 ], |
-2 => [ 4 ], |
||
-3 => [ 5 ], |
-3 => [ 5 ], |
||
}</ |
}</syntaxhighlight> |
||
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. |
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. |
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 |
<syntaxhighlight lang="raku" line>sub eq_index ( *@list ) { |
||
my $sum = 0; |
my $sum = 0; |
||
Line 2,239: | Line 2,615: | ||
say eq_index < 2 4 6 >; # (no eq point) |
say eq_index < 2 4 6 >; # (no eq point) |
||
say eq_index < 2 9 2 >; # 1 |
say eq_index < 2 9 2 >; # 1 |
||
say eq_index < 1 -1 1 -1 1 -1 1 >; # 0 1 2 3 4 5 6</ |
say eq_index < 1 -1 1 -1 1 -1 1 >; # 0 1 2 3 4 5 6</syntaxhighlight> |
||
The <tt>.classify</tt> 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. |
The <tt>.classify</tt> 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 <tt>.pairs</tt> instead of <tt>.keys</tt> to save the cost of <tt>@list</tt> lookups, but that would change each <tt>%h</tt> value to an Array of Pairs, which would complicate the return line. |
We could have used <tt>.pairs</tt> instead of <tt>.keys</tt> to save the cost of <tt>@list</tt> lookups, but that would change each <tt>%h</tt> value to an Array of Pairs, which would complicate the return line. |
||
=={{header|Red}}== |
=={{header|Red}}== |
||
< |
<syntaxhighlight lang="rebol">Red [] |
||
eqindex: func [a [block!]] [ |
eqindex: func [a [block!]] [ |
||
collect [ |
collect [ |
||
Line 2,252: | Line 2,628: | ||
prin "(1 based) equ indices are: " |
prin "(1 based) equ indices are: " |
||
probe eqindex [-7 1 5 2 -4 3 0] |
probe eqindex [-7 1 5 2 -4 3 0] |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>(1 based) equ indices are: [4 7]</pre> |
<pre>(1 based) equ indices are: [4 7]</pre> |
||
=={{header|ReScript}}== |
|||
<syntaxhighlight lang="rescript">let arr = [-7, 1, 5, 2, -4, 3, 0] |
|||
let sum = Js.Array2.reduce(arr, \"+", 0) |
|||
let len = Js.Array.length(arr) |
|||
let rec aux = (acc, i, left, right) => { |
|||
if (i >= len) { acc } else { |
|||
let x = arr[i] |
|||
let right = right - x |
|||
if (left == right) { |
|||
let _ = Js.Array2.push(acc, i) |
|||
} |
|||
aux(acc, i+1, (left + x), right) |
|||
} |
|||
} |
|||
let res = aux([], 0, 0, sum) |
|||
Js.log("Results:") |
|||
Js.Array2.forEach(res, Js.log)</syntaxhighlight> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
This REXX version utilizes a ''zero-based'' stemmed array to mimic the illustrative example in this Rosetta Code task's |
This REXX version utilizes a ''zero-based'' stemmed array to mimic the illustrative example in this Rosetta Code task's |
||
<br>prologue, which uses a ''zero-based'' index. |
<br>prologue, which uses a ''zero-based'' index. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates and displays the equilibrium index for a numeric array (list).*/ |
||
parse arg x /*obtain the optional arguments from CL*/ |
parse arg x /*obtain the optional arguments from CL*/ |
||
if x='' then x= copies(" 7 -7", 50) 7 /*Not specified? Then use the default.*/ |
if x='' then x= copies(" 7 -7", 50) 7 /*Not specified? Then use the default.*/ |
||
Line 2,275: | Line 2,671: | ||
if sum==0 then $= $ i |
if sum==0 then $= $ i |
||
end /*i*/ /* [↑] Zero? Found an equilibrium index*/ |
end /*i*/ /* [↑] Zero? Found an equilibrium index*/ |
||
return $ /*return equilibrium list (may be null)*/</ |
return $ /*return equilibrium list (may be null)*/</syntaxhighlight> |
||
{{out|output|text= when using the input of: <tt> -7 1 5 2 -4 3 0 </tt>}} |
{{out|output|text= when using the input of: <tt> -7 1 5 2 -4 3 0 </tt>}} |
||
<pre> |
<pre> |
||
Line 2,302: | Line 2,698: | ||
===version 2=== |
===version 2=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX --------------------------------------------------------------- |
||
* 30.06.2014 Walter Pachl |
* 30.06.2014 Walter Pachl |
||
*--------------------------------------------------------------------*/ |
*--------------------------------------------------------------------*/ |
||
Line 2,334: | Line 2,730: | ||
eil=eil im1 |
eil=eil im1 |
||
End |
End |
||
Return eil</ |
Return eil</syntaxhighlight> |
||
'''output''' |
'''output''' |
||
<pre> array list: -7 1 5 2 -4 3 0 |
<pre> array list: -7 1 5 2 -4 3 0 |
||
Line 2,350: | Line 2,746: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
list = [-7, 1, 5, 2, -4, 3, 0] |
list = [-7, 1, 5, 2, -4, 3, 0] |
||
see "equilibrium indices are : " + equilibrium(list) + nl |
see "equilibrium indices are : " + equilibrium(list) + nl |
||
Line 2,365: | Line 2,761: | ||
e = left(e,len(e)-1) |
e = left(e,len(e)-1) |
||
return e |
return e |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
equilibrium indices are : 3,6 |
equilibrium indices are : 3,6 |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{| class="wikitable" |
|||
! RPL code |
|||
! Comment |
|||
|- |
|||
| |
|||
≪ |
|||
0 SWAP + → seq |
|||
≪ { } 0 seq ∑LIST |
|||
2 seq SIZE '''FOR''' j |
|||
seq j GET - SWAP seq j 1 - GET + SWAP |
|||
'''IF''' DUP2 == '''THEN''' ROT j 2 - + ROT ROT '''END''' |
|||
'''NEXT''' DROP2 |
|||
≫ ≫ ‘'''EQIDX'''’ STO |
|||
| |
|||
'''EQIDX''' ''( { A0..An } -- { equilibrium index } ) '' |
|||
add zero at list head to avoid GET error at first loop |
|||
left = 0 ; right = A0+A1+...An |
|||
loop from j=2 to length(seq) e.g. A0 to An |
|||
right -= seq[j] ; left += A[j-1] |
|||
if left = right then append j-2 to index list |
|||
drop left and right |
|||
return list |
|||
|} |
|||
{ -7 1 5 2 -4 3 0 } EQIDX |
|||
{{out}} |
|||
<pre> |
|||
1: { 3 6 } |
|||
</pre> |
</pre> |
||
Line 2,374: | Line 2,800: | ||
;Functional Style |
;Functional Style |
||
< |
<syntaxhighlight lang="ruby">def eq_indices(list) |
||
list.each_index.select do |i| |
list.each_index.select do |i| |
||
list[0...i].sum == list[i+1..-1].sum |
list[0...i].sum == list[i+1..-1].sum |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
;Tail Recursion |
;Tail Recursion |
||
* This one would be good if Ruby did tail-call optimization (TCO). |
* This one would be good if Ruby did tail-call optimization (TCO). |
||
* [[MRI]] does not do TCO; so this function fails with a long list (by overflowing the call stack). |
* [[MRI]] does not do TCO; so this function fails with a long list (by overflowing the call stack). |
||
< |
<syntaxhighlight lang="ruby">def eq_indices(list) |
||
result = [] |
result = [] |
||
list.empty? and return result |
list.empty? and return result |
||
Line 2,395: | Line 2,821: | ||
helper.call 0, list.first, list.drop(1).sum, 0 |
helper.call 0, list.first, list.drop(1).sum, 0 |
||
result |
result |
||
end</ |
end</syntaxhighlight> |
||
;Imperative Style (faster) |
;Imperative Style (faster) |
||
< |
<syntaxhighlight lang="ruby">def eq_indices(list) |
||
left, right = 0, list |
left, right = 0, list.sum |
||
equilibrium_indices = [] |
equilibrium_indices = [] |
||
Line 2,408: | Line 2,834: | ||
equilibrium_indices |
equilibrium_indices |
||
end</ |
end</syntaxhighlight> |
||
;Test |
;Test |
||
< |
<syntaxhighlight lang="ruby">indices = [ |
||
[-7, 1, 5, 2,-4, 3, 0], |
[-7, 1, 5, 2,-4, 3, 0], |
||
[2, 4, 6], |
[2, 4, 6], |
||
Line 2,419: | Line 2,845: | ||
indices.each do |x| |
indices.each do |x| |
||
puts "%p => %p" % [x, eq_indices(x)] |
puts "%p => %p" % [x, eq_indices(x)] |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,426: | Line 2,852: | ||
[2, 9, 2] => [1] |
[2, 9, 2] => [1] |
||
[1, -1, 1, -1, 1, -1, 1] => [0, 1, 2, 3, 4, 5, 6] |
[1, -1, 1, -1, 1, -1, 1] => [0, 1, 2, 3, 4, 5, 6] |
||
</pre> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust"> |
|||
extern crate num; |
|||
use num::traits::Zero; |
|||
fn equilibrium_indices(v: &[i32]) -> Vec<usize> { |
|||
let mut right = v.iter().sum(); |
|||
let mut left = i32::zero(); |
|||
v.iter().enumerate().fold(vec![], |mut out, (i, &el)| { |
|||
right -= el; |
|||
if left == right { |
|||
out.push(i); |
|||
} |
|||
left += el; |
|||
out |
|||
}) |
|||
} |
|||
fn main() { |
|||
let v = [-7i32, 1, 5, 2, -4, 3, 0]; |
|||
let indices = equilibrium_indices(&v); |
|||
println!("Equilibrium indices for {:?} are: {:?}", v, indices); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Equilibrium indices for [-7, 1, 5, 2, -4, 3, 0] are: [3, 6] |
|||
</pre> |
</pre> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala"> def getEquilibriumIndex(A: Array[Int]): Int = { |
||
val bigA: Array[BigInt] = A.map(BigInt(_)) |
val bigA: Array[BigInt] = A.map(BigInt(_)) |
||
val partialSums: Array[BigInt] = bigA.scanLeft(BigInt(0))(_+_).tail |
val partialSums: Array[BigInt] = bigA.scanLeft(BigInt(0))(_+_).tail |
||
Line 2,437: | Line 2,895: | ||
def isRandLSumEqual(i: Int): Boolean = lSum(i) == rSum(i) |
def isRandLSumEqual(i: Int): Boolean = lSum(i) == rSum(i) |
||
(0 until partialSums.length).find(isRandLSumEqual).getOrElse(-1) |
(0 until partialSums.length).find(isRandLSumEqual).getOrElse(-1) |
||
} </ |
} </syntaxhighlight> |
||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const array integer: numList is [] (-7, 1, 5, 2, -4, 3, 0); |
const array integer: numList is [] (-7, 1, 5, 2, -4, 3, 0); |
||
Line 2,479: | Line 2,937: | ||
end for; |
end for; |
||
writeln; |
writeln; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,486: | Line 2,944: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func eq_index(nums) { |
||
var (i, sum, sums) = (0, 0, Hash.new); |
var (i, sum, sums) = (0, 0, Hash.new); |
||
nums.each { |n| |
nums.each { |n| |
||
Line 2,493: | Line 2,951: | ||
} |
} |
||
sums{sum} \\ []; |
sums{sum} \\ []; |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="ruby">var indices = [ |
||
[-7, 1, 5, 2,-4, 3, 0], |
[-7, 1, 5, 2,-4, 3, 0], |
||
[2, 4, 6], |
[2, 4, 6], |
||
Line 2,505: | Line 2,963: | ||
for x in indices { |
for x in indices { |
||
say ("%s => %s" % @|[x, eq_index(x)].map{.dump}); |
say ("%s => %s" % @|[x, eq_index(x)].map{.dump}); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,516: | Line 2,974: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">extension Collection where Element: Numeric { |
||
func equilibriumIndexes() -> [Index] { |
func equilibriumIndexes() -> [Index] { |
||
guard !isEmpty else { |
guard !isEmpty else { |
||
Line 2,543: | Line 3,001: | ||
let arr = [-7, 1, 5, 2, -4, 3, 0] |
let arr = [-7, 1, 5, 2, -4, 3, 0] |
||
print("Equilibrium indexes of \(arr): \(arr.equilibriumIndexes())")</ |
print("Equilibrium indexes of \(arr): \(arr.equilibriumIndexes())")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,550: | Line 3,008: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">proc listEquilibria {list} { |
||
set after 0 |
set after 0 |
||
foreach item $list {incr after $item} |
foreach item $list {incr after $item} |
||
Line 2,565: | Line 3,023: | ||
} |
} |
||
return $result |
return $result |
||
}</ |
}</syntaxhighlight> |
||
;Example of use |
;Example of use |
||
< |
<syntaxhighlight lang="tcl">set testData {-7 1 5 2 -4 3 0} |
||
puts Equilibria=[join [listEquilibria $testData] ", "]</ |
puts Equilibria=[join [listEquilibria $testData] ", "]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Equilibria=3, 6</pre> |
<pre>Equilibria=3, 6</pre> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
< |
<syntaxhighlight lang="ursala">#import std |
||
#import int |
#import int |
||
Line 2,580: | Line 3,038: | ||
#cast %nL |
#cast %nL |
||
example = edex <-7,1,5,2,-4,3,0></ |
example = edex <-7,1,5,2,-4,3,0></syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,588: | Line 3,046: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
Solution adopted from http://www.geeksforgeeks.org/equilibrium-index-of-an-array/ . |
Solution adopted from http://www.geeksforgeeks.org/equilibrium-index-of-an-array/ . |
||
< |
<syntaxhighlight lang="vb">arr = Array(-7,1,5,2,-4,3,0) |
||
WScript.StdOut.Write equilibrium(arr,UBound(arr)) |
WScript.StdOut.Write equilibrium(arr,UBound(arr)) |
||
WScript.StdOut.WriteLine |
WScript.StdOut.WriteLine |
||
Line 2,606: | Line 3,064: | ||
leftsum = leftsum + arr(i) |
leftsum = leftsum + arr(i) |
||
Next |
Next |
||
End Function</ |
End Function</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,612: | Line 3,070: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-fmt}} |
|||
<lang ecmascript>var equilibrium = Fn.new { |a| |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
var equilibrium = Fn.new { |a| |
|||
var len = a.count |
var len = a.count |
||
var equi = [] |
var equi = [] |
||
Line 2,624: | Line 3,085: | ||
} |
} |
||
return equi |
return equi |
||
} |
|||
var rset = Fn.new { |m, n| |
|||
var s = "%(n)" |
|||
var c = s.count |
|||
return (m > c) ? " " * (m - c) + s : s |
|||
} |
} |
||
Line 2,643: | Line 3,098: | ||
System.print("The equilibrium indices for the following sequences are:\n") |
System.print("The equilibrium indices for the following sequences are:\n") |
||
for (test in tests) { |
for (test in tests) { |
||
Fmt.print("$24n -> $n", test, equilibrium.call(test)) |
|||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,659: | Line 3,114: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">code Ran=1, ChOut=8, IntOut=11; |
||
def Size = 1_000_000; |
def Size = 1_000_000; |
||
int I, S, A(Size), Hi(Size), Lo(Size); |
int I, S, A(Size), Hi(Size), Lo(Size); |
||
Line 2,669: | Line 3,124: | ||
for I:= 0 to Size-1 do |
for I:= 0 to Size-1 do |
||
if Lo(I) = Hi(I) then [IntOut(0, I); ChOut(0, ^ )]; |
if Lo(I) = Hi(I) then [IntOut(0, I); ChOut(0, ^ )]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,678: | Line 3,133: | ||
=={{header|Yorick}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="yorick">func equilibrium_indices(A) { |
||
return where(A(psum) == A(::-1)(psum)(::-1)); |
return where(A(psum) == A(::-1)(psum)(::-1)); |
||
}</ |
}</syntaxhighlight> |
||
{{out|Example interactive usage}} |
{{out|Example interactive usage}} |
||
<pre>> equilibrium_indices([-7, 1, 5, 2, -4, 3, 0]) |
<pre>> equilibrium_indices([-7, 1, 5, 2, -4, 3, 0]) |
||
Line 2,687: | Line 3,142: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Clojure}} |
{{trans|Clojure}} |
||
< |
<syntaxhighlight lang="zkl">fcn equilibrium(lst){ // two pass |
||
reg acc=List(), left=0,right=lst.sum(0),i=0; |
reg acc=List(), left=0,right=lst.sum(0),i=0; |
||
foreach x in (lst){ |
foreach x in (lst){ |
||
Line 2,695: | Line 3,150: | ||
} |
} |
||
acc |
acc |
||
}</ |
}</syntaxhighlight> |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="zkl">fcn equilibrium(lst){ // lst should immutable, n^2 |
||
(0).filter(lst.len(),'wrap(n){ lst[0,n].sum(0) == lst[n+1,*].sum(0) }) |
(0).filter(lst.len(),'wrap(n){ lst[0,n].sum(0) == lst[n+1,*].sum(0) }) |
||
}</ |
}</syntaxhighlight> |
||
If the input list is immutable, no new lists are generated (other than accumulating the result). |
If the input list is immutable, no new lists are generated (other than accumulating the result). |
||
< |
<syntaxhighlight lang="zkl">equilibrium(T(-7, 1, 5, 2, -4, 3, 0)).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>L(3,6)</pre> |
<pre>L(3,6)</pre> |
||
Line 2,707: | Line 3,162: | ||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
{{trans|AWK}} |
{{trans|AWK}} |
||
< |
<syntaxhighlight lang="zxbasic">10 DATA 7,-7,1,5,2,-4,3,0 |
||
20 READ n |
20 READ n |
||
30 DIM a(n): LET sum=0: LET leftsum=0: LET s$="" |
30 DIM a(n): LET sum=0: LET leftsum=0: LET s$="" |
||
Line 2,718: | Line 3,173: | ||
100 PRINT "Numbers: "; |
100 PRINT "Numbers: "; |
||
110 FOR i=1 TO n: PRINT a(i);" ";: NEXT i |
110 FOR i=1 TO n: PRINT a(i);" ";: NEXT i |
||
120 PRINT '"Indices: ";s$</ |
120 PRINT '"Indices: ";s$</syntaxhighlight> |
Latest revision as of 22:30, 4 March 2024
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 :
3 is an equilibrium index, because:
6 is also an equilibrium index, because:
(sum of zero elements is zero)
7 is not an equilibrium index, because it is not a valid index of sequence .
- Task;
Write a function that, given a sequence, returns its equilibrium indices (if any).
Assume that the sequence may be very long.
11l
F eqindex(arr)
R (0 .< arr.len).filter(i -> sum(@arr[0.<i]) == sum(@arr[i+1..]))
print(eqindex([-7, 1, 5, 2, -4, 3, 0]))
- Output:
[3, 6]
ABAP
REPORT equilibrium_index.
TYPES: y_i TYPE STANDARD TABLE OF i WITH EMPTY KEY.
cl_demo_output=>display( REDUCE y_i( LET sequences = VALUE y_i( ( -7 ) ( 1 ) ( 5 ) ( 2 ) ( -4 ) ( 3 ) ( 0 ) )
total_sum = REDUCE #( INIT sum = 0
FOR sequence IN sequences
NEXT sum = sum + ( sequence ) ) IN
INIT x = VALUE y_i( )
y = 0
FOR i = 1 UNTIL i > lines( sequences )
LET z = sequences[ i ] IN
NEXT x = COND #( WHEN y = ( total_sum - y - z ) THEN VALUE y_i( BASE x ( i - 1 ) ) ELSE x )
y = y + z ) ).
Action!
PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
INT FUNC SumRange(INT ARRAY a INT first,last)
INT sum
INT i
sum=0
FOR i=first TO last
DO
sum==+a(i)
OD
RETURN(sum)
PROC EquilibriumIndices(INT ARRAY a INT size
INT ARRAY indices INT POINTER indSize)
INT i,left,right
indSize^=0
FOR i=0 TO size-1
DO
left=SumRange(a,0,i-1)
right=SumRange(a,i+1,size-1)
IF left=right THEN
indices(indSize^)=i
indSize^==+1
FI
OD
RETURN
PROC Test(INT ARRAY a INT size)
INT ARRAY indices(100)
INT indSize
EquilibriumIndices(a,size,indices,@indSize)
Print("Array=") PrintArray(a,size)
Print("Equilibrium indices=") PrintArray(indices,indSize)
PutE()
RETURN
PROC Main()
INT ARRAY a=[65529 1 5 2 65532 3 0]
INT ARRAY b=[65535 1 65535 1 65535 1 65535]
INT ARRAY c=[1 2 3 4 5 6 7 8 9]
INT ARRAY d=[0]
Test(a,7)
Test(b,7)
Test(c,9)
Test(d,1)
RETURN
- Output:
Screenshot from Atari 8-bit computer
Array=[-7 1 5 2 -4 3 0] Equilibrium indices=[3 6] Array=[-1 1 -1 1 -1 1 -1] Equilibrium indices=[0 1 2 3 4 5 6] Array=[1 2 3 4 5 6 7 8 9] Equilibrium indices=[] Array=[0] Equilibrium indices=[0]
Ada
Generic solution that returns a Vector of Indices.
equilibrium.ads:
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;
equilibrium.adb:
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;
Test program using two different versions, one with vectors and one with arrays:
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;
- Output:
(Index_Type is based on 1):
Results: Array: 4 7 Vector: 4 7
Version that works with Ada 95, too:
equilibrium.adb:
with Ada.Text_IO;
procedure Equilibrium is
type Integer_Sequence is array (Positive range <>) of Integer;
function Seq_Img (From : Integer_Sequence) return String is
begin
if From'First /= From'Last then
return " " & Integer'Image (From (From'First)) &
Seq_Img (From (From'First + 1 .. From'Last));
else
return " " & Integer'Image (From (From'First));
end if;
end Seq_Img;
type Boolean_Sequence is array (Positive range <>) of Boolean;
function Seq_Img (From : Boolean_Sequence) return String is
begin
if From'First > From'Last then
return "";
end if;
if From (From'First) then
return Integer'Image (From'First) &
Seq_Img (From (From'First + 1 .. From'Last));
else
return Seq_Img (From (From'First + 1 .. From'Last));
end if;
end Seq_Img;
function Get_Indices (From : Integer_Sequence) return Boolean_Sequence is
Result : Boolean_Sequence (From'Range) := (others => False);
Left_Sum, Right_Sum : Integer := 0;
begin
for Index in From'Range loop
Right_Sum := Right_Sum + From (Index);
end loop;
for Index in From'Range loop
Right_Sum := Right_Sum - From (Index);
Result (Index) := Left_Sum = Right_Sum;
Left_Sum := Left_Sum + From (Index);
end loop;
return Result;
end Get_Indices;
X1 : Integer_Sequence := (-7, 1, 5, 2, -4, 3, 0);
X1_Result : Boolean_Sequence := Get_Indices (X1);
X2 : Integer_Sequence := ( 2, 4, 6);
X2_Result : Boolean_Sequence := Get_Indices (X2);
X3 : Integer_Sequence := ( 2, 9, 2);
X3_Result : Boolean_Sequence := Get_Indices (X3);
X4 : Integer_Sequence := ( 1, -1, 1, -1, 1 ,-1, 1);
X4_Result : Boolean_Sequence := Get_Indices (X4);
begin
Ada.Text_IO.Put_Line ("Results:");
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X1:" & Seq_Img (X1));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X1_Result));
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X2:" & Seq_Img (X2));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X2_Result));
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X3:" & Seq_Img (X3));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X3_Result));
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("X4:" & Seq_Img (X4));
Ada.Text_IO.Put_Line ("Eqs:" & Seq_Img (X4_Result));
end Equilibrium;
- Output:
Results: X1: -7 1 5 2 -4 3 0 Eqs: 4 7 X2: 2 4 6 Eqs: X3: 2 9 2 Eqs: 2 X4: 1 -1 1 -1 1 -1 1 Eqs: 1 2 3 4 5 6 7
Aime
list
eqindex(list l)
{
integer e, i, s, sum;
list x;
s = sum = 0;
l.ucall(add_i, 1, sum);
for (i, e in l) {
if (s * 2 + e == sum) {
x.append(i);
}
s += e;
}
x;
}
integer
main(void)
{
list(-7, 1, 5, 2, -4, 3, 0).eqindex.ucall(o_, 0, "\n");
0;
}
ALGOL 68
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];
# FOR INT index IN # gen equilibrium index(arr, # ) DO ( #
## (INT index)VOID:
print(index)
# OD # );
print(new line)
)
- Output:
+3 +6
AppleScript
Functional
(ES6 version)
-- equilibriumIndices :: [Int] -> [Int]
on equilibriumIndices(xs)
script balancedPair
on |λ|(a, pair, i)
set {x, y} to pair
if x = y then
{i - 1} & a
else
a
end if
end |λ|
end script
script plus
on |λ|(a, b)
a + b
end |λ|
end script
-- Fold over zipped pairs of sums from left
-- and sums from right
foldr(balancedPair, {}, ¬
zip(scanl1(plus, xs), scanr1(plus, xs)))
end equilibriumIndices
-- TEST -----------------------------------------------------------------------
on run
map(equilibriumIndices, {¬
{-7, 1, 5, 2, -4, 3, 0}, ¬
{2, 4, 6}, ¬
{2, 9, 2}, ¬
{1, -1, 1, -1, 1, -1, 1}, ¬
{1}, ¬
{}})
--> {{3, 6}, {}, {1}, {0, 1, 2, 3, 4, 5, 6}, {0}, {}}
end run
-- GENERIC FUNCTIONS ----------------------------------------------------------
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- foldr :: (a -> b -> a) -> a -> [b] -> a
on foldr(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from lng to 1 by -1
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldr
-- init :: [a] -> [a]
on init(xs)
set lng to length of xs
if lng > 1 then
items 1 thru -2 of xs
else if lng > 0 then
{}
else
missing value
end if
end init
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- scanl :: (b -> a -> b) -> b -> [a] -> [b]
on scanl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
set lst to {startValue}
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
set end of lst to v
end repeat
return lst
end tell
end scanl
-- scanl1 :: (a -> a -> a) -> [a] -> [a]
on scanl1(f, xs)
if length of xs > 0 then
scanl(f, item 1 of xs, tail(xs))
else
{}
end if
end scanl1
-- scanr :: (b -> a -> b) -> b -> [a] -> [b]
on scanr(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
set lst to {startValue}
repeat with i from lng to 1 by -1
set v to |λ|(v, item i of xs, i, xs)
set end of lst to v
end repeat
return reverse of lst
end tell
end scanr
-- scanr1 :: (a -> a -> a) -> [a] -> [a]
on scanr1(f, xs)
if length of xs > 0 then
scanr(f, item -1 of xs, init(xs))
else
{}
end if
end scanr1
-- tail :: [a] -> [a]
on tail(xs)
if length of xs > 1 then
items 2 thru -1 of xs
else
{}
end if
end tail
-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
set lng to min(length of xs, length of ys)
set lst to {}
repeat with i from 1 to lng
set end of lst to {item i of xs, item i of ys}
end repeat
return lst
end zip
- Output:
{{3, 6}, {}, {1}, {0, 1, 2, 3, 4, 5, 6}, {0}, {}}
Straightforward
on equilibriumIndices(sequence)
script o
property seq : sequence
property output : {}
end script
set loSum to 0
set hiSum to 0
repeat with value in o's seq
set hiSum to hiSum + value
end repeat
repeat with i from 1 to (count o's seq)
set value to o's seq's item i
set hiSum to hiSum - value
if (hiSum = loSum) then set o's output's end to i
set loSum to loSum + value
end repeat
return o's output
end equilibriumIndices
equilibriumIndices({-7, 1, 5, 2, -4, 3, 0})
- Output:
AppleScript uses 1-based indices.
{4, 7}
Arturo
eqIndex: function [row][
suml: 0
delayed: 0
sumr: sum row
result: new []
loop.with:'i row 'r [
suml: suml + delayed
sumr: sumr - r
delayed: r
if suml = sumr -> 'result ++ i
]
return result
]
data: @[
@[neg 7, 1, 5, 2, neg 4, 3, 0]
@[2 4 6]
@[2 9 2]
@[1 neg 1 1 neg 1 1 neg 1 1]
]
loop data 'd ->
print [pad.right join.with:", " to [:string] d 25 "=> equilibrium index:" eqIndex d]
- Output:
-7, 1, 5, 2, -4, 3, 0 => equilibrium index: [3 6] 2, 4, 6 => equilibrium index: [] 2, 9, 2 => equilibrium index: [1] 1, -1, 1, -1, 1, -1, 1 => equilibrium index: [0 1 2 3 4 5 6]
AutoHotkey
Equilibrium_index(list, BaseIndex=0){
StringSplit, A, list, `,
Loop % A0 {
i := A_Index , Pre := Post := 0
loop, % A0
if (A_Index < i)
Pre += A%A_Index%
else if (A_Index > i)
Post += A%A_Index%
if (Pre = Post)
Res .= (Res?", ":"") i - (BaseIndex?0:1)
}
return Res
}
Examples:
list = -7, 1, 5, 2, -4, 3, 0
MsgBox % Equilibrium_index(list)
- Output:
3, 6
AWK
# syntax: GAWK -f EQUILIBRIUM_INDEX.AWK
BEGIN {
main("-7 1 5 2 -4 3 0")
main("2 4 6")
main("2 9 2")
main("1 -1 1 -1 1 -1 1")
exit(0)
}
function main(numbers, x) {
x = equilibrium(numbers)
printf("numbers: %s\n",numbers)
printf("indices: %s\n\n",length(x)==0?"none":x)
}
function equilibrium(numbers, arr,i,leftsum,leng,str,sum) {
leng = split(numbers,arr," ")
for (i=1; i<=leng; i++) {
sum += arr[i]
}
for (i=1; i<=leng; i++) {
sum -= arr[i]
if (leftsum == sum) {
str = str i " "
}
leftsum += arr[i]
}
return(str)
}
Output:
numbers: -7 1 5 2 -4 3 0 indices: 4 7 numbers: 2 4 6 indices: none numbers: 2 9 2 indices: 2 numbers: 1 -1 1 -1 1 -1 1 indices: 1 2 3 4 5 6 7
BASIC
BASIC256
arraybase 1
dim list = {-7, 1, 5, 2, -4, 3, 0}
print "equilibrium indices are : "; equilibrium(list)
end
function equilibrium (l)
r = 0: s = 0
e$ = ""
for n = 1 to l[?]
s += l[n]
next
for i = 1 to l[?]
if r = s - r - l[i] then e$ += string(i-1) + " "
r += l[i]
next
e$ = left(e$, length(e$)-1)
return e$
end function
- Output:
The equilibrium indices are : 3 6
Batch File
@echo off
setlocal enabledelayedexpansion
call :equilibrium-index "-7 1 5 2 -4 3 0"
call :equilibrium-index "2 4 6"
call :equilibrium-index "2 9 2"
call :equilibrium-index "1 -1 1 -1 1 -1 1"
pause>nul
exit /b
%== The Function ==%
:equilibrium-index <sequence with quotes>
::Set the pseudo-array sequence...
set "seq=%~1"
set seq.length=0
for %%S in (!seq!) do (
set seq[!seq.length!]=%%S
set /a seq.length+=1
)
::Initialization of other variables...
set "equilms="
set /a last=seq.length - 1
::The main checking...
for /l %%e in (0,1,!last!) do (
set left=0
set right=0
for /l %%i in (0,1,!last!) do (
if %%i lss %%e (set /a left+=!seq[%%i]!)
if %%i gtr %%e (set /a right+=!seq[%%i]!)
)
if !left!==!right! (
if defined equilms (
set "equilms=!equilms! %%e"
) else (
set "equilms=%%e"
)
)
)
echo [!equilms!]
goto :EOF
%==/The Function ==%
- Output:
[3 6] [] [1] [0 1 2 3 4 5 6]
BBC BASIC
BBC BASIC's SUM function is useful for this task.
DIM list(6)
list() = -7, 1, 5, 2, -4, 3, 0
PRINT "Equilibrium indices are " FNequilibrium(list())
END
DEF FNequilibrium(l())
LOCAL i%, r, s, e$
s = SUM(l())
FOR i% = 0 TO DIM(l(),1)
IF r = s - r - l(i%) THEN e$ += STR$(i%) + ","
r += l(i%)
NEXT
= LEFT$(e$)
Output:
Equilibrium indices are 3,6
C
#include <stdio.h>
#include <stdlib.h>
int list[] = {-7, 1, 5, 2, -4, 3, 0};
int eq_idx(int *a, int len, int **ret)
{
int i, sum, s, cnt;
/* alloc long enough: if we can afford the original list,
* we should be able to afford to this. Beats a potential
* million realloc() calls. Even if memory is a real concern,
* there's no garantee the result is shorter than the input anyway */
cnt = s = sum = 0;
*ret = malloc(sizeof(int) * len);
for (i = 0; i < len; i++)
sum += a[i];
for (i = 0; i < len; i++) {
if (s * 2 + a[i] == sum) {
(*ret)[cnt] = i;
cnt++;
}
s += a[i];
}
/* uncouraged way to use realloc since it can leak memory, for example */
*ret = realloc(*ret, cnt * sizeof(int));
return cnt;
}
int main()
{
int i, cnt, *idx;
cnt = eq_idx(list, sizeof(list) / sizeof(int), &idx);
printf("Found:");
for (i = 0; i < cnt; i++)
printf(" %d", idx[i]);
printf("\n");
return 0;
}
C#
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);
}
}
}
- Output:
3
6
C++
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
template <typename T>
std::vector<size_t> equilibrium(T first, T last)
{
typedef typename std::iterator_traits<T>::value_type value_t;
value_t left = 0;
value_t right = std::accumulate(first, last, value_t(0));
std::vector<size_t> result;
for (size_t index = 0; first != last; ++first, ++index)
{
right -= *first;
if (left == right)
{
result.push_back(index);
}
left += *first;
}
return result;
}
template <typename T>
void print(const T& value)
{
std::cout << value << "\n";
}
int main()
{
const int data[] = { -7, 1, 5, 2, -4, 3, 0 };
std::vector<size_t> indices(equilibrium(data, data + 7));
std::for_each(indices.begin(), indices.end(), print<size_t>);
}
- Output:
3 6
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)))))
- Output:
> (equilibrium [-7, 1, 5, 2, -4, 3, 0]) (3 6)
Common Lisp
(defun dflt-on-nil (v dflt)
(if v v dflt))
(defun eq-index (v)
(do*
((stack nil)
(i 0 (+ 1 i))
(rest v (cdr rest))
(lsum 0)
(rsum (apply #'+ (cdr v))))
;; Reverse here is not strictly necessary
((null rest) (reverse stack))
(if (eql lsum rsum) (push i stack))
(setf lsum (+ lsum (car rest)))
(setf rsum (- rsum (dflt-on-nil (cadr rest) 0)))))
- Output:
(eq-index '(-7 1 5 2 -4 3 0))
(3 6)
D
More Functional Style
import std.stdio, std.algorithm, std.range, std.functional;
auto equilibrium(Range)(Range r) pure nothrow @safe /*@nogc*/ {
return r.length.iota.filter!(i => r[0 .. i].sum == r[i + 1 .. $].sum);
}
void main() {
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln;
}
- Output:
[3, 6]
Less Functional Style
Same output.
import std.stdio, std.algorithm;
size_t[] equilibrium(T)(in T[] items) @safe pure nothrow {
size_t[] result;
T left = 0, right = items.sum;
foreach (immutable i, e; items) {
right -= e;
if (right == left)
result ~= i;
left += e;
}
return result;
}
void main() {
[-7, 1, 5, 2, -4, 3, 0].equilibrium.writeln;
}
Delphi
See Pascal.
EasyLang
func[] equind a[] .
for v in a[]
sumr += v
.
for i to len a[]
sumr -= a[i]
if suml = sumr
r[] &= i
.
suml += a[i]
.
return r[]
.
print equind [ -7 1 5 2 -4 3 0 ]
- Output:
[ 4 7 ]
Elena
ELENA 6.x :
import extensions;
import system'routines;
import system'collections;
import extensions'routines;
class EquilibriumEnumerator : Enumerator
{
int left;
int right;
int index;
Enumerator en;
constructor new(Enumerator en)
{
this en := en;
self.reset()
}
constructor new(Enumerable list)
<= new(list.enumerator());
constructor new(o)
<= new(cast Enumerable(o));
bool next()
{
index += 1;
while(en.next())
{
var element := *en;
right -= element;
bool found := (left == right);
left += element;
if (found)
{
^ true
};
index += 1
};
^ false
}
reset()
{
en.reset();
left := 0;
right := en.summarize();
index := -1;
en.reset();
}
get Value() = index;
enumerable() => en;
}
public program()
{
EquilibriumEnumerator.new(new int[]{ -7, 1, 5, 2, -4, 3, 0 })
.forEach(printingLn)
}
3 6
Elixir
computes either side each time.
defmodule Equilibrium do
def index(list) do
last = length(list)
Enum.filter(0..last-1, fn i ->
Enum.sum(Enum.slice(list, 0, i)) == Enum.sum(Enum.slice(list, i+1..last))
end)
end
end
faster version:
defmodule Equilibrium do
def index(list), do: index(list,0,0,Enum.sum(list),[])
defp index([],_,_,_,acc), do: Enum.reverse(acc)
defp index([h|t],i,left,right,acc) when left==right-h, do: index(t,i+1,left+h,right-h,[i|acc])
defp index([h|t],i,left,right,acc) , do: index(t,i+1,left+h,right-h,acc)
end
Test:
indices = [
[-7, 1, 5, 2,-4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1,-1, 1,-1, 1,-1, 1]
]
Enum.each(indices, fn list ->
IO.puts "#{inspect list} => #{inspect Equilibrium.index(list)}"
end)
- Output:
[-7, 1, 5, 2, -4, 3, 0] => [3, 6] [2, 4, 6] => [] [2, 9, 2] => [1] [1, -1, 1, -1, 1, -1, 1] => [0, 1, 2, 3, 4, 5, 6]
ERRE
PROGRAM EQUILIBRIUM
DIM LISTA[6]
PROCEDURE EQ(LISTA[]->RES$)
LOCAL I%,R,S,E$
FOR I%=0 TO UBOUND(LISTA,1) DO
S+=LISTA[I%]
END FOR
FOR I%=0 TO UBOUND(LISTA,1) DO
IF R=S-R-LISTA[I%] THEN E$+=STR$(I%)+"," END IF
R+=LISTA[I%]
END FOR
RES$=LEFT$(E$,LEN(E$)-1)
END PROCEDURE
BEGIN
LISTA[]=(-7,1,5,2,-4,3,0)
EQ(LISTA[]->RES$)
PRINT("Equilibrium indices are";RES$)
END PROGRAM
Output:
Equilibrium indices are 3, 6
Euphoria
function equilibrium(sequence s)
integer lower_sum, higher_sum
sequence indices
lower_sum = 0
higher_sum = 0
for i = 1 to length(s) do
higher_sum += s[i]
end for
indices = {}
for i = 1 to length(s) do
higher_sum -= s[i]
if lower_sum = higher_sum then
indices &= i
end if
lower_sum += s[i]
end for
return indices
end function
? equilibrium({-7,1,5,2,-4,3,0})
- Output:
(Remember that indices are 1-based in Euphoria)
{4,7}
Factor
Executed in the listener. Note that accum-left
and accum-right
have different outputs than accumulate
as they drop the final result.
USE: math.vectors
: accum-left ( seq id quot -- seq ) accumulate nip ; inline
: accum-right ( seq id quot -- seq ) [ <reversed> ] 2dip accum-left <reversed> ; inline
: equilibrium-indices ( seq -- inds )
0 [ + ] [ accum-left ] [ accum-right ] 3bi [ = ] 2map
V{ } swap dup length iota [ [ suffix ] curry [ ] if ] 2each ;
- Output:
( scratchpad ) { -7 1 5 2 -4 3 0 } equilibrium-indices .
V{ 3 6 }
Fortran
Array indices are 1-based.
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
FreeBASIC
' FB 1.05.0 Win64
Sub equilibriumIndices (a() As Integer, b() As Integer)
If UBound(a) = -1 Then Return '' empty array
Dim sum As Integer = 0
Dim count As Integer = 0
For i As Integer = LBound(a) To UBound(a) : sum += a(i) : Next
Dim sumLeft As Integer = 0, sumRight As Integer = 0
For i As Integer = LBound(a) To UBound(a)
sumRight = sum - sumLeft - a(i)
If sumLeft = sumRight Then
Redim Preserve b(0 To Count)
b(count) = i
count += 1
End If
sumLeft += a(i)
Next
End Sub
Dim a(0 To 6) As Integer = { -7, 1, 5, 2, -4, 3, 0 }
Dim b() As Integer
equilibriumIndices a(), b()
If UBound(b) = -1 Then
Print "There are no equilibrium indices"
ElseIf UBound(b) = LBound(b) Then
Print "The only equilibrium index is : "; b(LBound(b))
Else
Print "The equilibrium indices are : "
For i As Integer = LBound(b) To UBound(b) : Print b(i); " "; : Next
End If
Print
Print "Press any key to quit"
Sleep
- Output:
The equilibrium indices are : 3 6
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
In Fōrmulæ, indices are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays.
Test cases
Go
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
fmt.Println(ex([]int32{-7, 1, 5, 2, -4, 3, 0}))
// sequence of 1,000,000 random numbers, with values
// chosen so that it will be likely to have a couple
// of equalibrium indexes.
rand.Seed(time.Now().UnixNano())
verylong := make([]int32, 1e6)
for i := range verylong {
verylong[i] = rand.Int31n(1001) - 500
}
fmt.Println(ex(verylong))
}
func ex(s []int32) (eq []int) {
var r, l int64
for _, el := range s {
r += int64(el)
}
for i, el := range s {
r -= int64(el)
if l == r {
eq = append(eq, i)
}
l += int64(el)
}
return
}
- Output:
[3 6] [145125 947872]
Haskell
import System.Random (randomRIO)
import Data.List (findIndices, takeWhile)
import Control.Monad (replicateM)
import Control.Arrow ((&&&))
equilibr xs =
findIndices (\(a, b) -> sum a == sum b) . takeWhile (not . null . snd) $
flip ((&&&) <$> take <*> (drop . pred)) xs <$> [1 ..]
langeSliert = replicateM 2000 (randomRIO (-15, 15) :: IO Int) >>= print . equilibr
Small example
*Main> equilibr [-7, 1, 5, 2, -4, 3, 0]
[3,6]
Long random list in langeSliert (several tries for this one)
*Main> langeSliert
[231,245,259,265,382,1480,1611,1612]
Or, using default Prelude functions:
equilibriumIndices :: [Int] -> [Int]
equilibriumIndices xs =
zip3
(scanl1 (+) xs) -- Sums from the left
(scanr1 (+) xs) -- Sums from the right
[0 ..] -- Indices
>>= (\(x, y, i) -> [i | x == y])
--------------------------- TEST -------------------------
main :: IO ()
main =
mapM_
print
$ equilibriumIndices
<$> [ [-7, 1, 5, 2, -4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1, -1, 1, -1, 1, -1, 1],
[1],
[]
]
- Output:
[3,6] [] [1] [0,1,2,3,4,5,6] [0] []
Icon and Unicon
- Output:
equilibrium indicies of [ -7 1 5 2 -4 3 0 ] = 4 7
J
equilidx=: +/\ I.@:= +/\.
- Example use:
equilidx _7 1 5 2 _4 3 0
3 6
Java
public class Equlibrium {
public static void main(String[] args) {
int[] sequence = {-7, 1, 5, 2, -4, 3, 0};
equlibrium_indices(sequence);
}
public static void equlibrium_indices(int[] sequence){
//find total sum
int totalSum = 0;
for (int n : sequence) {
totalSum += n;
}
//compare running sum to remaining sum to find equlibrium indices
int runningSum = 0;
for (int i = 0; i < sequence.length; i++) {
int n = sequence[i];
if (totalSum - runningSum - n == runningSum) {
System.out.println(i);
}
runningSum += n;
}
}
}
- Output:
3 6
JavaScript
ES5
function equilibrium(a) {
var N = a.length, i, l = [], r = [], e = []
for (l[0] = a[0], r[N - 1] = a[N - 1], i = 1; i<N; i++)
l[i] = l[i - 1] + a[i], r[N - i - 1] = r[N - i] + a[N - i - 1]
for (i = 0; i < N; i++)
if (l[i] === r[i]) e.push(i)
return e
}
// test & output
[ [-7, 1, 5, 2, -4, 3, 0], // 3, 6
[2, 4, 6], // empty
[2, 9, 2], // 1
[1, -1, 1, -1, 1, -1, 1], // 0,1,2,3,4,5,6
[1], // 0
[] // empty
].forEach(function(x) {
console.log(equilibrium(x))
});
- Output:
[[3,6],[],[1],[0,1,2,3,4,5,6],[0],[]]
ES6 Procedural
Two pass O(n), returning only the first equilibrium index.
function equilibrium(arr) {
let sum = arr.reduce((a, b) => a + b);
let leftSum = 0;
for (let i = 0; i < arr.length; ++i) {
sum -= arr[i];
if (leftSum === sum) {
return i;
}
leftSum += arr[i];
}
return -1;
}
- Output:
3, -1, 1, 0, 0
ES6 Functional
A composition of pure generic functions, returning all equilibrium indices.
(() => {
"use strict";
// ------------- ALL EQUILIBRIUM INDICES -------------
// equilibriumIndices :: [Int] -> [Int]
const equilibriumIndices = xs =>
zip(
scanl1(add)(xs)
)(
scanr1(add)(xs)
)
.reduceRight(
(a, xy, i) => xy[0] === xy[1] ? (
[i, ...a]
) : a, []
);
// ---------------------- TEST -----------------------
const main = () => [
[-7, 1, 5, 2, -4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1, -1, 1, -1, 1, -1, 1],
[1],
[]
].map(compose(
JSON.stringify,
equilibriumIndices
))
.join("\n");
// -> [[3, 6], [], [1], [0, 1, 2, 3, 4, 5, 6], [0], []]
// ---------------- GENERIC FUNCTIONS ----------------
// add (+) :: Num a => a -> a -> a
const add = a =>
// Curried addition.
b => a + b;
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...fs) =>
// A function defined by the right-to-left
// composition of all the functions in fs.
fs.reduce(
(f, g) => x => f(g(x)),
x => x
);
// scanl :: (b -> a -> b) -> b -> [a] -> [b]
const scanl = f => startValue => xs =>
// The series of interim values arising
// from a catamorphism. Parallel to foldl.
xs.reduce((a, x) => {
const v = f(a[0])(x);
return [v, a[1].concat(v)];
}, [startValue, [startValue]])[1];
// scanl1 :: (a -> a -> a) -> [a] -> [a]
const scanl1 = f =>
// scanl1 is a variant of scanl that has no
// starting value argument.
xs => xs.length > 0 ? (
scanl(f)(
xs[0]
)(xs.slice(1))
) : [];
// scanr :: (a -> b -> b) -> b -> [a] -> [b]
const scanr = f =>
startValue => xs => xs.reduceRight(
(a, x) => {
const v = f(x)(a[0]);
return [v, [v].concat(a[1])];
}, [startValue, [startValue]]
)[1];
// scanr1 :: (a -> a -> a) -> [a] -> [a]
const scanr1 = f =>
// scanr1 is a variant of scanr that has no
// seed-value argument, and assumes that
// xs is not empty.
xs => xs.length > 0 ? (
scanr(f)(
xs.slice(-1)[0]
)(xs.slice(0, -1))
) : [];
// zip :: [a] -> [b] -> [(a, b)]
const zip = xs =>
// The paired members of xs and ys, up to
// the length of the shorter of the two lists.
ys => Array.from({
length: Math.min(xs.length, ys.length)
}, (_, i) => [xs[i], ys[i]]);
// MAIN ---
return main();
})();
- Output:
[3,6] [] [1] [0,1,2,3,4,5,6] [0] []
jq
Also works with gojq, the Go implementation of jq, and jaq
`equilibrium_indices` is defined as a 0-arity filter that emits answers as a stream, as is idiomatic in jq.
# The index origin is 0 in jq.
def equilibrium_indices:
. as $in
| add as $add
| foreach range(0;length) as $i (
[0, 0, $add]; # [before, pivot, after]
$in[$i] as $x | [.[0]+.[1], $x, .[2] - $x];
if .[0] == .[2] then $i else empty end) ;
Example 1:
[-7, 1, 5, 2, -4, 3, 0] | equilibrium_indices
- Output:
$ jq -M -n -f equilibrium_indices.jq 3 6
Example 2:
def count(g): reduce g as $i (0; .+1);
# Create an array of length n with "init" elements:
def array(n;init): reduce range(0;n) as $i ([]; . + [0]);
count( array(10000;0) | equilibrium_indices )
- Output:
$ jq -M -n -f equilibrium_indices.jq 10000
Julia
function equindex2pass(data::Array)
rst = Vector{Int}(0)
suml, sumr, ddelayed = 0, sum(data), 0
for (i, d) in enumerate(data)
suml += ddelayed
sumr -= d
ddelayed = d
if suml == sumr
push!(rst, i)
end
end
return rst
end
@show equindex2pass([1, -1, 1, -1, 1, -1, 1])
@show equindex2pass([1, 2, 2, 1])
@show equindex2pass([-7, 1, 5, 2, -4, 3, 0])
- Output:
equindex2pass([1, -1, 1, -1, 1, -1, 1]) = [1, 2, 3, 4, 5, 6, 7] equindex2pass([1, 2, 2, 1]) = Int64[] equindex2pass([-7, 1, 5, 2, -4, 3, 0]) = [4, 7]
K
f:{&{(+/y# x)=+/(y+1)_x}[x]'!#x}
f -7 1 5 2 -4 3 0
3 6
f 2 4 6
!0
f 2 9 2
,1
f 1 -1 1 -1 1 -1 1
0 1 2 3 4 5 6
Kotlin
// version 1.1
fun equilibriumIndices(a: IntArray): MutableList<Int> {
val ei = mutableListOf<Int>()
if (a.isEmpty()) return ei // empty list
val sumAll = a.sumBy { it }
var sumLeft = 0
var sumRight: Int
for (i in 0 until a.size) {
sumRight = sumAll - sumLeft - a[i]
if (sumLeft == sumRight) ei.add(i)
sumLeft += a[i]
}
return ei
}
fun main(args: Array<String>) {
val a = intArrayOf(-7, 1, 5, 2, -4, 3, 0)
val ei = equilibriumIndices(a)
when (ei.size) {
0 -> println("There are no equilibrium indices")
1 -> println("The only equilibrium index is : ${ei[0]}")
else -> println("The equilibrium indices are : ${ei.joinToString(", ")}")
}
}
- Output:
The equilibrium indices are : 3, 6
Liberty BASIC
a(0)=-7
a(1)=1
a(2)=5
a(3)=2
a(4)=-4
a(5)=3
a(6)=0
print "EQ Indices are ";EQindex$("a",0,6)
wait
function EQindex$(b$,mini,maxi)
if mini>=maxi then exit function
sum=0
for i = mini to maxi
sum=sum+eval(b$;"(";i;")")
next
sumA=0:sumB=sum
for i = mini to maxi
sumB = sumB - eval(b$;"(";i;")")
if sumA=sumB then EQindex$=EQindex$+str$(i)+", "
sumA = sumA + eval(b$;"(";i;")")
next
if len(EQindex$)>0 then EQindex$=mid$(EQindex$, 1, len(EQindex$)-2) 'remove last ", "
end function
- Output:
EQ Indices are 3, 6
Logo
to equilibrium.iter :i :before :after :tail :ret
if equal? :before :after [make "ret lput :i :ret]
if empty? butfirst :tail [output :ret]
output equilibrium.iter :i+1 (:before+first :tail) (:after-first butfirst :tail) (butfirst :tail) :ret
end
to equilibrium.index :list
output equilibrium.iter 1 0 (apply "sum butfirst :list) :list []
end
show equilibrium_index [-7 1 5 2 -4 3 0] ; [4 7]
Lua
function array_sum(t)
assert(type(t) == "table", "t must be a table!")
local sum = 0
for i=1, #t do sum = sum + t[i] end
return sum
end
function equilibrium_index(t)
assert(type(t) == "table", "t must be a table!")
local left, right, ret = 0, array_sum(t), -1
for i,j in pairs(t) do
right = right - j
if left == right then
ret = i
break
end
left = left + j
end
return ret
end
print(equilibrium_index({-7, 1, 5, 2, -4, 3, 0}))
Mathematica / Wolfram Language
Mathematica indexes are 1-based so the output of this program will be shifted up by one compared to solutions in languages with 0-based arrays.
equilibriumIndex[data_]:=Reap[
Do[If[Total[data[[;; n - 1]]] == Total[data[[n + 1 ;;]]],Sow[n]],
{n, Length[data]}]][[2, 1]]
- Usage:
equilibriumIndex[{-7 , 1, 5 , 2, -4 , 3, 0}] {4, 7}
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.
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
- Output:
>> equilibriumIndex([-7 1 5 2 -4 3 0])
ans =
4 7
NetRexx
/* NetRexx */
options replace format comments java crossref symbols nobinary
numeric digits 20
runSample(arg)
return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- @see http://www.geeksforgeeks.org/equilibrium-index-of-an-array/
method equilibriumIndex(sequence) private static
es = ''
loop ix = 1 to sequence.words()
sum = 0
loop jx = 1 to sequence.words()
if jx < ix then sum = sum + sequence.word(jx)
if jx > ix then sum = sum - sequence.word(jx)
end jx
if sum = 0 then es = es ix
end ix
return es
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
-- Note: A Rexx object based list of "words" starts at index 1
sequences = [ -
'-7 1 5 2 -4 3 0', - -- 4 7
' 2 4 6' , - -- (no equilibrium point)
' 0 2 4 0 6 0' , - -- 4
' 2 9 2' , - -- 2
' 1 -1 1 -1 1 -1 1' - -- 1 2 3 4 5 6 7
]
loop sequence over sequences
say 'For sequence "'sequence.space(1, ',')'" the equilibrium indices are: \-'
say '"'equilibriumIndex(sequence).space(1, ',')'"'
end sequence
return
- Output:
For sequence "-7,1,5,2,-4,3,0" the equilibrium indices are: "4,7" For sequence "2,4,6" the equilibrium indices are: "" For sequence "0,2,4,0,6,0" the equilibrium indices are: "4" For sequence "2,9,2" the equilibrium indices are: "2" For sequence "1,-1,1,-1,1,-1,1" the equilibrium indices are: "1,2,3,4,5,6,7"
Nim
import math, sequtils, strutils
iterator eqindex(data: openArray[int]): int =
var suml, ddelayed = 0
var sumr = sum(data)
for i,d in data:
suml += ddelayed
sumr -= d
ddelayed = d
if suml == sumr:
yield i
const 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:
echo "d = [", data.join(", "), ']'
echo "eqIndex(d) -> [", toSeq(eqindex(data)).join(", "), ']'
- Output:
d = [-7, 1, 5, 2, -4, 3, 0] eqIndex(d) -> [3, 6] d = [2, 4, 6] eqIndex(d) -> [] d = [2, 9, 2] eqIndex(d) -> [1] d = [1, -1, 1, -1, 1, -1, 1] eqIndex(d) -> [0, 1, 2, 3, 4, 5, 6]
Objeck
class Rosetta {
function : Main(args : String[]) ~ Nil {
sequence := [-7, 1, 5, 2, -4, 3, 0];
EqulibriumIndices(sequence);
}
function : EqulibriumIndices(sequence : Int[]) ~ Nil {
# find total sum
totalSum := 0;
each(i : sequence) {
totalSum += sequence[i];
};
# compare running sum to remaining sum to find equlibrium indices
runningSum := 0;
each(i : sequence) {
n := sequence[i];
if (totalSum - runningSum - n = runningSum) {
i->PrintLine();
};
runningSum += n;
};
}
}
Output:
3 6
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 ()
Oforth
Oforth collections are 1-based
: equilibrium(l)
| ls rs i e |
0 ->ls
l sum ->rs
ListBuffer new l size loop: i [
l at(i) ->e
rs e - dup ->rs ls == ifTrue: [ i over add ]
ls e + ->ls
] ;
- Output:
>equilibrium([-7, 1, 5, 2, -4, 3, 0]) println [4, 7]
PARI/GP
This uses 1-based vectors instead of 0-based arrays; subtract 1 from each index if you prefer the other style.
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))
};
Pascal
Program EquilibriumIndexDemo(output);
{$IFDEF FPC}{$Mode delphi}{$ENDIF}
function ArraySum(list: array of integer; first, last: integer): integer;
var
i: integer;
begin
Result := 0;
for i := first to last do // not taken if first > last
Result := Result + list[i];
end;
procedure EquilibriumIndex(list: array of integer; offset: integer);
var
i: integer;
begin
for i := low(list) to high(list) do
if ArraySum(list, low(list), i-1) = ArraySum(list, i+1, high(list)) then
write(offset + i:3);
end;
var
{** The base index of the array is fully taken care off and can be any number. **}
numbers: array [1..7] of integer = (-7, 1, 5, 2, -4, 3, 0);
i: integer;
begin
write('List of numbers: ');
for i := low(numbers) to high(numbers) do
write(numbers[i]:3);
writeln;
write('Equilibirum indices: ');
EquilibriumIndex(numbers, low(numbers));
writeln;
end.
- Output:
:> ./EquilibriumIndex List of numbers: -7 1 5 2 -4 3 0 Equilibirum indices: 4 7
alternative
slightly modified.Calculating the sum only once.Using a zero-based array type.Data type could be any type of signed integer or float. But beware, that during building the sum, the limits of the data type mustn't be violated.
Program EquilibriumIndexDemo(output);
{$IFDEF FPC}{$Mode delphi}{$ENDIF}
type
tEquiData = shortInt;//Int64;extended ,double
tnumList = array of tEquiData;
tresList = array of LongInt;
const
cNumbers: array [11..17] of tEquiData = (-7, 1, 5, 2, -4, 3, 0);
function ArraySum(const list: tnumList):tEquiData;
var
i: integer;
begin
result := 0;
for i := Low(list) to High(list) do
result := result+list[i];
end;
procedure EquilibriumIndex(const list:tnumList;
var indices:tresList);
var
pC : ^tEquiData;
LeftSum,
RightSum : tEquiData;
i,idx,HiList: integer;
begin
HiList := High(List);
RightSum :=ArraySum(list);
setlength(indices,10);
idx := 0;
i := -Hilist;
pC := @List[0];
LeftSum:= 0;
repeat
Rightsum:= RightSum-pC^;
IF LeftSum = RightSum then
Begin
indices[idx] := Hilist+i;
inc(idx);
IF idx > high(indices) then
setlength(indices, idx+10);
end;
inc(i);
leftSum := leftsum+pC^;
inc(pC);
until i>=0;
leftSum := leftsum+pC^;
IF LeftSum = RightSum then
Begin
indices[idx] := Hilist+i;
inc(idx);
end;
setlength(indices,idx);
end;
procedure TestRun(const numbers:tnumList);
var
indices : tresList;
i: integer;
Begin
write('List of numbers: ');
for i := low(numbers) to high(numbers) do
write(numbers[i]:3);
writeln;
EquilibriumIndex(numbers,indices);
write('Equilibirum indices: ');
EquilibriumIndex(numbers,indices);
for i := low(indices) to high(indices) do
write(indices[i]:3);
writeln;
writeln;
end;
var
numbers: tnumList;
I: integer;
begin
setlength(numbers,High(cNumbers)-Low(cNumbers)+1);
move(cNumbers[Low(cNumbers)],numbers[0],sizeof(cnumbers));
TestRun(numbers);
for i := low(numbers) to high(numbers) do
numbers[i]:= 0;
TestRun(numbers);
end.
- Output:
List of numbers: -7 1 5 2 -4 3 0Equilibirum indices: 3 6
List of numbers: 0 0 0 0 0 0 0
Equilibirum indices: 0 1 2 3 4 5 6
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
Phix
with javascript_semantics function equilibrium(sequence s) atom lower_sum = 0, higher_sum = sum(s) sequence res = {} for i=1 to length(s) do higher_sum -= s[i] if lower_sum=higher_sum then res &= i end if lower_sum += s[i] end for return res end function ?equilibrium({-7,1,5,2,-4,3,0})
- Output:
(Remember that indices are 1-based in Phix)
{4,7}
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, ";
?>
- Output:
# results: 3, 6,
Picat
Note: Picat is 1-based.
Prolog-style
equilibrium_index1(A, Ix) =>
append(Front, [_|Back], A),
sum(Front) = sum(Back),
Ix = length(Front)+1. % give 1 based index
Loop approach
equilibrium_index2(A, Ix) =>
Len = A.length,
Ix1 = [],
TotalSum = sum(A),
RunningSum = 0,
foreach(I in 1..Len)
AI = A[I],
if TotalSum - RunningSum - AI == RunningSum then
Ix1 := Ix1 ++ [I]
end,
RunningSum := RunningSum + AI
end,
Ix = Ix1.
Test the approaches.
go =>
As = [
[-7, 1, 5, 2, -4, 3, 0], % 4 7
[ 2, 4, 6], % (no equilibrium point)
[ 0, 2, 4, 0, 6, 0], % 4
[ 2, 9, 2], % 2
[ 1, -1, 1, -1, 1, -1, 1] % 1 2 3 4 5 6 7
],
foreach(A in As)
println(a=A),
All1 = findall(Ix1, equilibrium_index1(A,Ix1)),
println(all1=All1),
equilibrium_index2(A,All2),
println(all2=All2),
nl
end,
% A larger random instance
print("A larger random instance:"),
_ = random2(),
N = 5001,
Random = [random(-10,10) : _ in 1..N],
% println(Random),
time(R1 = findall(IxR1, equilibrium_index1(Random,IxR1))),
println(r1=R1),
time(equilibrium_index2(Random,R2)),
println(r2=R2),
nl.
- Output:
a = [-7,1,5,2,-4,3,0] all1 = [4,7] all2 = [4,7] a = [2,4,6] all1 = [] all2 = [] a = [0,2,4,0,6,0] all1 = [4] all2 = [4] a = [2,9,2] all1 = [2] all2 = [2] a = [1,-1,1,-1,1,-1,1] all1 = [1,2,3,4,5,6,7] all2 = [1,2,3,4,5,6,7] A larger random instance: CPU time 0.113 seconds. r1 = [115,372,4082,4254,4258,4261] CPU time 0.019 seconds. r2 = [115,372,4082,4254,4258,4261]
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)) ) ) ) )
- 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)
PowerShell
In real life in PowerShell, one would likely leverage pipelines, ForEach-Object, Where-Object, and Measure-Object for tasks such as this. Normally in PowerShell, speed is an important, but not primary consideration, and the advantages of pipelines tend to outweigh the overhead incurred. However, for this particular task, keeping in mind that “the sequence may be very long,” this code was optimized primarly for speed.
function Get-EquilibriumIndex ( $Sequence )
{
$Indexes = 0..($Sequence.Count - 1)
$EqulibriumIndex = @()
ForEach ( $TestIndex in $Indexes )
{
$Left = 0
$Right = 0
ForEach ( $Index in $Indexes )
{
If ( $Index -lt $TestIndex ) { $Left += $Sequence[$Index] }
ElseIf ( $Index -gt $TestIndex ) { $Right += $Sequence[$Index] }
}
If ( $Left -eq $Right )
{
$EqulibriumIndex += $TestIndex
}
}
return $EqulibriumIndex
}
Get-EquilibriumIndex -7, 1, 5, 2, -4, 3, 0
- Output:
3 6
Prolog
equilibrium_index(List, Index) :-
append(Front, [_|Back], List),
sumlist(Front, Sum),
sumlist(Back, Sum),
length(Front, Len),
Index is Len.
Example:
?- equilibrium_index([-7, 1, 5, 2, -4, 3, 0], Index).
Index = 3 ;
Index = 6 ;
false.
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 j<i
LSum+Val(ProgramParameter(j))
ElseIf j>i
RSum+Val(ProgramParameter(j))
EndIf
Next j
If LSum=RSum: PrintN(Str(i)): EndIf
Next i
EndIf
- Output:
> 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.
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
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:
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
Shorter alternative:
def eqindexMultiPass(s):
return [i for i in xrange(len(s)) if sum(s[:i]) == sum(s[i+1:])]
print eqindexMultiPass([-7, 1, 5, 2, -4, 3, 0])
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.
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]
Tests
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))))
- 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]
In terms of itertools.accumulate
The left scan is efficiently derived by the accumulate function in the itertools module.
The right scan can be derived from the left as a map or equivalent list comprehension:
"""Equilibrium index"""
from itertools import (accumulate)
# equilibriumIndices :: [Num] -> [Int]
def equilibriumIndices(xs):
'''List indices at which the sum of values to the left
equals the sum of values to the right.
'''
def go(xs):
'''Left scan from accumulate,
right scan derived from left
'''
ls = list(accumulate(xs))
n = ls[-1]
return [
i for (i, (x, y)) in enumerate(zip(
ls,
[n] + [n - x for x in ls[0:-1]]
)) if x == y
]
return go(xs) if xs else []
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''Tabulated test results'''
print(
tabulated('Equilibrium indices:\n')(
equilibriumIndices
)([
[-7, 1, 5, 2, -4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1, -1, 1, -1, 1, -1, 1],
[1],
[]
])
)
# ----------------------- GENERIC ------------------------
# tabulated :: String -> (a -> b) -> [a] -> String
def tabulated(s):
'''heading -> function -> input List
-> tabulated output string
'''
def go(f):
def width(x):
return len(str(x))
def cols(xs):
w = width(max(xs, key=width))
return s + '\n' + '\n'.join([
str(x).rjust(w, ' ') + ' -> ' + str(f(x))
for x in xs
])
return cols
return go
if __name__ == '__main__':
main()
- Output:
Equilibrium indices: [-7, 1, 5, 2, -4, 3, 0] -> [3, 6] [2, 4, 6] -> [] [2, 9, 2] -> [1] [1, -1, 1, -1, 1, -1, 1] -> [0, 1, 2, 3, 4, 5, 6] [1] -> [0] [] -> []
Quackery
[ dip [ [] [] 0 ]
witheach
[ + dup dip join ]
over [] swap
witheach
[ dip over - join ]
join
-1 split drop
witheach
[ over i^ peek = if
[ dip [ i^ join ] ] ]
drop ] is equilibria ( [ --> [ )
' [ -7 1 5 2 -4 3 0 ] equilibria echo
- Output:
[ 3 6 ]
Racket
#lang racket
(define (subsums xs)
(for/fold ([sums '()] [sum 0]) ([x xs])
(values (cons (+ x sum) sums)
(+ x sum))))
(define (equivilibrium xs)
(define-values (sums total) (subsums xs))
(for/list ([sum (reverse sums)]
[x xs]
[i (in-naturals)]
#:when (= (- sum x) (- total sum)))
i))
(equivilibrium '(-7 1 5 2 -4 3 0))
- Output:
'(3 6)
Raku
(formerly Perl 6)
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).grep(/\d/);
And here's an FP solution that manages to remain O(n):
sub equilibrium_index(@list) {
my @a = [\+] @list;
my @b = reverse [\+] reverse @list;
^@list Zxx (@a »==« @b);
}
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.
# 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
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:
{
-7 => [ 0, 2 ],
-13 => [ 1 ],
0 => [ 3, 6 ],
-2 => [ 4 ],
-3 => [ 5 ],
}
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.
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
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.
Red
Red []
eqindex: func [a [block!]] [
collect [
repeat ind length? a [ if (sum skip a ind) = sum copy/part a ind - 1 [ keep ind ] ]
]
]
prin "(1 based) equ indices are: "
probe eqindex [-7 1 5 2 -4 3 0]
- Output:
(1 based) equ indices are: [4 7]
ReScript
let arr = [-7, 1, 5, 2, -4, 3, 0]
let sum = Js.Array2.reduce(arr, \"+", 0)
let len = Js.Array.length(arr)
let rec aux = (acc, i, left, right) => {
if (i >= len) { acc } else {
let x = arr[i]
let right = right - x
if (left == right) {
let _ = Js.Array2.push(acc, i)
}
aux(acc, i+1, (left + x), right)
}
}
let res = aux([], 0, 0, sum)
Js.log("Results:")
Js.Array2.forEach(res, Js.log)
REXX
version 1
This REXX version utilizes a zero-based stemmed array to mimic the illustrative example in this Rosetta Code task's
prologue, which uses a zero-based index.
/*REXX program calculates and displays the equilibrium index for a numeric array (list).*/
parse arg x /*obtain the optional arguments from CL*/
if x='' then x= copies(" 7 -7", 50) 7 /*Not specified? Then use the default.*/
say ' array list: ' space(x) /*echo the array list to the terminal. */
#= words(x) /*the number of elements in the X list.*/
do j=0 for #; @.j= word(x, j+1) /*zero─start is for zero─based array. */
end /*j*/ /* [↑] assign @.0 @.1 @.3 ··· */
say /* ··· and also display a blank line. */
answer= equilibriumIDX(); w= words(answer) /*calculate the equilibrium index. */
say 'equilibrium' word("(none) index: indices:", 1 + (w>0) + (w>1)) answer
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
equilibriumIDX: $=; do i=0 for #; sum= 0
do k=0 for #; sum= sum + @.k * sign(k-i); end /*k*/
if sum==0 then $= $ i
end /*i*/ /* [↑] Zero? Found an equilibrium index*/
return $ /*return equilibrium list (may be null)*/
- output when using the input of: -7 1 5 2 -4 3 0
array list: -7 1 5 2 -4 3 0 equilibrium indices: 3 6
- output when using the input of: 2 9 2
array list: 2 9 2 equilibrium index: 1
- output when using the input of: 5 4 4 5
array list: 5 4 4 5 equilibrium (none)
- output when using the default input
array list: 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 -7 7 equilibrium indices: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
version 2
/* REXX ---------------------------------------------------------------
* 30.06.2014 Walter Pachl
*--------------------------------------------------------------------*/
parse arg l
say ' array list:' strip(l)
x.=0
Do i=1 To words(l)
x.i=word(l,i)
End
n=i-1
ans=strip(equilibriumIndices())
n=words(ans)
Select
When n=0 Then Say 'There''s no equilibrium index'
When n=1 Then Say 'equilibrium index :' ans
Otherwise Say 'equilibrium indices:' ans
End
Say '---'
exit
equilibriumIndices: procedure expose x. n
sum.=0
sum=0
eil=''
Do i=1 To n
sum=sum+x.i
sum.i=sum
End
Do i=1 To n
im1=i-1
If sum.im1=(sum.n-x.i)/2 Then
eil=eil im1
End
Return eil
output
array list: -7 1 5 2 -4 3 0 equilibrium indices: 3 6 --- array list: 2 9 2 equilibrium index : 1 --- array list: 1 -1 1 -1 1 -1 1 equilibrium indices: 0 1 2 3 4 5 6 --- array list: 1 1 There's no equilibrium index ---
Ring
list = [-7, 1, 5, 2, -4, 3, 0]
see "equilibrium indices are : " + equilibrium(list) + nl
func equilibrium l
r = 0 s = 0 e = ""
for n = 1 to len(l)
s += l[n]
next
for i = 1 to len(l)
if r = s - r - l[i] e += string(i-1) + "," ok
r += l[i]
next
e = left(e,len(e)-1)
return e
Output:
equilibrium indices are : 3,6
RPL
RPL code | Comment |
---|---|
≪ 0 SWAP + → seq ≪ { } 0 seq ∑LIST 2 seq SIZE FOR j seq j GET - SWAP seq j 1 - GET + SWAP IF DUP2 == THEN ROT j 2 - + ROT ROT END NEXT DROP2 ≫ ≫ ‘EQIDX’ STO |
EQIDX ( { A0..An } -- { equilibrium index } ) add zero at list head to avoid GET error at first loop left = 0 ; right = A0+A1+...An loop from j=2 to length(seq) e.g. A0 to An right -= seq[j] ; left += A[j-1] if left = right then append j-2 to index list drop left and right return list |
{ -7 1 5 2 -4 3 0 } EQIDX
- Output:
1: { 3 6 }
Ruby
- Functional Style
def eq_indices(list)
list.each_index.select do |i|
list[0...i].sum == list[i+1..-1].sum
end
end
- Tail Recursion
- This one would be good if Ruby did tail-call optimization (TCO).
- MRI does not do TCO; so this function fails with a long list (by overflowing the call stack).
def eq_indices(list)
result = []
list.empty? and return result
final = list.size - 1
helper = lambda do |left, current, right, index|
left == right and result << index # Push index to result?
index == final and return # Terminate recursion?
new = list[index + 1]
helper.call(left + current, new, right - new, index + 1)
end
helper.call 0, list.first, list.drop(1).sum, 0
result
end
- Imperative Style (faster)
def eq_indices(list)
left, right = 0, list.sum
equilibrium_indices = []
list.each_with_index do |val, i|
right -= val
equilibrium_indices << i if right == left
left += val
end
equilibrium_indices
end
- Test
indices = [
[-7, 1, 5, 2,-4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1,-1, 1,-1, 1,-1, 1]
]
indices.each do |x|
puts "%p => %p" % [x, eq_indices(x)]
end
- Output:
[-7, 1, 5, 2, -4, 3, 0] => [3, 6] [2, 4, 6] => [] [2, 9, 2] => [1] [1, -1, 1, -1, 1, -1, 1] => [0, 1, 2, 3, 4, 5, 6]
Rust
extern crate num;
use num::traits::Zero;
fn equilibrium_indices(v: &[i32]) -> Vec<usize> {
let mut right = v.iter().sum();
let mut left = i32::zero();
v.iter().enumerate().fold(vec![], |mut out, (i, &el)| {
right -= el;
if left == right {
out.push(i);
}
left += el;
out
})
}
fn main() {
let v = [-7i32, 1, 5, 2, -4, 3, 0];
let indices = equilibrium_indices(&v);
println!("Equilibrium indices for {:?} are: {:?}", v, indices);
}
- Output:
Equilibrium indices for [-7, 1, 5, 2, -4, 3, 0] are: [3, 6]
Scala
def getEquilibriumIndex(A: Array[Int]): Int = {
val bigA: Array[BigInt] = A.map(BigInt(_))
val partialSums: Array[BigInt] = bigA.scanLeft(BigInt(0))(_+_).tail
def lSum(i: Int): BigInt = if (i == 0) 0 else partialSums(i - 1)
def rSum(i: Int): BigInt = partialSums.last - partialSums(i)
def isRandLSumEqual(i: Int): Boolean = lSum(i) == rSum(i)
(0 until partialSums.length).find(isRandLSumEqual).getOrElse(-1)
}
Seed7
$ include "seed7_05.s7i";
const array integer: numList is [] (-7, 1, 5, 2, -4, 3, 0);
const func array integer: equilibriumIndex (in array integer: elements) is func
result
var array integer: indexList is 0 times 0;
local
var integer: element is 0;
var integer: index is 0;
var integer: sum is 0;
var integer: subSum is 0;
var integer: count is 0;
begin
indexList := length(elements) times 0;
for element range elements do
sum +:= element;
end for;
for element key index range elements do
if 2 * subSum + element = sum then
incr(count);
indexList[count] := index;
end if;
subSum +:= element;
end for;
indexList := indexList[.. count];
end func;
const proc: main is func
local
var array integer: indexList is 0 times 0;
var integer: element is 0;
begin
indexList := equilibriumIndex(numList);
write("Found:");
for element range indexList do
write(" " <& element);
end for;
writeln;
end func;
- Output:
Found: 4 7
Sidef
func eq_index(nums) {
var (i, sum, sums) = (0, 0, Hash.new);
nums.each { |n|
sums{2*sum + n} := [] -> append(i++);
sum += n;
}
sums{sum} \\ [];
}
Test:
var indices = [
[-7, 1, 5, 2,-4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1,-1, 1,-1, 1,-1, 1],
]
for x in indices {
say ("%s => %s" % @|[x, eq_index(x)].map{.dump});
}
- Output:
[-7, 1, 5, 2, -4, 3, 0] => [3, 6] [2, 4, 6] => [] [2, 9, 2] => [1] [1, -1, 1, -1, 1, -1, 1] => [0, 1, 2, 3, 4, 5, 6]
Swift
extension Collection where Element: Numeric {
func equilibriumIndexes() -> [Index] {
guard !isEmpty else {
return []
}
let sumAll = reduce(0, +)
var ret = [Index]()
var sumLeft: Element = 0
var sumRight: Element
for i in indices {
sumRight = sumAll - sumLeft - self[i]
if sumLeft == sumRight {
ret.append(i)
}
sumLeft += self[i]
}
return ret
}
}
let arr = [-7, 1, 5, 2, -4, 3, 0]
print("Equilibrium indexes of \(arr): \(arr.equilibriumIndexes())")
- Output:
Equilibrium indexes of [-7, 1, 5, 2, -4, 3, 0]: [3, 6]
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
}
- Example of use
set testData {-7 1 5 2 -4 3 0}
puts Equilibria=[join [listEquilibria $testData] ", "]
- Output:
Equilibria=3, 6
Ursala
#import std
#import int
edex = num@yK33ySPtK33xtS2px; ~&nS+ *~ ==+ ~~r sum:-0
#cast %nL
example = edex <-7,1,5,2,-4,3,0>
- Output:
<3,6>
VBScript
Solution adopted from http://www.geeksforgeeks.org/equilibrium-index-of-an-array/ .
arr = Array(-7,1,5,2,-4,3,0)
WScript.StdOut.Write equilibrium(arr,UBound(arr))
WScript.StdOut.WriteLine
Function equilibrium(arr,n)
sum = 0
leftsum = 0
'find the sum of the whole array
For i = 0 To UBound(arr)
sum = sum + arr(i)
Next
For i = 0 To UBound(arr)
sum = sum - arr(i)
If leftsum = sum Then
equilibrium = equilibrium & i & ", "
End If
leftsum = leftsum + arr(i)
Next
End Function
- Output:
Indices: 3, 6,
Wren
import "./fmt" for Fmt
var equilibrium = Fn.new { |a|
var len = a.count
var equi = []
if (len == 0) return equi // sequence has no indices at all
var rsum = a.reduce { |acc, x| acc + x }
var lsum = 0
for (i in 0...len) {
rsum = rsum - a[i]
if (rsum == lsum) equi.add(i)
lsum = lsum + a[i]
}
return equi
}
var tests = [
[-7, 1, 5, 2, -4, 3, 0],
[2, 4, 6],
[2, 9, 2],
[1, -1, 1, -1, 1, -1, 1],
[1],
[]
]
System.print("The equilibrium indices for the following sequences are:\n")
for (test in tests) {
Fmt.print("$24n -> $n", test, equilibrium.call(test))
}
- Output:
The equilibrium indices for the following sequences are: [-7, 1, 5, 2, -4, 3, 0] -> [3, 6] [2, 4, 6] -> [] [2, 9, 2] -> [1] [1, -1, 1, -1, 1, -1, 1] -> [0, 1, 2, 3, 4, 5, 6] [1] -> [0] [] -> []
XPL0
code Ran=1, ChOut=8, IntOut=11;
def Size = 1_000_000;
int I, S, A(Size), Hi(Size), Lo(Size);
[for I:= 0 to Size-1 do A(I):= Ran(100) - 50;
S:= 0;
for I:= 0 to Size-1 do [S:= S+A(I); Lo(I):= S];
S:= 0;
for I:= Size-1 downto 0 do [S:= S+A(I); Hi(I):= S];
for I:= 0 to Size-1 do
if Lo(I) = Hi(I) then [IntOut(0, I); ChOut(0, ^ )];
]
- Output:
502910 504929 508168
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.
func equilibrium_indices(A) {
return where(A(psum) == A(::-1)(psum)(::-1));
}
- Example interactive usage:
> equilibrium_indices([-7, 1, 5, 2, -4, 3, 0]) [4,7]
zkl
fcn equilibrium(lst){ // two pass
reg acc=List(), left=0,right=lst.sum(0),i=0;
foreach x in (lst){
right-=x;
if(left==right) acc.write(i);
i+=1; left+=x;
}
acc
}
fcn equilibrium(lst){ // lst should immutable, n^2
(0).filter(lst.len(),'wrap(n){ lst[0,n].sum(0) == lst[n+1,*].sum(0) })
}
If the input list is immutable, no new lists are generated (other than accumulating the result).
equilibrium(T(-7, 1, 5, 2, -4, 3, 0)).println();
- Output:
L(3,6)
ZX Spectrum Basic
10 DATA 7,-7,1,5,2,-4,3,0
20 READ n
30 DIM a(n): LET sum=0: LET leftsum=0: LET s$=""
40 FOR i=1 TO n: READ a(i): LET sum=sum+a(i): NEXT i
50 FOR i=1 TO n
60 LET sum=sum-a(i)
70 IF leftsum=sum THEN LET s$=s$+STR$ i+" "
80 LET leftsum=leftsum+a(i)
90 NEXT i
100 PRINT "Numbers: ";
110 FOR i=1 TO n: PRINT a(i);" ";: NEXT i
120 PRINT '"Indices: ";s$
- Programming Tasks
- Solutions by Programming Task
- 11l
- ABAP
- Action!
- Ada
- Aime
- ALGOL 68
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BASIC256
- Batch File
- BBC BASIC
- C
- C sharp
- C++
- Clojure
- Common Lisp
- D
- Delphi
- EasyLang
- Elena
- Elixir
- ERRE
- Euphoria
- Factor
- Fortran
- FreeBASIC
- Fōrmulæ
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- Liberty BASIC
- Logo
- Lua
- Mathematica
- Wolfram Language
- MATLAB
- NetRexx
- Nim
- Objeck
- OCaml
- Oforth
- PARI/GP
- Pascal
- Perl
- Phix
- PHP
- Picat
- PicoLisp
- PowerShell
- Prolog
- PureBasic
- Python
- Quackery
- Racket
- Raku
- Red
- ReScript
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Seed7
- Sidef
- Swift
- Tcl
- Ursala
- VBScript
- Wren
- Wren-fmt
- XPL0
- Yorick
- Zkl
- ZX Spectrum Basic