Travelers, hello.

If you are reading this, I propose a continuation of that “entertaining” material that I wrote before. If you have followed the idea that has been clarified in three articles, the main message then was only to show interest in the declarative approach. For some reason, it is not great, as if Esculla has not become generally accessible and obligatory, because without it, it is impossible to think, and how it is possible to process the data otherwise. True, it is better to formulate the task and not to care about what it embodies.

Let's get to the point, I wrote about attempts to amuse you, so I will continue to show an example of using the prologue, although previous articles have shown that interest in python and even go will cause interest for a couple of thousand people right away, that interest in news about the 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’ll just show how the prologue can be used, this is a modern, developing, and free spreading tool, it can be taken and formulated, only that this could be formulated to see the advantage.

I will say that time travel does not exist, but we will go a week ago, there was an interesting prologue about three parts in the tape, that’s where the new problem was solved, I’ve taken this interesting site and the most difficult task (only not turning a string into a number)), I will try to do in the Prolog .

Stop calling interest, I'm starting ...

Problem 446 arithmetic-slices-ii-subsequence

It is a sequence of numbers of consecutive elements.
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

Only, the difference between the two neighbors should be maintained, just need to check this?
We read further:

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

Wow wording, you need to know how many slices can be found, how many options of sublists can be found, so that the difference between the standing elements does not differ.

As if the sublists 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 the sub-list in the prologue, this is:

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

How to check that the list of the desired type - you need to check for triples:

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

If we discard the permutations of all the elements of the list, it turns out that these are not just sublists of elements standing next to each other; they are such sublists that were formed with the omission of elements.

Then we express 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 sub-lists from the list, but it can start from one element, or by skipping it, from the next, any number can also be dropped at the end.

In total, we get an overestimated number of solutions; it’s immediately obvious that the empty list will come back many times as well as not to avoid repetitions when the elements are dropped from the end.

After reviewing the proposed tests for this task, it turned out that there could be repeated values ​​at the input, that for such a list [0,1,2,2,2] there should be 4 solutions. Each 2-ku can be taken separately, and this should be considered as a separate slice, for a total of three options [0,1,2] and one [2,2,2] will do.

Here bad luck, because the sequence generator will produce duplicate values, and how to make only unique counts? You have to mark them, make the lists differ from each other. The whole solution will be built on how to generate lists, check the condition and count the number of solutions. And what to do with repeating decisions ...

I will make a simple numbering of elements, let the list turn into a list of components Value / Index, a structured term, so call it. For the example above, this would be [0 / 1.1 / 2.2 / 3.2 / 4.2 / 5]. The sequences generated from this input will be all different.

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

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

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

The input is a marked list, the output will be the key value, we will calculate it as an integer, the digits of which will be the sum Value + Index for each item.

 %is_seq ,  ,  is_seq([A/An,B/Bn,C/Cn],2,N):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, is_seq([B/Bn,C/Cn|T],K1,N1), K is K1+1, N is N1+(A+An)*(100**K). 

To count all the decisions, I will use the built-in ability to fulfill the goal and collect all the unique solutions in the setof () list. Collecting just a list of all sequences turned out to be completely ineffective, hence 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, in this decision, the performance is not particularly expressed.

Here is the full text of the program, with a list of tests, which is hardcore 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):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, 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, such effectiveness:

 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 

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

The conclusion.

This is how 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 algorithmic solution is available? How much need to complicate the process?

Again leave questions ...

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