The weekly challenge 221 - Task 2: Arithmetic Subsequence

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-221/#TASK2
 3 #
 4 # Task 2: Arithmetic Subsequence
 5 # ==============================
 6 #
 7 # You are given an array of integers, @ints.
 8 #
 9 # Write a script to find the length of the longest Arithmetic Subsequence in the given array.
10 #
11 ##  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.
12 #
13 ##  A subsquence is arithmetic if ints[i + 1] - ints[i] are all the same value (for 0 <= i < ints.length - 1).
14 #
15 #
16 ## Example 1:
17 ##
18 ## Input: @ints = (9, 4, 7, 2, 10)
19 ## Output: 3
20 ##
21 ## The longest Arithmetic Subsequence (4, 7, 10) can be derived by deleting 9 and 2.
22 #
23 ## Example 2:
24 ##
25 ## Input: @ints = (3, 6, 9, 12)
26 ## Output: 4
27 ##
28 ## No need to remove any elements, it is already an Arithmetic Subsequence.
29 #
30 ## Example 3:
31 ##
32 ## Input: @ints = (20, 1, 15, 3, 10, 5, 8)
33 ## Output: 4
34 ##
35 ## The longest Arithmetic Subsequence (20, 15, 10, 5) can be derived by deleting 1, 3 and 8.
36 #
37 ############################################################
38 ##
39 ## discussion
40 ##
41 ############################################################
42 #
43 # We find the longest arithmetic subsequence recursively. If
44 # the current array is arithmetic, we're done and have found
45 # the longest arithmetic subsequence. Otherwise we try in turn
46 # to find the longest arithmetic subsequence with each of the
47 # elements of the array removed. The longest of all these
48 # subsolutions is our final solution.
49 
50 use strict;
51 use warnings;
52 
53 arithmetic_subsequence(9, 4, 7, 2, 10);
54 arithmetic_subsequence(3, 6, 9, 12);
55 arithmetic_subsequence(20, 1, 15, 3, 10, 5, 8);
56 
57 sub arithmetic_subsequence {
58    my @ints = @_;
59    print "Input: (" . join(", ", @ints) . ")\n";
60    my $result = find_longest_arithmetic(@ints);
61    print "Output: $result\n";
62 }
63 
64 sub find_longest_arithmetic {
65    my @ints = @_;
66    my $result;
67    if(is_arithmetic(@ints)) {
68       $result = scalar(@ints);
69    } else {
70       my $max = 0;
71       foreach my $index (0..$#ints) {
72          my $tmp = find_longest_arithmetic( @ints[0..$index-1], @ints[$index+1..$#ints]);
73          $max = $tmp if $tmp > $max;
74       }
75       return $max;
76    }
77 }
78 
79 # this helper function just checks if a given array is
80 # arithmetic. For that, we calculate the first difference.
81 # If any of the subsequent differences doesn't match this
82 # first one, the array is not arithmetic and we return 0.
83 # In the end all differences match so we can return 1.
84 sub is_arithmetic {
85    my @ints = @_;
86    return 0 if scalar(@ints) < 2;
87    my $diff = $ints[1] - $ints[0];
88    foreach my $index (1..$#ints-1) {
89       my $this_diff = $ints[$index+1] - $ints[$index];
90       return 0 if $this_diff != $diff;
91    }
92    return 1;
93 }