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 deeper and deeper into modernity, so you and lambda in C ++ and javascripts, can haskel?

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 everyone reading it would be interesting to express their opinion 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 task, 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, an arbiter is needed, you are not reviewing yourself. I will select leetcode.com in this role .

1. So

Here we choose 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

The wildcard pattern for the? and '*'.

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

Note:

s Could the BE empty and the 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 = '*'


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: for the first * matches the substring "dce".

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 we start, I write immediately a draft right here, then I will show the working version:
String ... in the prologue an important data type is a list, this is a recursive concept, declaratively described, so you need 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. This is 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 is the atom of Length characters. 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:

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

Here is a list of tests, someone tried well by entering such a checklist to 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 anysequenceof 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, although this solution did not have any optimization. Manually getting to more complex tests turned out to be very time consuming, and so far it has not been 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.