## The Problem Description

A zero-indexed array

Aconsisting ofNintegers is given. An

equilibrium indexof this array is any integerPsuch that 0 <=

P<Nand the sum of elements of lower indices is equal to the sum

of elements of higher indices, i.e.,A[0] + A[1] + ... + A[P-1] = A[P+1] + ... + A[N-2] + A[N-1].The sum of zero elements is assumed to be equal to 0.

Write a function that, given a zero-indexed array

Aconsisting of

Nintegers, returns any of its equilibrium indices. The function

should return -1 if no equilibrium index exists.

- Expected worst-case time complexity is O(N)
- Expected worst-case space complexity is O(N), beyond input storage
(not counting the storage required for input arguments).

The above is taken from the problem description by Codility; they discuss one solution (written in C) here.

## Notes on this Implementation

First things first: we’ll avoid the `return -1`

“C-ism,” as it’s more natural to return `nil`

in Ruby. In fact, Ruby sees -1 as `True`

, so returning it will break many common predicates, whereas `nil`

won’t.

Experienced programmers will observe that this implementation does not meet the `O(n)`

time and space complexity requirements as listed above. Absolute simplicity of implementation is the focus right now, but that may change in a future version.

Finally, notice that this short essay is itself a literate program, implemented using the wonderful Org-mode capabilities which are included with the Emacs text editor.

## The Inner Loop

Since most of the program’s work is done inside a single `while`

loop, we’ll begin there.

Let *A* be the Ruby array

[-7, 1, 5, 2, -4, 3, 0].

The equilibrium index of *A* can be computed by hand, so it’s a good place to start. It’s also our first test case (see below).

We’ve chosen to implement the iteration over *A* using a `while`

loop rather than the more idiomatic `Array#each`

method since we need to keep track of our current index into the array.

As we begin the loop, the variable `index`

is initialized as the length of the array minus one. This is required because Ruby’s arrays are zero-based, but the value returned by its `Array#length`

method is not.

while index > 0 left = a[0..index-1].reduce(:+) right = a[index+1..len].reduce(:+) if left == right return index end index -= 1 end

We’ll iterate backwards through the array from the end. At each value of `index`

, we’ll split *A* into two smaller arrays, `left`

and `right`

. This requires allocating two new arrays in memory, reading the values of the desired “slices” of *A*, and copying them into `left`

and `right`

, respectively. This operation provides for an implementation that is simple to visualize and understand, but it’s also the reason why we fail to meet the requirements for `O(n)`

space and time complexity. A more efficient implementation would avoid these unnecessary allocation and copying steps, and we might change this program at some point to achieve that.

## Visualizing the Iteration

Let’s look at `left`

and `right`

at each stage of the iteration:

We can see that when we split *A* at `index`

, we always leave a “gap” in between, and it’s this gap which will provide us with the answer we seek: the equilibrium index (provided that the equilibrium index is defined for the given array, that is). At every iteration in the diagram above, we sum the values within `left`

and `right`

using the `Array#reduce`

method. If `left`

and `right`

are equal, `index`

is defined as the equilibrium index, and we `return index`

. Otherwise, we’ll end up escaping the loop and returning `nil`

.

## The `equi`

Function

Looking briefly at the entire `equi`

function, we can see that it’s just a wrapper for the `while`

loop. First we set the value of `index`

and `len`

as bookkeeping measures. We then enter the `while`

loop as described above. If the loop completes without returning a value, the program returns to the next outer context and returns the `nil`

value, which lets our caller know that this array doesn’t have an equilibrium index.

def equi(a) index = a.length-1 len = a.length-1 while index > 0 left = a[0..index-1].reduce(:+) right = a[index+1..len].reduce(:+) if left == right return index end index -= 1 end nil end

## Test Cases

Over the course of developing the program, a number of test cases have come to mind. We’ll begin with the given array *A* that we started with.

def test_random sample_array = [-7, 1, 5, 2, -4, 3, 0] expected = equi(sample_array) assert_equal expected, 3 end

Here we’ve defined a trivial `pyramid’ array of values that ascend and descend symmetrically.

def test_trivial_pyramid sample_array = [1, 2, 3, 4, 3, 2, 1] expected = equi(sample_array) assert_equal expected, 3 end

This test checks the case where the first value is equal to the sum of all the rest (save the equilibrium index, of course).

def test_biggest_first sample_array = [99, 0, 66, 32, 1] expected = equi(sample_array) assert_equal expected, 1 end

Similarly, we check for the case where the last value alone is equal to the sum of `left`

.

def test_biggest_last sample_array = [66, 32, 1, 0, 99] expected = equi(sample_array) assert_equal expected, 3 end

We should return `nil`

for an array with a single element, since the equilibrium index is not defined in that case.

def test_single_element sample_array = [0] expected = equi(sample_array) assert_equal expected, nil end

The same is true of an array containing a single `nil`

.

def test_single_nil sample_array = [nil] expected = equi(sample_array) assert_equal expected, nil end

## The Complete Program Listing

Finally, we have the complete program listing for the `tangle`

‘d file `literate-equi.rb`

. Since we’ve included our tests by subclassing the `Test::Unit`

class, Ruby will run them for us when we invoke the program. Running `ruby literate-equi.rb`

at the command shell should return the following output:

~/Desktop/Dropbox/current/logicgrimoire $ ruby literate-equi.rb Loaded suite literate-equi Started ...... Finished in 0.002195 seconds. 6 tests, 6 assertions, 0 failures, 0 errors

The program itself:

#!/usr/bin/env ruby require 'test/unit' def equi(a) index = a.length-1 len = a.length-1 while index > 0 left = a[0..index-1].reduce(:+) right = a[index+1..len].reduce(:+) if left == right return index end index -= 1 end nil end class TestEqui < Test::Unit::TestCase def test_random sample_array = [-7, 1, 5, 2, -4, 3, 0] expected = equi(sample_array) assert_equal expected, 3 end def test_trivial_pyramid sample_array = [1, 2, 3, 4, 3, 2, 1] expected = equi(sample_array) assert_equal expected, 3 end def test_biggest_first sample_array = [99, 0, 66, 32, 1] expected = equi(sample_array) assert_equal expected, 1 end def test_biggest_last sample_array = [66, 32, 1, 0, 99] expected = equi(sample_array) assert_equal expected, 3 end def test_single_element sample_array = [0] expected = equi(sample_array) assert_equal expected, nil end def test_single_nil sample_array = [nil] expected = equi(sample_array) assert_equal expected, nil end end