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

## Leave a comment