#!/usr/bin/perl -s

use v5.24;
use Test2::V0 '!float';
use PDL v2.017;
use PDL::NiceSlice;

our ($tests, $examples);

run_tests() if $tests || $examples;	# does not return

die <<EOS unless @ARGV;
usage: $0 [-examples] [-tests] [--] [N...]

-examples
    run the examples from the challenge
 
-tests
    run some tests

N...
    list of numbers

EOS


### Input and Output

say max_arith_seq(@ARGV);


### Implementation

# Using some graph theory for the solution of this task.
# Taking the list elements as vertices in a directed graph having a
# corresponding value.  Two vertices v1, v2 are connected with an edge
# v1->v2, if v2 follows v1 in the list and the difference of their
# values equals a given constant D.  By construction of the graph, each
# walk in this graph corresponds to an arithmetic subsequence of the
# list with a difference of D and vice versa.
# A graph's adjacency matrix A specifies all direct neighbor vertices,
# while in general the k-th power of A specifies the number of walks
# having a length of k between any two vertices.  Thus the largest power
# of A that is non-zero specifies the longest walk between two vertices.
# Taking the maximum walk length over the graphs generated by all
# possible differences D results in the requested maximum length of an
# arithmetic subsequence.
# As there are only "forward edges" in the constructed graph, each walk
# is actually a path and the length of any path in a graph cannot exceed
# the number of its edges. Therefore all graphs having less edges than
# the current found maximum walk length can be ignored.
# As a funny side note, the maximum length is computed without actually
# constructing such a sequence.
#
# References:
# https://en.wikipedia.org/wiki/Path_(graph_theory)
# https://en.wikipedia.org/wiki/Adjacency_matrix

sub max_arith_seq {
	my $s = long @_;
    # Get all pairwise differences from the list.
    my $diff = $s - $s->dummy(0);
    # Consider only forward differences, i.e. invalidate the difference
    # matrix' lower left triangle including the diagonal.
    $diff->badflag(1);
    $diff->indexND(
        scalar whichND sequence($s->dim(0)) <= sequence(1, $s->dim(0))
    ) .= $diff->badvalue;

    my $max = '-inf';
    # Loop over all forward differences along with their frequency,
    # sorted descending by frequency.
    for my $fd (cat(rle $diff->where($diff->isgood)->qsort)
            ->xchg(0, 1)->qsortvec->(,-1:0)->dog) {
        my ($freq, $d) = $fd->list;
        # Terminate the process for too low frequencies.
        last if $freq <= $max;
        # Build the adjacency matrix from the difference matrix for the
        # current value of D.
        my $adj = ($diff == $d)->setbadtoval(0);
        # Find the largest power of the adjacency matrix that is
        # non-zero.
        my $pow;
        for (my $adj_p = $adj->copy; $adj_p->any; $adj_p x= $adj) {
            $pow++;
        }
        # Record a new maximum.
        $max = $pow if $pow > $max;
    }
    # The number of vertices in an open walk is one more than the number
    # of its edges.
    $max + 1;
}


### Examples and tests

sub run_tests {
    SKIP: {
        skip "examples" unless $examples;

        is max_arith_seq(9, 4, 7, 2, 10), 3, 'example 1';
        is max_arith_seq(3, 6, 9, 12), 4, 'example 2';
        is max_arith_seq(20, 1, 15, 3, 10, 5, 8), 4, 'example 3';
    }

    SKIP: {
        skip "tests" unless $tests;

        is max_arith_seq(0, 1, 0, 1, 3, 3, 4, 4, 9, 9, 10, 10, 12, 12,
            13, 13, 27, 27, 28, 28, 30, 30, 31, 31, 36, 36), 2,
        'trivial arithmetic subsequences only';
	}

    done_testing;
    exit;
}