RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved English word lengths and array partitioning. (Note that this is open until 17 April 2022.)

Task 1: Four Is Magic Submitted by: Mohammad S Anwar

You are given a positive number, $n < 10.

Write a script to generate english text sequence starting with the English cardinal representation of the given number, the word 'is' and then the English cardinal representation of the count of characters that made up the first word, followed by a comma. Continue until you reach four.

We haven't had string handling in these things for a while - though it turns out to be relatively easy to do even in the languages that are new to me. (My PostScript library set has grown some new functions.) This is probably a relatively ugly way to do it, but it works.

Here's the Perl – which still does a good job of making string handling easy even though I miss the features of later languages.

sub fim {
  my $n=shift;

Establish the lookup table.

  my @words=qw(zero one two three four five six seven eight nine);
  my @p;
  while (1) {

Each phrase starts the same way.

    my $s=$words[$n] . ' is ';

The final phrase ends differently, and leaves the loop.

    if ($n == 4) {
      $s .= 'magic.';
      push @p,$s;
      last;

Otherwise, do it the standard way.

    } else {
      $n=length($words[$n]);
      $s .= $words[$n];
      push @p,$s;
    }
  }

Join all the phrases for the result.

  return ucfirst(join(', ',@p));
}

Task 2: Equilibrium Index

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].

I found a pleasing approach to this. First get the sum of the whole series. Then for each index calculate a partial sums: twice the sum of all previous values, plus this value. At the equilibrium index, this will equal the total. (If the values were guaranteed to be non-negative, you could bail out if this value got higher than the whole-series sum, but the problem specification does not make this guarantee.)

Rust:

fn equilibriumindex(s: Vec<isize>) -> isize {

Sum of the series. (In Rust, a reference to satisfy the borrow checker.)

    let sm=&s.iter().sum::<isize>();

Start the partial sums.

    let mut sa=0;
    for (i,v) in s.iter().enumerate() {
        sa += v;

Partial sum is now (twice all previous entries) plus (this entry).

        if sa == *sm {
            return i as isize;
        }
        sa += v;

Partial sum is now (twice all entries) ready for the next entry.

    }

If we didn't bail out early, there's no solution.

    -1
}

So in the case of [1,3,5,7,9]:

• Sum of series (sm) is 25
• Accumulator (sa) starts at 0
• index 0, value 1, sa becomes 1; not equal to 25; sa becomes 2.
• index 1, value 3, sa becomes 5; not equal to 25; sa becomes 8.
• index 2, value 5, sa becomes 13; not equal to 25; sa becomes 18.
• index 3, value 7, sa becomes 25; equal to 25. Return index 3.

Full code on github.