Slicing and dicing
a double century
Weekly challenge 200 — 16 January 2023
Week 200  16 Jan 2023
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.
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.
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]
:
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).
#!/usr/bin/perl # Peter Campbell Smith  20230116 # 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 subruns (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 subrun lengths for $sub_length (3 .. $length) { # loop over possible starting positions for $offset (0 .. $length  $sub_length) { # add subrun to rubric $rubric .= '('; for $j ($start + $offset .. $start + $offset + $sub_length  1) { $rubric .= qq[$array[$j], ]; } $rubric =~ s, $), ; } } }
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)