## Perl Weekly Challenge 291: Middle Index

These are some answers to the Week 291, Task 1, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

*Spoiler Alert:* This weekly challenge deadline is due in a few days from now (on October 20, 2024, at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

## Task 1: Middle Index

*You are given an array of integers, @ints.*

*Write a script to find the leftmost middle index (MI) i.e. the smallest amongst all the possible ones.*

A middle index is an index where`ints[0] + ints[1] + … + ints[MI-1] == ints[MI+1] + ints[MI+2] + … + ints[ints.length-1]`

.

*If MI == 0, the left side sum is considered to be 0. Similarly, if MI == ints.length - 1, the right side sum is considered to be 0.*

*Return the leftmost MI that satisfies the condition, or -1 if there is no such index.*

*Example 1*

```
Input: @ints = (2, 3, -1, 8, 4)`
Output: 3
The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4
```

*Example 2*

```
Input: @ints = (1, -1, 4)
Output: 2
The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0
```

*Example 3*

```
Input: @ints = (2, 5)
Output: -1
There is no valid MI.
```

I first thought of starting from both ends of the array and working inwards progressively to try to find "the man in the middle", something similar to what is done in a bisection algorithm. But that doesn't work because the input values are not sorted, or, at least, it would lead to too many complicated and time-consuming edge cases.

So we decided to use a "brute force" approach, i.e. we try every possible index from 0 to the last (from left to right) and check if it is a middle index. And we stop as soon as we find one.

### Middle Index in Raku

We loop over the input array indexes and check and check whether the index qualifies as a middle index. Note that, for the sake of simplicity, the program doesn't check whether:

ints[0] + ints[1] + … + ints[MI-1] == ints[MI+1] + ints[MI+2] + … + ints[ints.length-1]

but rather whether:

ints[0] + ints[1] + … + ints[MI] == ints[MI] + ints[MI+2] + … + ints[ints.length-1],

which is equivalent and slightly simpler.

```
sub middle-index (@in) {
return $_ if @in[0..$_].sum == @in[$_..@in.end].sum
for 0..@in.end;
return -1;
}
my @tests = (2, 3, -1, 8, 4), (1, -1, 4), (2, 5);
for @tests -> @test {
printf "%-12s => ", "@test[]";
say middle-index @test;
}
```

This program displays the following output:

```
$ raku ./middle-index.raku
2 3 -1 8 4 => 3
1 -1 4 => 2
2 5 => -1
```

### Middle Index in Perl

This is a port to Perl of the above Raku program. Please refer to the above two sections if you need further explanations. The only significant change is that I had to implement a `sum`

subroutine since it is not natively built in Perl (although I admit there are some modules doing that, but I consider that using off-the-shelf modules is not proper conduct in a coding challenge).

```
use strict;
use warnings;
use feature 'say';
sub sum {
my $sum = 0;
$sum += $_ for @_;
return $sum;
}
sub middle_index {
for my $i (0..$#_) {
return $i if sum(@_[0..$i]) == sum(@_[$i..$#_]);
}
return -1;
}
my @tests = ( [2, 3, -1, 8, 4], [1, -1, 4], [2, 5]);
for my $test (@tests) {
printf "%-12s => ", "@$test";
say middle_index @$test;
}
```

This program displays the following output:

```
$ perl ./middle-index.pl
2 3 -1 8 4 => 3
1 -1 4 => 2
2 5 => -1
```

## Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on October 27, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.

## Leave a comment