Task — Arithmetic slices

You are given an array of integers. Write a script to find out all Arithmetic Slices for the given array of integers. An integer array is called arithmetic if it has at least 3 elements and the differences between any three consecutive elements are the same.

Examples

Example 1
Input: @array = (1,2,3,4)
Output: (1,2,3), (2,3,4), (1,2,3,4)

Example 2
Input: @array = (2)
Output: () as no slice found.

Analysis

For ease, I decided to start by creating an array @diff, where $diff[$j] = $array[$j + 1] - $array[$j] - so I am looking for runs of 3 or more identical numbers in @diff.

I move along @diff, maintaining a value $run_starts which is the index into @array where the current run of identical values of $diff[$j] starts, and $this_diff which is that value. Whenever I reach a $j which is not equal to $this_diff I know that $array[$j] is the end of the current run and potentially the start of another run.

Having identified a run of identical values of $diff[$j]:

• if it is less than 3 long I ignore it
• if it is 3 long, then I add it to the output
• if it is more than 3 long I add all its subsets as well - as in the example above

For convenience and clarity I have delegated that part of the task to subroutine analyse.

In my submission I have added a number of edge cases, such as zero or negative numbers in @array, runs of negative differences, overlapping slices (eg 1, 2, 3, 6, 9).

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2023-01-16
# PWC 200 task 1

use v5.28;
use utf8;
use warnings;

my (@tests, $test, @array, $rubric);

@tests = ([1, 2, 3, 4], [1, 2, 3, 4, 6], [0, 1, 5, 9, 13, 22, 99, 101, 102, 103, 105],
    [0, 0, 0], [-3, 1, 5, 9], [10, 8, 6, 4], [7, 8, 8, 10, 13, 17], [1, 2, 3, 6, 9],
    [0, 4, 8, 12, 16, 20, 24, 28, 32]);

for $test (@tests) {
    arithmetic_slices(@$test);
}

sub arithmetic_slices {
    
    my ($j, @diff, $last_diff, $run_starts);
    @array = @_;
    
    # initialise
    $rubric = '';
    @diff = ();
    
    # create @diff array and put a dummy value on the end
    for $j (0 .. scalar(@array) - 2) {
        $diff[$j] = $array[$j + 1] - $array[$j];
    }
    push @diff, 1e9;
    
    # loop over the @diff array looking for runs of the same number
    $last_diff = 1e9;
    $run_starts = -1;
    for $j (0 .. scalar(@array) - 1) {
        
        # continuation of a run
        next if $diff[$j] == $last_diff;
            
        # end of a run, possible start of next one
        analyse($run_starts, $j) if $run_starts >= 0;
        $run_starts = $j;
        $last_diff = $diff[$j];
    }
    
    # report result
    say qq[\nInput:  (] . join(', ', @array) . ')';
    say qq[Output: ] . ($rubric ? substr($rubric, 0, -2) : '() as no slice found');
}   

sub analyse {
    
    # split a run into sub-runs (eg 1,2,3,4 => 1,2,3; 2,3,4; 1,2,3,4)
    my ($start, $end) = @_;
    my ($length, $sub_length, $offset, $j);
    
    # minimum run length is 3
    $length = $end - $start + 1;
    return if $length < 3;
    
    # loop over possible sub-run lengths
    for $sub_length (3 .. $length) {
        
        # loop over possible starting positions
        for $offset (0 .. $length - $sub_length) {
            
            # add sub-run to rubric
            $rubric .= '(';
            for $j ($start + $offset .. $start + $offset + $sub_length - 1) {
                $rubric .= qq[$array[$j], ];
            }
            $rubric =~ s|, $|), |;
        }
    }
}

Output

Input:  (1, 2, 3, 4)
Output: (1, 2, 3), (2, 3, 4), (1, 2, 3, 4)

Input:  (1, 2, 3, 4, 6)
Output: (1, 2, 3), (2, 3, 4), (1, 2, 3, 4)

Input:  (0, 1, 5, 9, 13, 22, 99, 101, 102, 103, 105)
Output: (1, 5, 9), (5, 9, 13), (1, 5, 9, 13), 
        (101, 102, 103)

Input:  (0, 0, 0)
Output: (0, 0, 0)

Input:  (-3, 1, 5, 9)
Output: (-3, 1, 5), (1, 5, 9), (-3, 1, 5, 9)

Input:  (10, 8, 6, 4)
Output: (10, 8, 6), (8, 6, 4), (10, 8, 6, 4)

Input:  (7, 8, 8, 10, 13, 17)
Output: () as no slice found

Input:  (1, 2, 3, 6, 9)
Output: (1, 2, 3), (3, 6, 9)

Input:  (0, 4, 8, 12, 16, 20, 24, 28, 32)
Output: (0, 4, 8), (4, 8, 12), (8, 12, 16), (12, 16, 20), 
        (16, 20, 24), (20, 24, 28), (24, 28, 32), 
        (0, 4, 8, 12), (4, 8, 12, 16), (8, 12, 16, 20),
        (12, 16, 20, 24), (16, 20, 24, 28),
        (20, 24, 28, 32), (0, 4, 8, 12, 16), 
        (4, 8, 12, 16, 20), (8, 12, 16, 20, 24),
        (12, 16, 20, 24, 28), (16, 20, 24, 28, 32),
        (0, 4, 8, 12, 16, 20), (4, 8, 12, 16, 20, 24),
        (8, 12, 16, 20, 24, 28), (12, 16, 20, 24, 28, 32),
        (0, 4, 8, 12, 16, 20, 24),
        (4, 8, 12, 16, 20, 24, 28),
        (8, 12, 16, 20, 24, 28, 32), 
        (0, 4, 8, 12, 16, 20, 24, 28),
        (4, 8, 12, 16, 20, 24, 28, 32),
        (0, 4, 8, 12, 16, 20, 24, 28, 32)