laurent_r

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.