Equilibrium index: Difference between revisions

Line 1,518:

=={{header|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.

~~The top-level function~~ is defined as a 0-arity filter that emits answers as a stream, as is idiomatic in jq.

<syntaxhighlight lang="jq"># The index origin is 0 in jq.

def equilibrium_indices:

. as $in

def indices(a; mx):

| add as $add

def report: # [i, headsum, tailsum]

.[0] as $i

| if 0 == $add - .[0] then 0 else empty end,

foreach range(1;length) as $i (

| if $i == mx then empty # all done

~~else~~ .[1] as $h

[0, .[0], $add - .[0]]; # [before, pivot, after]

| (.[2] - a[$i]) as $t

$in[$i] as $x | [.[0]+.[1], $x, .[2] - $x];

~~| (~~if $h == $t then $i else empty end),

if .[0] == .[2] then $i else empty end) ;

</syntaxhighlight>

( [ $i + 1, $h + a[$i], $t ] | report )

end;

[0, 0, (a|add)] | report;

. as $in | indices($in; $in|length);</syntaxhighlight>

'''Example 1:'''

<syntaxhighlight lang="jq">[-7, 1, 5, 2, -4, 3, 0] | equilibrium_indices</syntaxhighlight>