Хабрахабр

[Из песочницы] Занимательный пролог

Это когда вам в институте втирали, что программы можно не кодить, а формулировать. Привет, жители, пришло время поговорить про декларативное программирование. Отдадим должное функциональному подходу, он тут братский, и дело свое делает все глубже проникая в современность, вот вам и лямбды в си++ и яваскрипты, может хаскел? Это противоположность императивности, которая сейчас во всех языках программирования.

Но грустнее дело обстоит с логическим, продукционным программированием, которое можно представить только на Prolog.

Почему бы не написать статью про решение программистской задачки. Вот собираюсь подкинуть интересную мыслишку для хабр-эффекта. Присоединяюсь к выбору темы. Так, думаю, много постов и получилось. Вот оригинальное, новое направление развития и соревнования между участниками, показываем, как именно мы можем решать задачи, так чтобы всем читающим было интересно выразить свое мнение, и указать на твои ошибки, потому как в яваскрипт и си++ у вас тут спецов достаточно, может питонознавы еще попадаются...

Но для этой проверки нужен арбитр, сам себя не рецензируешь-то. Итого цель статьи: решить во время написания статьи задачу, которая была еще не известна на начало поста и показать свой код мысли, подтвердив это ходом и полученным рабочим решением. Выберу в этой роли leetcode.com.

Тут выбираем ближайшее к самым сложным задание, и пытаемся его решить на Prolog, необходимо продемонстрировать насколько он занимателен.

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

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

Note:

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

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 empty sequence, while the second * matches the substring "dce".

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

Чудеса, не придется даже делать никакого ввода/вывода, который может быть затруднителен в такой среде. Вот это да ))) (модераторы извините), выпала задача в которой необходимо реализовать предикат. Элементарно. На входе простые типы, на выходе булево.

Это и есть задача для обратного поиска. Пока выставлял значки цитирования вкратце ознакомился с заданием, перед нами конечный автомат, есть цепочка символов она же шаблон, надо пробежаться по ней и сделать проверку, обход графа состояний такой, если достигли от начала конечной вершины, то ответ истина.

Атом, между прочим, это не просто символ, хотя он тоже, атом это строка с маленькой буквы без пробелов, для Пролога это строковые константы и никаких кавычек можно не ставить. Тогда приступаем, пишу сразу же черновик прям сюда, далее покажу рабочий вариант:
Строка… в прологе важный тип данных список, это понятие рекурсивное, декларативно описанное, поэтому с ним и надо работать, нужно превратить строки в списки атомов.

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, там есть онлайн редактор, вот:
image
Уппс. Ищем правильные встроенные предикаты для работы с атомами.
И на картинке сообщение, что переменная H оказалась невостребована, какой-то недостаток в логике, голова списка это первый символ, а на ее месте должна быть Ch.

Вот немного документации:

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

The SWI-Prolog version accepts all atomic types, as well as code-lists and character-lists. atom_length(+Atom, -Length)
True if Atom is an atom of Length characters. New code should avoid this feature and use write_length/3 to > get the number of characters that would be written if the argument was handed to write_term/3.

Вот так

Черновик решения: Вообразим себе такой граф, который читает символы из шаблона и проверяет на соответствие символам во входной строке.

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

Вот все примеры из постановки задачи:

На сайте 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

Забавно на нем решать задачи, хоть данное решение и не обладало никакой оптимизацией. Prolog как разминка для ума. А до размера хабр-статьи мне кажется я уже добрался. Добраться вручную до более сложных тестов, оказалось очень трудоемко, доказать полноту решения пока не удалось.

На каком примере это решение провалиться?

Как вам мой вызов, жители Хабра?

Можно посоревноваться, заставив свои мозги решать задачи и показывать интересные решения, ведь программирование это процесс творческий.

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»