Jump to content

Equilibrium index: Difference between revisions

Equilibrium index (view source)

Revision as of 05:15, 29 October 2022

501 bytes removed ,  1 year ago
→‎{{header|jq}}: use foreach; now also works with jaq
(→‎{{header|jq}}: use foreach; now also works with jaq)
Line 1,518:
 
=={{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.
 
The top-level function`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]
| if 0 == $add - .[0] asthen $i0 else empty end,
foreach range(1;length) as $i (
| if $i == mx then empty # all done
[0, .[0], else$add - .[10]]; as $h# [before, pivot, after]
$in[$i] as $x | ([.[20]+.[1], -$x, a.[$i2]) as- $tx];
| (if $h.[0] == $t.[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>
Peak
2,467

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/332828"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information