Equilibrium index
And here's an FP solution that manages to remain O(n):
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.
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:
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.
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.
Last updated