laurent_r

These are some answers to the Week 221, task 2, 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 June 18, 2023 at 23:59). This blog post offers some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Arithmetic Subsequence

You are given an array of integers, @ints.

Write a script to find the length of the longest Arithmetic Subsequence in the given array.

A subsequence is an array that can be derived from another array by deleting some or none elements without changing the order of the remaining elements.

A subsequence is arithmetic if ints[i + 1] - ints[i] are all the same value (for 0 <= i < ints.length - 1).

Example 1:

Input: @ints = (9, 4, 7, 2, 10)
Output: 3

The longest Arithmetic Subsequence (4, 7, 10) can be derived by deleting 9 and 2.

Example 2:

Input: @ints = (3, 6, 9, 12)
Output: 4

No need to remove any elements, it is already an Arithmetic Subsequence.

Example 3:

Input: @ints = (20, 1, 15, 3, 10, 5, 8)
Output: 4

The longest Arithmetic Subsequence (20, 15, 10, 5) can be derived by deleting 1, 3 and 8.

Arithmetic Subsequence in Raku

The longest-subseq subroutine first collects all combinations of items (@pairs) from the input and then populates the %gaps histogram of differences between pairs elements, and then returns the most frequent gap (+ 1, as for n gaps, we have n+1 items).

sub longest-subseq (@in) {
    my @pairs = @in.combinations: 2;
    my %gaps;
    %gaps{~($_[1] - $_[0])}++ for @pairs;
    # For n gaps, we have n + 1 values
    return %gaps.values.max + 1;
}

for <9 4 7 2 10>, <3 6 9 12>, <20 1 15 3 10 5 8> -> @test {
    printf "%-18s => %d\n", ~(@test), longest-subseq @test;
}

This program displays the following output:

9 4 7 2 10         => 3
3 6 9 12           => 4
20 1 15 3 10 5 8   => 4

Arithmetic Subsequence in Perl

This is essentially a port to Perl of the Raku program above. The call to the combinations method is replaced by a nested for loop over the input array, and we need also an additional for loop to find the gap with the highest frequency. The longest_subseq subroutine first collects all combinations of items (@pairs) from the input and then populates the %gaps histogram of differences between pairs elements, and then returns the most frequent gap (+ 1, as for n gaps, we have n+1 items).

use strict;
use warnings;
use feature 'say';

sub longest_subseq {
    my @pairs;
    for my $i (0..$#_) {
        for my $j ($i+1..$#_) {
            push @pairs, [$_[$i], $_[$j]];
        }
    }
    my %gaps;
    $gaps{($_->[1] - $_->[0])}++ for @pairs;
    my $max = 0;
    for my $k (keys %gaps) {
        $max = $gaps{$k} if $gaps{$k} > $max;
    }
    # For n gaps, we have n + 1 values
    return $max + 1;
}

for my $test ( [<9 4 7 2 10>], [<3 6 9 12>], [<20 1 15 3 10 5 8>] ) {
    printf "%-18s => ", "@$test";
    say longest_subseq @$test;
}

This program displays the following output:

9 4 7 2 10         => 3
3 6 9 12           => 4
20 1 15 3 10 5 8   => 4

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 June 25, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.