• Guest
HabraHabr
  • Main
  • Users

  • Development
    • Programming
    • Information Security
    • Website development
    • JavaScript
    • Game development
    • Open source
    • Developed for Android
    • Machine learning
    • Abnormal programming
    • Java
    • Python
    • Development of mobile applications
    • Analysis and design of systems
    • .NET
    • Mathematics
    • Algorithms
    • C#
    • System Programming
    • C++
    • C
    • Go
    • PHP
    • Reverse engineering
    • Assembler
    • Development under Linux
    • Big Data
    • Rust
    • Cryptography
    • Entertaining problems
    • Testing of IT systems
    • Testing Web Services
    • HTML
    • Programming microcontrollers
    • API
    • High performance
    • Developed for iOS
    • CSS
    • Industrial Programming
    • Development under Windows
    • Image processing
    • Compilers
    • FPGA
    • Professional literature
    • OpenStreetMap
    • Google Chrome
    • Data Mining
    • PostgreSQL
    • Development of robotics
    • Visualization of data
    • Angular
    • ReactJS
    • Search technologies
    • Debugging
    • Test mobile applications
    • Browsers
    • Designing and refactoring
    • IT Standards
    • Solidity
    • Node.JS
    • Git
    • LaTeX
    • SQL
    • Haskell
    • Unreal Engine
    • Unity3D
    • Development for the Internet of things
    • Functional Programming
    • Amazon Web Services
    • Google Cloud Platform
    • Development under AR and VR
    • Assembly systems
    • Version control systems
    • Kotlin
    • R
    • CAD/CAM
    • Customer Optimization
    • Development of communication systems
    • Microsoft Azure
    • Perfect code
    • Atlassian
    • Visual Studio
    • NoSQL
    • Yii
    • Mono и Moonlight
    • Parallel Programming
    • Asterisk
    • Yandex API
    • WordPress
    • Sports programming
    • Lua
    • Microsoft SQL Server
    • Payment systems
    • TypeScript
    • Scala
    • Google API
    • Development of data transmission systems
    • XML
    • Regular expressions
    • Development under Tizen
    • Swift
    • MySQL
    • Geoinformation services
    • Global Positioning Systems
    • Qt
    • Dart
    • Django
    • Development for Office 365
    • Erlang/OTP
    • GPGPU
    • Eclipse
    • Maps API
    • Testing games
    • Browser Extensions
    • 1C-Bitrix
    • Development under e-commerce
    • Xamarin
    • Xcode
    • Development under Windows Phone
    • Semantics
    • CMS
    • VueJS
    • GitHub
    • Open data
    • Sphinx
    • Ruby on Rails
    • Ruby
    • Symfony
    • Drupal
    • Messaging Systems
    • CTF
    • SaaS / S+S
    • SharePoint
    • jQuery
    • Puppet
    • Firefox
    • Elm
    • MODX
    • Billing systems
    • Graphical shells
    • Kodobred
    • MongoDB
    • SCADA
    • Hadoop
    • Gradle
    • Clojure
    • F#
    • CoffeeScript
    • Matlab
    • Phalcon
    • Development under Sailfish OS
    • Magento
    • Elixir/Phoenix
    • Microsoft Edge
    • Layout of letters
    • Development for OS X
    • Forth
    • Smalltalk
    • Julia
    • Laravel
    • WebGL
    • Meteor.JS
    • Firebird/Interbase
    • SQLite
    • D
    • Mesh-networks
    • I2P
    • Derby.js
    • Emacs
    • Development under Bada
    • Mercurial
    • UML Design
    • Objective C
    • Fortran
    • Cocoa
    • Cobol
    • Apache Flex
    • Action Script
    • Joomla
    • IIS
    • Twitter API
    • Vkontakte API
    • Facebook API
    • Microsoft Access
    • PDF
    • Prolog
    • GTK+
    • LabVIEW
    • Brainfuck
    • Cubrid
    • Canvas
    • Doctrine ORM
    • Google App Engine
    • Twisted
    • XSLT
    • TDD
    • Small Basic
    • Kohana
    • Development for Java ME
    • LiveStreet
    • MooTools
    • Adobe Flash
    • GreaseMonkey
    • INFOLUST
    • Groovy & Grails
    • Lisp
    • Delphi
    • Zend Framework
    • ExtJS / Sencha Library
    • Internet Explorer
    • CodeIgniter
    • Silverlight
    • Google Web Toolkit
    • CakePHP
    • Safari
    • Opera
    • Microformats
    • Ajax
    • VIM
  • Administration
    • System administration
    • IT Infrastructure
    • *nix
    • Network technologies
    • DevOps
    • Server Administration
    • Cloud computing
    • Configuring Linux
    • Wireless technologies
    • Virtualization
    • Hosting
    • Data storage
    • Decentralized networks
    • Database Administration
    • Data Warehousing
    • Communication standards
    • PowerShell
    • Backup
    • Cisco
    • Nginx
    • Antivirus protection
    • DNS
    • Server Optimization
    • Data recovery
    • Apache
    • Spam and antispam
    • Data Compression
    • SAN
    • IPv6
    • Fidonet
    • IPTV
    • Shells
    • Administering domain names
  • Design
    • Interfaces
    • Web design
    • Working with sound
    • Usability
    • Graphic design
    • Design Games
    • Mobile App Design
    • Working with 3D-graphics
    • Typography
    • Working with video
    • Work with vector graphics
    • Accessibility
    • Prototyping
    • CGI (graphics)
    • Computer Animation
    • Working with icons
  • Control
    • Careers in the IT industry
    • Project management
    • Development Management
    • Personnel Management
    • Product Management
    • Start-up development
    • Managing the community
    • Service Desk
    • GTD
    • IT Terminology
    • Agile
    • Business Models
    • Legislation and IT-business
    • Sales management
    • CRM-systems
    • Product localization
    • ECM / EDS
    • Freelance
    • Venture investments
    • ERP-systems
    • Help Desk Software
    • Media management
    • Patenting
    • E-commerce management
    • Creative Commons
  • Marketing
    • Conferences
    • Promotion of games
    • Internet Marketing
    • Search Engine Optimization
    • Web Analytics
    • Monetize Web services
    • Content marketing
    • Monetization of IT systems
    • Monetize mobile apps
    • Mobile App Analytics
    • Growth Hacking
    • Branding
    • Monetize Games
    • Display ads
    • Contextual advertising
    • Increase Conversion Rate
  • Sundry
    • Reading room
    • Educational process in IT
    • Research and forecasts in IT
    • Finance in IT
    • Hakatonas
    • IT emigration
    • Education abroad
    • Lumber room
    • I'm on my way

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:

3r33333.  
    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.

It may be interesting

  • Comments
  • About article
  • Similar news
This publication has no comments.

weber

Author

4-11-2018, 08:34

Publication Date

Development / Prolog

Category
  • Comments: 0
  • Views: 302
SHOCK! New software for phishing does
Declarative thinking
“How to turn a simple project into a
The story of one game or 4 strategy,
Entertaining prologue # 2
Entertaining prologue
Write a comment
Name:*
E-Mail:


Comments
this is really nice to read..informative post is very good to read..thanks a lot! How is the cost of house cleaning calculated?
Yesterday, 17:14

Legend SEO

It’s very informative and you are obviously very knowledgeable in this area. You have opened my eyes to varying views on this topic with interesting and solid content.

entegrasyon programları
Yesterday, 17:09

taxiseo2

I am really enjoying reading your well written articles. It looks like you spend a lot of effort and time on your blog. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work.

entegrasyon programları
Yesterday, 17:02

taxiseo2

I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work...먹튀

Yesterday, 16:50

raymond weber

Lose Weight Market provides the best fitness tips, workout guides, keto recipes and diet plans, yoga workout routine and plans, healthy recipes, and more! Check Out: Lose Weight Market


Corvus Health provides medical training services as well as recruiting high quality health workers for you or placing our own best team in your facility. Check Out: Health Workforce Recruitment




I.T HATCH offers a wide range of IT services including remote access setup, small business servers, data storage solutions, IT strategy services, and more. Check Out: IT strategy services
Yesterday, 22:33

noorseo

Adv
Website for web developers. New scripts, best ideas, programming tips. How to write a script for you here, we have a lot of information about various programming languages. You are a webmaster or a beginner programmer, it does not matter, useful articles will help to make your favorite business faster.

Login

Registration Forgot password