Warm up with the Prologue
3r3-31.
Travelers, hello. 3r33333.
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, but 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. 3r33333.
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, causes a hundred hits, and for writing programs, on 3r-37.
development portal itself. not so few people noticed this behavior were noted in the comments, and maybe five of them, after the second reading of this sentence, will get confused by the thought that it is worth reading more 3r33301.
It turned out that the hypothesis of interest is not fulfilled, and then I will simply show how the prologue can be used, this is a modern, developing, and free-spread tool, it can be taken and formulated, only that such a thing could be formulated to see the advantage. 3r33333.
I will say that time travel does not exist, but we will go a week ago, there in the tape there was an interesting prologue about three parts, it was there that the topic of solving a randomly encountered problem was touched, I take 3r313. this
An interesting site, and the most difficult task (just not turning the string into a number)), I will try to do in 3r315. Prologue 3r3166. . 3r33333.
Enough interest, starting 3r3303. arithmetic-slices-ii-subsequence
3r33333.
3r362. It is a sequence of numbers between consecutive elements. 3r33333.
For example, these are arithmetic sequences:
? ? ? ? 9
? ? ? 7
? -? -? -9
The following sequence is not arithmetic. 3r33333.
? ? ? ? 7
Only, the difference between the two neighbors should be maintained, just need to check this? 3r33333.
Read on:
3r33333.
3r362. A zero-indexed array A numbers of N numbers is given. A sequence of integers (P? P? , Pk) such that 0 ≤ P0 < P1 <… < Pk < N.
A subsequence slice (P? P? , Pk) of the array A[P0], A[P1], , A[Pk-1], A[Pk]is arithmetic. In particular, this means that k ≥ 2.
Wow wording, you need to find out how many slices you can meet, how many options of sublists you can find, so that the difference between the standing elements does not differ. 3r33333.
As if the sublists are in one large set of all permutations of the input list. 3r3303. 3r33333.
3r362. Example: 3r33333.
Input:[2, 4, 6, 8, 10]3r33333.
Output: 7
Explanation:
All arithmetic subsequence slices are:
[2,4,6]3r33333.
[4,6,8]3r33333.
[6,8,10]3r33333.
[2,4,6,8]3r33333.
[4,6,8,10]3r33333.
[2,4,6,8,10]3r33333.
[2,6,10]
I know how to express the sub-list in the prologue, this is:
3r33333.
sublists (InputList, SubList): -
append (Prefix, Root, InputList),
append (SubList, Suffix ,, Root). 3r33333. How to check that the list of the desired type - you need to check for triples:
3r33333. is_seq (A, B, C]): - A-B =: = B-C.
is_seq (A, B, C | Tail]): - A-B =: = B-C, is_seq (B, C | Tail]). 3r33333. 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. 3r33333.
Then we express it like this:
seq (_,[]).
seq ([H|T],[H|T1]): - seq (T, T1).
seq ([_|T], T1): - seq (T, T1). 3r33333. 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. 3r33333.
In total, we get an overestimated number of solutions; it’s immediately obvious that the empty list will return many times as well as not to avoid repetitions when the elements are dropped from the end. 3r33333.
After reviewing the proposed tests for this task, it turned out that there may be duplicate values at the input, which for such a list is[0,1,2,2,2]There should be 4 solutions. Each 2-ku can be taken separately, and it should be considered as a separate slice, in total three options[0,1,2]will do. and one[2,2,2]. 3r33333.
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 different 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 the repetition of 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 above example, this would be[0/1,1/2,2/3,2/4,2/5]. The sequences generated from such an input will already be all different. 3r33333.
So, you can turn the list into marked: 3r3303. 3r33333.
label ([],[], _).
label ([A|T],[A/N|T1], N): - N1 is N + ? label (T, T? N1). 3r33333. 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. 3r33333.
The input is a marked list, the output will be the key value, we calculate it as an integer, the digits of which will be the sum Value + Index for each item. 3r3303. 3r33333.
% is_seq list, maximum index, key
is_seq ([A/An,B/Bn,C/Cn], ? 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], K? N1),
K is K1 + ?
N is N1 + (A + An) * (100 ** K). 3r33333. 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 a simple list of all sequences turned out to be completely ineffective, hence the ideas of the key, as a simpler value: 3r3303. 3r33333.
get_number (List, N): -
label (List, ListL, 1),
setof (Len, K ^ Sub ^ (seq (ListL, Sub), is_seq (Sub, K, Len)), Result), 3r3144. length (Result, N),!.
get_number (_, 0). 3r33333. Of course, in this decision, performance is not particularly expressed. 3r33333.
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): 3r3303. 3r33333.
label ([],[], _).
label ([A|T],[A/N|T1], N): - N1 is N + ? label (T, T? N1).
seq (_,[]).
seq ([H|T],[H|T1]): - seq (T, T1).
seq ([_|T], T1): - seq (T, T1).
is_seq ([A/An,B/Bn,C/Cn], ? 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], K? N1),
K is K1 + ?
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, 3r3333314. 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). 3r33333. As a disappointing result, such effectiveness: 3r3303. 3r33333.
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
3r33333.
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. 3r3303. 3r33333.
The conclusion.
3r33333.
This is how problems in the Prolog language are formulated, simply transferring the problem statement to the program is fraught with insufficient efficiency.Yu. Or maybe in this problem only algorithmic solution is available? How much need to complicate the process? 3r33333.
Again I leave the questions
All the same, the search for answers and interesting in our profession, right? 3r3303.
3r3307. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r3308.
