Travelers, hello.

If you read this, I suggest continuation of the "entertaining" material that I wrote before. If you followed a little thought, which branched out into three articles, but the main message was, only to show interest in the declarative approach. For some reason, it’s not great, as if eSCuel did not become publicly available and obligatory, because without it it’s impossible to think about how the data can be processed differently. True, it’s better to formulate the task and not to worry about what this translates into.

Let's get down to business, I wrote before that about trying to amuse you, so I’ll continue to show an example of using the prologue, although the previous articles have shown that interest in python and even go will arouse interest right away for a couple of thousand people, that interest in news about a new battery to Tesla, is stotysch views, and for writing programs on the portal razrabotnichestskom not so few, seen behind this behavior were noted on reading the comments, and maybe FIVE of them, after the second reading of this proposal esch It confuses the idea that it should read more ...

It turned out that the hypothesis of interest is not fulfilled, and then I just show how to use the prologue, it is a modern, developing, and freely distributed tool, it can be taken and formulated, only so that it could be formulated to see an advantage.

I’ll say that time travel does not exist, but we’ll go a week ago, there was an interesting Prolog about three parts in the tape, that’s where the topic of solving a randomly encountered new problem was touched, I take this interesting site, and the most difficult task (only not turning a string into a number)), I'll try to do it in the Prolog .

Stop raising interest, starting ...

Task 446 arithmetic-slices-ii-subsequence

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequences:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9.
The following sequence is not arithmetic.
1, 1, 2, 5, 7

All in all, the difference between the two neighbors should be preserved, just need to check this?
Read on:

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 <P1 <... <Pk <N.
A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A [P0], A [P1], ..., A [Pk-1], A [Pk] is arithmetic. In particular, this means that k ≥ 2.
The function should return the number of arithmetic subsequence slices in the array A.

Wow wording, you need to find out how many slices you can meet, how many options for sublists you can find, so that the difference between adjacent items does not differ.

It is as if the sublists are in one large set of all permutations of the input list.

Example:
Input: [2, 4, 6, 8, 10]
Output: 7
Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2, 4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

I know how to express a sublist in a prolog, this:

sublists(InputList, SubList):-
    append(Prefix,Root,InputList),
    append(SubList,Suffix,Root).

How to check that the list of the desired type is necessary to check in triples:

is_seq(A,B,C]):-A-B =:=B-C.
is_seq(A,B,C|Tail]):-A-B =:=B-C, is_seq(B,C|Tail]).

If we discard the permutations of all elements of the list, it turns out that this is not just a sublist of the elements standing nearby, it is such a sublist that was formed with the omission of the elements.

Then put it like this:

seq(_,[]).
seq([H|T],[H|T1]):-seq(T,T1).
seq([_|T],T1):-seq(T,T1).

Such a rule will return all possible sublists from the list, but can start from one element, or by skipping it, from the next one, also any quantity can be discarded at the end.

In total, we get an overestimated number of solutions, it is immediately clear that an empty list will return many times, and repetitions cannot be avoided when elements are dropped from the end.

After reviewing the proposed tests for this problem, it turned out that there could be duplicate values ​​at the input, that for such a list [0,1,2,2,2] there should be 4 solutions. Each 2-ka can be taken separately, and this should be considered as a separate slice, so three options [0,1,2] and one [2,2,2] are suitable.

This is bad luck, because the sequence generator will produce duplicate values, but how to make the calculation only unique? You’ll have to mark them, make the lists different from each other. I’ll build the whole solution on the basis of generating lists, checking the condition and counting the number of solutions. And what to do with repetitions of decisions ...

I’ll make a simple numbering of the elements, let the list turn into a list of components Value / Index, a structured term, this is what they call it. For the above example, this would be [0 / 1,1 / 2,2 / 3,2 / 4,2 / 5]. The sequences generated by this input will all be different.

So, you can turn the list into a marked one:

label([],[],_).
label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1).

Well and the most important point, checking for is_seq arithmetic, after a series of attempts, taking into account the marked list, this rule turned into a rather complicated expression. Here we check that the triples of numbers correspond to the condition, and calculate the key of this particular solution, to exclude unique solutions, a key was needed, this will help to collect all the keys in a list and then count them.

At the input is a marked list, the output will be the key value, calculate it as an integer whose digits are the sum of Value + Index for each element.

%is_seq список, максимальный индекс, ключ
is_seq([A/An,B/Bn,C/Cn],2,N):-
      A-B=:=B-C,
      N is 10000*(A+An)+100*(B+Bn)+(C+Cn).
is_seq([A/An,B/Bn,C/Cn|T],K,N):-
      A-B=:=B-C,
      is_seq([B/Bn,C/Cn|T],K1,N1),
      K is K1+1,
      N is N1+(A+An)*(100**K).

To count all the solutions, I will use the built-in ability to fulfill the goal and collect all the unique solutions into the setof () list. Simply compiling a list of all sequences turned out to be completely ineffective, from here came the idea of ​​a key as a simpler value:

get_number(List,N) :- 
   label(List,ListL,1),
   setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result),
   length(Result,N),!.
get_number(_,0).

Of course, performance was not particularly expressed in such a solution.

Here is such a complete text of the program, with a list of tests, which is hardcore fished out from the site with the task (this is just part of the tests):

label([],[],_).
label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1).
seq(_,[]).
seq([H|T],[H|T1]):-seq(T,T1).
seq([_|T],T1):-seq(T,T1).
is_seq([A/An,B/Bn,C/Cn],2,N):-
      A-B=:=B-C,
      N is 10000*(A+An)+100*(B+Bn)+(C+Cn).
is_seq([A/An,B/Bn,C/Cn|T],K,N):-
      A-B=:=B-C,
      is_seq([B/Bn,C/Cn|T],K1,N1),
      K is K1+1,
      N is N1+(A+An)*(100**K).
get_number(List,N) :- label(List,ListL,1),setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result),
   length(Result,N),!.
get_number(_,0).
%unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal,     !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).
%all test
:-assert_are_equal(get_number([2,4,6,8,10],7),true).
:-assert_are_equal(get_number([],0),true).
:-assert_are_equal(get_number([1],0),true).
:-assert_are_equal(get_number([1,2],0),true).
:-assert_are_equal(get_number([1,2,3],1),true).
:-assert_are_equal(get_number([1,2,3,4],3),true).
:-assert_are_equal(get_number([1,2,3,4,5],7),true).
:-assert_are_equal(get_number([1,2,3,4,5,6],12),true).
:-assert_are_equal(get_number([1,2,3,4,5,6,7],20),true).
:-assert_are_equal(get_number([1,2,3,4,5,6,7,8],29),true).
:-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9],41),true).
:-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9,10],55),true).
:-assert_are_equal(get_number([2,2,3,4],2),true).
:-assert_are_equal(get_number([0,1,2,2,2],4),true).
:-assert_are_equal(get_number([0,2000000000,-294967296],0),true).
:-assert_are_equal(get_number([1,1,1],1),true).
:-assert_are_equal(get_number([1,1,1,1],5),true).
:-assert_are_equal(get_number([1,1,1,1,1],16),true).
:-assert_are_equal(get_number([1,1,1,1,1,1],42),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1],99),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1],219),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1],466),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1],968),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1],1981),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1],4017),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1],8100),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1],16278),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],32647),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],65399),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],130918),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],261972),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],524097),true).
:-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],1048365),true).

As a disappointing result, here is such an efficiency:

get_number([2, 4, 6, 8, 10], 7)->ok:0/sec
get_number([], 0)->ok:0/sec
get_number([1], 0)->ok:0/sec
get_number([1, 2], 0)->ok:0/sec
get_number([1, 2, 3], 1)->ok:0/sec
get_number([1, 2, 3, 4], 3)->ok:0/sec
get_number([1, 2, 3, 4, 5], 7)->ok:0/sec
get_number([1, 2, 3, 4, 5, 6], 12)->ok:0/sec
get_number([1, 2, 3, 4, 5, 6, 7], 20)->ok:0/sec
get_number([1, 2, 3, 4, 5, 6, 7, 8], 29)->ok:0/sec
get_number([1, 2, 3, 4, 5, 6, 7, 8, 9], 41)->ok:0/sec
get_number([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 55)->ok:0/sec
get_number([2, 2, 3, 4], 2)->ok:0/sec
get_number([0, 1, 2, 2, 2], 4)->ok:0/sec
get_number([0, 2000000000, -294967296], 0)->ok:0/sec
get_number([1, 1, 1], 1)->ok:0/sec
get_number([1, 1, 1, 1], 5)->ok:0/sec
get_number([1, 1, 1, 1, 1], 16)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1], 42)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1], 99)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1], 219)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1], 466)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 968)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1981)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 4017)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 8100)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 16278)->ok:0/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 32647)->ok:1/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 65399)->ok:1/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 130918)->ok:3/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 261972)->ok:6/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 524097)->ok:12/sec
get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1048365)->ok:27/sec

Collecting a list, even just decision keys, is very cumbersome, but this is a declarative decision, without which it is not possible to count all unique solutions.

Conclusion.

This is how the tasks in the Prolog language are formulated; simply transferring the problem statement to the program is fraught with insufficient efficiency. Or maybe in this problem only an algorithmic solution is available? How complicated is the process?

Again I leave questions ...

All the same, the search for answers is interesting in our profession, right?