All Things in Balance

Wherein the yin meets the yang, and with the heat of the meat — and the mass of the ass — the shade of the toothpick meets the hot burning sun…

THE WEEKLY CHALLENGE – PERL & RAKU #160 Task 2

---

“Life is like riding a bicycle. To keep your balance, you must keep moving.“

— Albert Einstein

---

Equilibrium Index

Submitted by: Mohammad S Anwar

You are give an array of integers, @n.

Write a script to find out the Equilibrium Index of the given array, if found.

For an array A consisting n elements, index i is an equilibrium index if the sum of elements of subarray A[0…i-1] is equal to the sum of elements of subarray A[i+1…n-1].

Example 1:

Input: @n = (1, 3, 5, 7, 9)
Output: 3

Example 2:

Input: @n = (1, 2, 3, 4, 5)
Output: -1 as no Equilibrium Index found.

Example 3:

Input: @n = (2, 4, 2)
Output: 1

ANALYSIS

The word “equilibrium” to me means a dynamic system where multiple forces act on a state to alter it in one direction or another, yet taken together work to cancel each other out, achieving a balanced stasis. An equilibrium is a middle-ground by definition, and so cannot be an extreme. It parks itself between extremes. If the stable state lands at an extreme, then that force dominates the system, rendering others inconsequential, and the word does not apply.

This internal rebalancing suggests in turn a dynamic algorithm, homing in on a result, oscillating within a narrowing field until a final central compromise is achieved.

That would be one way to do it. On the other hand we could also process the data list-wise in a single expression: working left to right across the indices we sum the two non-inclusive lists of elements on the left and right and compare the two values, noting the first index where we find the halves to be equal.

That would be a more direct way.

Are there others? Sure. Let’s look to an equilibrated solution and see what it tells us.

In an equilibrium state, as defined, the two sub-lists to either side of a pivot point sum to the same value. Which means the sum of the entire list is equal to 2× the sum of either outside list plus the pivot value. Well, we could first make a pass and sum the list elements, then walk it upwards from index 1, all the while keeping a running total of all those elements seen previously to the element being examined. For each position this sum is doubled, the element value added, and compared to the pre-calculated total sum. If they match we have found the equilibrium index.

This is a good plan, as we aren’t continuously re-summing the varying side-lists for every index. However it still does require two traversals. Can we do it in one? Of course we can.

That solution is to walk the list, and at each element compute the total of twice the sum of the previously seen left-hand list and the value of the element, then store this number in a hash associated with the value of the index that created it. Then, by the time we get to the last element we will have all the information required to compute the total sum. We then look up the hash key with the sum and it will point to the equilibrium index.

Clever, you might say, and I might modestly answer yes I thought so. But what if the keys weren’t unique? Can a list have two equilibrium points? If we only allow for positive values it can’t, but if we admit negative values, and zeros, to the party — which aren’t explicitly excluded in the description — then we can construct multi-stable lists. The list

(5, -5, 0, 5, 0)

for example has equilibria at indices [1] and [3].

The list

(5, -5, 0, 5, 0, -5, 5)

similarly has stable centers at [1], [3], and [5]. The patterns can be generalized as any individual 0 can be replaced with a multi-member sub-list that itself sums to 0.

The exhaustive solution finds the first solution found, and in our single-pass solution we will overwrite any key value that is repeated with new data, so it will find the last instance. It’s not at all clear what we should do in those cases, and the correct implementation would really depend on the application. We could use a more complex data structure, keeping all matches in a list that is later reported, without too much difficulty. All-in all I kind of view this possibility of multiple equilibrium as somewhat pathological fringe cases, as they require careful construction to achieve. One equilibrium, I think, should be enough for anybody. The world is not a flat line of 0s, calm and uneventful.

Like, ever. It just doesn’t work that way.

METHOD

PERL 5 SOLUTION

In Perl we create two subroutines, for the two ways of processing outlined above. In eq_direct() we process the data one position at time, summing the side-lists as array slices until they are equal to each other.

In the second method, eq_linear(), we create a value for each position equal to twice the left-hand list plus the position itself. Were this to be the equilibrium point then this would in turn equal the sum of the entire list. So we save this sum as a hash key, pointing to the position that produced it.

We only process the central portion of the array, under the theory that the start and end cannot be equilibrium points as the term has no meaning at those extremes. By the time we get to the last position checked, we then add the end of the array to the running sum tally to get the sum of the entire array. Once we have that, we can consult the hash to find the position, if any, that sums to that total.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use List::Util qw( first sum );

sub eq_direct {
## exhaustive traversal, re-summing side-lists
    return (first { sum(@_[0..$_-1]) == sum(@_[$_+1..$#_]) } (1..$#_-1)) // -1;
} ;

sub eq_linear (@list) {
## single-pass continuous summing with lookup
    my %sums;
    my $total = $list[0];
    for (1..$#list-1) {
        $sums{ 2 * $total + $list[$_] } = $_;
        $total += $list[$_];
    }
    $total += $list[-1];
    return $sums{$total} // -1
}

Raku Solution

In Raku we can create the exhaustive solution in a functional style, processing a sub-list of index positions to scan, summing the left and right side slices as in the Perl solution. The linear version also takes advantage of some list-wise methods that are available: head and end. Other than that it flows in much the same way as above.

unit sub MAIN () ;


sub eq_direct (@list) {
## exhaustive traversal, re-summing side-lists
    @list.keys[1..@list.end-1].first( 
        { @list[$_+1..@list.end].sum == @list[0..$_-1].sum }
        ) // -1
} ;

sub eq_linear (@list) {
## single-pass continuous summing with lookup
    my %sums;
    my $total = @list.head;
    for (1..@list.end-1) {
        %sums{ 2 * $total + @list[$_] } = $_;
        $total += @list[$_];
    }
    $total += @list[*-1];
    return %sums{$total} // -1
}