Hello residents , it's time to talk about declarative programming. This is when you rubbed at the institute, that the program can not code, and formulate. This is the opposite of imperative, which is now in all programming languages. Let's pay tribute to the functional approach, it’s brotherly here, and it’s doing its job getting deeper into modernity, so you can find lambda in C ++ and javascripts?

But the situation is sadder with logical, production programming, which can be presented only on Prolog .

Here I am going to throw an interesting thought for habr-effect. Why not write an article about solving a programmer's problem. So, I think a lot of posts and turned out. I join the choice of topics. Here is the original, new direction of development and competition between the participants, we show how we can solve problems, so that all readers are interested to express their opinions and point out your mistakes, because you have enough specialists in Javascript and C ++, can pitonoznavvy still come across ...

Total goal of the article : to solve at the time of writing the problem, which was not yet known at the beginning of the post and show your code of thought, confirming it with the course and the resulting working solution. But for this check you need an arbiter, you don’t review yourself. I will select leetcode.com in this role.

1. So

Here we select the closest to the most difficult task, and try to solve it at Prolog, it is necessary to demonstrate how entertaining it is.

2. Problem 44. Wildcard Matching

An anaeronautical string (s) and a pattern (p), implement a wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching input string (not partial).

Note:
')
s could be empty and contains only lowercase letters az.
could be empty and contains characters like lowercase? or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
Input:
s = "aa"
p = '*'
Output: true

Explanation: '*' matches any sequence.

Example 3:
Input:
s = "cb"
p = "? a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:
Input:
s = "adceb"
p = "* a * b"

Output: true
Explanation: the first "star" matches the substring while the second "matches"

Example 5:
Input:
s = "acdcb"
p = "a * c? b"
Output: false

3. This is a move.

Wow))) (sorry moderators), there was a task in which you need to implement a predicate. Miracles do not even have to do any input / output, which can be difficult in such an environment. The input types are simple, the output is boolean. Elementary.

While setting the citation icons in brief, I got acquainted with the task, we have a state machine, there is a chain of characters, it is a pattern, we must run through it and make a check, bypassing the state graph such that if we have reached the final vertex from the beginning, the answer is true. This is the task for the reverse search.

Then proceed, I write immediately a draft right here, then I will show the working version:
The string ... in the prologue is an important data type list, this concept is recursive, declaratively described, so you have to work with it, you need to turn the lines into lists of atoms. An atom, by the way, is not just a symbol, although it, too, an atom is a string with a small letter without spaces, for a Prolog it is a string constant, and no quotation marks can be used.

atom_to_list('',[]). %-      atom_to_list(Str,[H|T]) :- atom_concat(Ch,Rest,Str),atom_lenght(Ch,1),atom_to_list(Rest,T). %-  ,         

Sorry for my English, check it in the best on the current environment swi-prolog.org , there is an online editor, here:

Upps. That's what it means to not deceive anyone, this is a high entry threshold, references to library predicates are not correct. We are looking for the correct built-in predicates for working with atoms.
And in the picture there is a message that the variable H was unclaimed, some flaw in logic, the head of the list is the first character, and Ch must be in its place.

Here is some documentation:

atom_concat (? Atom1,? Atom2,? Atom3)
Atom3 forms the concatenation of Atom1 and Atom2. Must be instantiated to atoms. This predicate also allows for the mode (-, -, +), non-deterministically splitting> this 3rd argument into two parts (as append / 3 does for lists). SWI-Prolog allows for atomic arguments. Portable code must use atomic_concat / 3 if non-atom arguments are involved.

atom_length (+ Atom, -Length)
True if Atom. The SWI-Prolog version accepts all atomic types as well as code-lists and character-lists. It would be a good idea to avoid the number of characters.

3.1 Atom to atom list

Like this

3.2 The actual state machine

Imagine a graph that reads characters from a template and checks for matching characters in the input string. Solution Draft:

 %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn([],['*'|PatTail]):-test_pattrn([],PatTail). 

Let's make the final interface:
isMatch (S, P): - atom_to_list (S, SL), atom_to_list (P, PL),!, test_pattrn (SL, PL),!.

Here are all the examples from the problem statement:

4. Arbitrator

It seems the decision is ready, now we include the arbitrator. On the website leetcode.com (yes, yes, we solve the problem number 44), will receive tests, we will try to execute them consistently with our implementation. One bad luck, there do not accept programs on Prolog .

Nothing, one by one we get all the tasks:

 class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ if s=="aa" and p=="a":return False if s=="aa" and p=="*":return True if s=="cb" and p=="?a":return False if s=="adceb"and p=="*a*b":return True if s=="acdcb" and p=="a*c?b":return False if s=="aab" and p=="c*a*b":return False if s=="mississippi" and p=="m??*ss*?i*pi":return False if s=="aa" and p=="aa":return True if s=="aaa" and p=="aa":return False if s=="aa" and p=="a*":return True if s=="ab" and p=="?*":return True if s=="a" and p=="a":return True if s=="a" and p=="aa":return False if s=="aa" and p=="aaa":return False if s=="abefcdgiescdfimde" and p=="ab*cd?i*de":return True if s=="zacabz" and p=="*a?b*":return False if s=="leetcode" and p=="*e*t?d*":return False if s=="missingtest" and p=="mi*ing?s*t":return False if s=="aaaa" and p=="***a":return True if s=="" and p=="":return True if s=="" and p=="*":return True if s=="" and p=="a":return False if s=="" and p=="?":return False if s=="a" and p=="":return False if s=="a" and p=="a*":return True if s=="a" and p=="?*":return True if s=="a" and p=="*":return True if s=="b" and p=="?":return True if s=="b" and p=="??":return False if s=="bc" and p=="??":return True if s=="bcd" and p=="??":return False if s=="b" and p=="?*?":return False if s=="b" and p=="*?*?":return False if s=="b" and p=="*?*?*":return False if s=="c" and p=="*?*":return True if s=="cd" and p=="*?":return False if s=="cd" and p=="?":return False if s=="de" and p=="??":return True if s=="fg" and p=="???":return False if s=="hi" and p=="*?":return True if s=="ab" and p=="*a":return False if s=="aa" and p=="*a":return True if s=="cab" and p=="*ab":return True if s=="ab" and p=="*ab":return True if s=="ac" and p=="*ab":return False if s=="abc" and p=="*ab":return False if s=="cabab" and p=="ab*":return True if s=="cabab" and p=="*ab":return True if s=="ab" and p=="ab":return True if s=="ab" and p=="*?*?*":return True if s=="ac" and p=="ab":return False if s=="a" and p=="ab":return False if s=="abc" and p=="ab":return False if s=="" and p=="ab*":return False if s=="a" and p=="ab*":return False if s=="ab" and p=="ab*":return True if s=="ac" and p=="ab*":return False if s=="abc" and p=="ab*":return True if s=="" and p=="*a*":return False if s=="a" and p=="*a*":return True if s=="b" and p=="*a*":return True 

Here is a list of tests, someone tried well to enter such a checklist for this task.

And this is not all the tests, until we stop:

Here is the finished program, plus some tests:

 %-      atom_to_list('',[]). %-  ,         atom_to_list(Str,[Ch|T]) :- atom_concat(Ch,Rest,Str),atom_length(Ch,1), atom_to_list(Rest,T). is_letter(X):-X@>=a, X@=<z. %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail). isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!, test_pattrn(SL,PL),!. %unit-tests framework assert_are_equal(Goal, false):-not(Goal),!,writeln(Goal->ok). assert_are_equal(Goal, true):-Goal,!,writeln(Goal->ok). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %main goal :-assert_are_equal(isMatch(aa,a),false). :-assert_are_equal(isMatch(aa,'*'),true). :-assert_are_equal(isMatch(cb,'?a'),false). :-assert_are_equal(isMatch(adceb,'*a*b'),true). :-assert_are_equal(isMatch(acdcb,'a*c?b'),false). :-assert_are_equal(isMatch(aab,'c*a*b'),false). :-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false). :-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true). :-assert_are_equal(isMatch(zacabz,'*a?b*'),false). :-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false). :-assert_are_equal(isMatch(aaaa,'***a'),true). :-assert_are_equal(isMatch(b,'*?*?*'),false). 

Here are the test results:

 isMatch(aa, *)->ok isMatch(cb, ?a)->ok isMatch(adceb, *a*b)->ok isMatch(acdcb, a*c?b)->ok isMatch(aab, c*a*b)->ok isMatch(mississippi, m??*ss*?i*pi)->ok isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok isMatch(zacabz, *a?b*)->ok isMatch(leetcode, *e*t?d*)->ok isMatch(aaaa, ***a)->ok isMatch(b, *?*?*)->ok true 

5. Conclusion

Prolog as a workout for the mind. It's funny to solve problems on it, even though this solution did not have any optimization. Manually getting to more complex tests turned out to be very time consuming, and so far it was not possible to prove the completeness of the solution. And it seems to me that I have already reached the size of a habr article.

What example is this decision to fail?

How to you my call, inhabitants Habr?

You can compete by forcing your brains to solve problems and show interesting solutions, because programming is a creative process.