## Perl Weekly Challenge 221: Arithmetic Subsequence

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.