Good strings and hidden sequences

Weekly challenge 221 — 12 June 2023

Week 221 - 12 Jun 2023

Task 2

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 zero or more elements without changing the order of the remaining elements.

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

Let's look at the first two integers - say they are 3 and 7. They differ by 4, and any arithmetic subsequence (AS) starting with that pair must continue with 7 + 4 = 11, 11 + 4 = 15 and so on. (I have slighly narrowed Mohammad's definition by asserting that an AS must have at least 3 members.) So I can scan along @ints looking for 11, and then for 15 and so on.

So I need only to check every possible pair of starting values a and b, differing by d (= b - a), and see if b + d, b + 2d and so on exist further on in @ints. This works even if d or any of @ints is zero or negative.

Interestingly, by using this method I don't need to use recursion or engage in the potentially expensive action of deleting values from @ints, so this is very fast even with several hundred values in @ints.

#!/usr/bin/perl use v5.16; # The Weekly Challenge - 2023-06-12 use utf8; # Week 221 task 2 - Arithmetic subsequence use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge my ($j, @ints); arithmetic_subsequence(9, 4, 7, 2, 10, 12, 13); arithmetic_subsequence(2, 7, -1, 9, -4, 11, -7, 33, -10); arithmetic_subsequence(3, 3, 3); arithmetic_subsequence(1, 2, 4, 7, 11, 16); arithmetic_subsequence(2, 4, 6, 8, 21, 22, 23, 24); arithmetic_subsequence(1, 2, 7, 19, 44, 123); arithmetic_subsequence(1, 2); arithmetic_subsequence(1, 2, 'x'); # larger example for $j (0 .. 99) { push (@ints, int(rand(50))); } arithmetic_subsequence(@ints); sub arithmetic_subsequence { my (@ints, $best, $last, $first, $second, $next, $length, $target, $explain, $best_explain, $delta); # initialise @ints = @_; return unless validate(@ints); $best = 0; $last = scalar @ints - 1; # loop over all possible first and second members of a subsequence for $first (0 .. $last - 2) { for $second ($first + 1 .. $last - 1) { # see how many subsequent members exist $delta = $ints[$second] - $ints[$first]; $length = 2; $target = $ints[$second] + $delta; $explain = qq[($ints[$first], $ints[$second], ]; # loop over rest of @ints to find them for $next ($second + 1 .. $last) { if ($ints[$next] == $target) { $length ++; $target += $delta; $explain .= qq[$ints[$next], ]; } } # new or new equal longest length found $explain = substr($explain, 0, -2) . '), '; if ($length > $best) { $best = $length; $best_explain = $explain; } elsif ($length == $best) { $best_explain .= $explain unless $best_explain =~ m|\Q$explain|; } } } # give verdict say qq[\nInput: (] . join(', ', @ints) . ')'; say qq[Output: ] . ($best > 2 ? qq[$best: ] . substr($best_explain, 0, -2) : q[No arithmetic subsequences]); } sub validate { my (@ints, $j, $error); # check input is valid @ints = @_; # must have >= 3 in @ints $error = qq[need at least 3 integers] if scalar @ints < 3; # must be integers for $j (@ints) { $error = qq[$j is not an integer] unless $j =~ m|^-?\d+$|; } return 1 unless $error; say qq[\nInput: (] . join(', ', @ints) . qq[)\nOutput: Invalid input - $error]; return 0; }

Input: (9, 4, 7, 2, 10, 12, 13) Output: 4: (4, 7, 10, 13) Input: (2, 7, -1, 9, -4, 11, -7, 33, -10) Output: 5: (2, -1, -4, -7, -10) Input: (3, 3, 3) Output: 3: (3, 3, 3) Input: (1, 2, 4, 7, 11, 16) Output: 3: (1, 4, 7) Input: (2, 4, 6, 8, 21, 22, 23, 24) Output: 4: (2, 4, 6, 8), (21, 22, 23, 24) Input: (1, 2, 7, 19, 44, 123) Output: No arithmetic subsequences Input: (1, 2) Output: Invalid input - need at least 3 integers Input: (1, 2, x) Output: Invalid input - x is not an integer Input: (26, 9, 14, 10, 42, 44, 42, 24, 6, 14, 48, 19, 33, 4, 6, 4, 48, 31, 46, 1, 10, 37, 23, 28, 20, 36, 43, 22, 26, 43, 36, 7, 40, 19, 37, 8, 49, 4, 49, 39, 42, 10, 24, 22, 26, 31, 19, 41, 20, 33, 47, 17, 33, 32, 36, 46, 19, 44, 47, 27, 20, 25, 41, 14, 49, 28, 30, 15, 10, 2, 31, 47, 28, 45, 46, 36, 39, 0, 37, 9, 6, 33, 10, 38, 22, 8, 23, 25, 49, 34, 34, 3, 24, 46, 28, 43, 9, 27, 48, 24) Output: 6: (6, 14, 22, 30, 38, 46), (19, 22, 25, 28, 31, 34), (33, 36, 39, 42, 45, 48), (1, 10, 19, 28, 37, 46), (23, 28, 33, 38, 43, 48), (20, 22, 24, 26, 28, 30)

Peter Campbell Smith is hereby placed in the public domain