嗨，居民，是时候谈谈声明式编程了。这是当您在该研究所受到困扰时，无法对程序进行编码，而只能制定程序。这与现在所有编程语言中的命令式相反。让我们归功于功能性方法，这里是兄弟般的功能，它正在越来越深入地研究现代性，这里您有C ++和javascript的lambda，也许是Haskell吗？

但是令人遗憾的是，逻辑，高效的编程只能在Prolog上表示。

在这里，我将对habr效果提出一个有趣的想法。为什么不写一篇有关解决编程问题的文章。因此，我认为有很多帖子。我参加主题的选择。这是参与者之间发展和竞争的原始，新的方向，我们展示了我们如何才能解决问题，使所有读者都有兴趣表达意见并指出错误，因为您有足够的javascript和C ++专家，也许化解仍然存在...

总而言之，本文的目的是 ：在撰写本文时，解决在文章开头尚未解决的问题，并显示您的思想代码，并通过迁移和收到的可行解决方案确认这一点。但是对于此检查，您需要一名仲裁员，您自己不会进行审查。我将以这个角色选择leetcode.com 。

1.所以

在这里，我们选择最困难的任务，并尝试在Prolog上解决它，有必要证明它的娱乐性。

2.任务44.通配符匹配

给定一个输入字符串（s）和一个模式（p），实现通配符模式匹配并支持'？' 和“ *”。

'？' 匹配任何单个字符。
'*'匹配任何字符序列（包括空序列）。
匹配项应覆盖整个输入字符串（而非部分）。

注意事项：

s可以为空，并且仅包含小写字母az。
p可以为空，仅包含小写字母az和类似字符？或*。
范例1：
输入：
s =“ aa”
p =“ a”
输出：假
说明：“ a”与整个字符串“ aa”不匹配。

范例2：
输入：
s =“ aa”
p ='*'
输出：真

说明：'*'匹配任何序列。

范例3：
输入：
s =“ cb”
p =“？a”
输出：假
说明：“？” 匹配“ c”，但第二个字母是“ a”，不匹配“ b”。

范例4：
输入：
s =“ adceb”
p =“ * a * b”

输出：真
说明：第一个“ star”匹配空序列，而第二个*匹配子串“ dce”。

范例5：
输入：
s =“ acdcb”
p =“ a * c？b”
输出：假

3.这是举动

哇）））（主持人对不起），有一项任务需要实现谓词。奇迹，您甚至不必执行任何I / O，在这种环境下这可能很困难。在输入处为简单类型；在输出处为布尔值。小学的。

在设置引用图标时，我简短地熟悉了这个任务，我们有一个有限的状态机，有一个字符链，它是一个模板，我们需要检查它，进行检查，绕过状态图，所以如果我们到达顶点的末尾，那么答案是正确的。这是反向搜索的任务。

然后继续，我立即在此处编写草稿，然后显示工作版本：
序言中的一行...，重要的数据类型是列表，这是一个递归概念，以声明方式进行了描述，因此您需要使用它，需要将字符串转换为原子列表。顺便说一下，一个原子不仅是一个符号，尽管它也是一个符号，它是一个带有小字母且没有空格的字符串，对于Prolog来说，它是字符串常量，您不能加上任何引号。

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

对不起，我的英语，我们会在目前最好的环境swi-prolog.org中进行检查，这里有一个在线编辑器，位于：

哎呀这就是不欺骗任何人的意思，进入的门槛很高，对库谓词的调用不正确。我们正在寻找使用原子的正确内置谓词。
在图片中，有一条消息表明变量H原来是无人认领的，这在逻辑上有些缺陷，列表的开头是第一个字符，而在其位置应为Ch 。

这里是一些文档：

atom_concat（？Atom1，？Atom2，？Atom3）
Atom3构成Atom1和Atom2的串联。参数中的至少两个必须实例化为原子。该谓词还允许使用模式（-，-，+），将第3个参数不确定地拆分为两个部分（如append / 3表示列表）。 SWI-Prolog允许使用原子参数。如果涉及非原子参数，则可移植代码必须使用atomic_concat / 3。

atom_length（+ Atom，-Length）
如果Atom是Length字符的原子，则为True。 SWI-Prolog版本接受所有原子类型，以及代码列表和字符列表。新代码应避免使用此功能，并使用write_length / 3来>获取将参数传递给write_term / 3时要写入的字符数。

3.1原子列表中的原子

像这样

3.2状态机本身

想象一下一个图形，该图形从模板读取字符并检查是否符合输入行中的字符。解决方案草案：

 %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).

让我们做最后一个界面：
isMatch（S，P）：-atom_to_list（S，SL），atom_to_list（P，PL），！，test_pattrn（SL，PL），！。

这里是问题陈述的所有示例：

4.仲裁员

似乎已经准备好决定，现在我们打开仲裁程序。在leetcode.com网站上（是的，是的，我们解决了问题编号44），我们将收到测试，我们将尝试按实现顺序依次执行它们。不幸的是，他们不接受Prolog上的程序。

一无所有，我们将一一完成所有任务：

 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

这是测试列表，有人通过将此类检查表引入此问题来进行了艰苦的尝试。

在我们停止之前，这些还不是全部测试：

这是完成的程序，加上一些测试：

 %-      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).

测试结果如下：

 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.结论

Prolog就像是锻炼大脑。解决此问题很有趣，尽管该解决方案没有任何优化。手动进行更复杂的测试非常费力，到目前为止，尚无法证明解决方案的完整性。在我看来，我已经达到了habr文章的大小。

这个决定失败的例子是什么？

哈勃（Habr）的居民你喜欢我的电话吗？

因为编程是一个富有创造力的过程，所以您可以使自己的大脑解决问题并显示有趣的解决方案来竞争。

有趣的序幕