Привет, сообщество разработчиков, надо довести дело до конца.

В предыдущем моем опусе был вызов показать как можно использовать язык Пролог, да и показать что бы это было забавно. Превратить это в упражнение.

Попробую продолжить выпендриваться демонстрировать.

Коротко напомню задачу:

Доказать полноту решения не удалось. На сайте, который предоставляет задание есть 1808 тестов, которые сразу увидеть нельзя, нужно написать программу и получить как ошибку очередной тест.

Хардкорно я получил от него 66 и проверил свое решение — пока все работало. Но не может быть все так просто.

Зачем было делать так много тестов, хочу проверить дальше...

Попробую переписать данное решение на языке понятном доступном в этой системе (они отражают популярность языков программирования современности).

Итак, выбираю Питон.

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

А Питон это современный Паскаль (что-то уже три языка на букву "П")), писать на нем программы доступно и школьникам.

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

Далее запущу его в систему тестирования, и увижу верен ли был ход(код).

Присоединяйтесь.

На входе тестируемая строка и шаблон:

def test(st,pat):
    if st=="" and pat=="": yield True
    if pat>"" and pat[0]=='*':yield test(st,pat[1:])
    if st>"" and pat>"":
        if st[0]==pat[0] or pat[0]=='?': yield test(st[1:],pat[1:])
        if pat[0]=='*':yield test(st[1:],pat)
    yield False 

Вроде получилось очень похоже на реализацию Пролога:

test_pattrn([],[]). 
test_pattrn([Ch|UnpTail],[Ch|PatTail]):-test_pattrn(UnpTail,PatTail).
test_pattrn([Ch|UnpTail],['?'|PatTail]):-test_pattrn(UnpTail,PatTail).
test_pattrn([Ch|UnpTail],['*'|PatTail]):-test_pattrn(UnpTail,['*'|PatTail]).
test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail).

Пять вариантов решения, иначе ложь.

Но как сделать поиск с возвратом?, для этого использую yield, как его там называют, неоконченные(ленивые) вычисления, замыкание, элемент функционального подхода, подскажите… Он будет возвращать что-то, из чего можно будет выудить следующее решение, но если оно не приведет к правильному ответу, то перейдем на ветку программы со следующим yield, в этом и отличие от return.

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

Вот, тут уже конкретно нужен return:

def run(r):
    if type(r)==bool:
        if r==True: return True
    else:
        for nr in r:
            if run(nr):return True
    return False  

Проверяем 1

Ого, вот это результат, "939 / 1808 test cases passed." и "Status: Time Limit Exceeded".
Именно этого я и ждал, декларативное решение не всегда приводит к эффективной по времени выполнения реализации. Прозрачная формулировка это не быстрая формулировка.

Но, тут результат питона, опробуем открывшийся тест в реализации из первой статьи, и замерим время:

import time
pt=time.time()
print(run(test("babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab","***bba**a*bbba**aab**b")))
print(time.time()-pt)

Время выполнения Питоном 11.10963249206543 сек., да-а многовато.

Усовершенствованный механизм тестирования для Пролога:

%unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is Fin-St,writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal,     !,get_time(Fin),Per is Fin-St,writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).

:-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true).

И вот такой результат Пролога (запуская не в онлайн-редакторе, локально, на одном железе с предыдущим):

isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,*ab***ba**b*b*aaab*b)->ok:2.208951950073242/sec

Похоже я плохо пользуюсь питоном ((, надо усовершенствовать, уже не так наглядно:

def test(st,pat):
    if st==pat: return True
    if pat>"" and pat[0]=='*':
        if test(st,pat[1:]):return True
    if st>"" and pat>"":
        if st[0]==pat[0] or pat[0]=='?':
            if test(st[1:],pat[1:]):return True
        if pat[0]=='*':
            if test(st[1:],pat):return True
    return False 

import time
pt=time.time()
print(test("babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab","***bba**a*bbba**aab**b"))
print(time.time()-pt)

Вот результат: 3.921879768371582 сек. (это уже ближе к исходному). Возвращаемся к арбитру:

И еще раз.

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

Нужна оптимизация на порядок.

Проверяем 2. Нужна оптимизация.

Что напрашивается, точно — поиск в ширину.

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

Попробую сделать это питоном, а потом продемонстрирую пролог.

def test(st,pat):
    if st==pat: return True
    res=[] #буду собирать все варианты перехода вглубь, это уровни дерева
    if pat>"" and pat[0]=='*':res+=[(st,pat[1:])]
    if st>"" and pat>"":
        stt=st[1:]
        if st[0]==pat[0] or pat[0]=='?':res+=[(stt,pat[1:])]
        if pat[0]=='*':res+=[(stt,pat)]
    return res

def run(st,pat):
    lev=[(st,pat)]
    while len(lev)!=0:
        nxt=set() ##все нижележащие решения соберем в множество без дублей
        for s,p in lev:
            one=test(s,p)
            if one==True:return True
            else:nxt.update(set(one))
        lev=nxt
    return False

Тут уже результат для теста 939, всего 0.01585698127746582 сек.
и..., УРА это решение принимается

Пролог

Попробую показать, как реализовать поиск в ширину, в декларативной реализации. Для этого есть специальные предикаты второго порядка, которые могут собрать решения в список, например bagof, setof, findall.

bagof(+Template, :Goal, -Bag)
Unify Bag with the alternatives of Template. If Goal has free variables besides the one sharing with Template, bagof/3 will backtrack over the alternatives of these free variables, unifying Bag with the corresponding alternatives of Template. The construct +Var^Goal tells bagof/3 not to bind Var in Goal. bagof/3 fails if Goal has no solutions.
setof(+Template, +Goal, -Set)
Equivalent to bagof/3, but sorts the result using sort/2 to get a sorted list of alternatives without duplicates.

Хорошо подходит предикат setof т.к. он уже умеет удалять дубли (в питоне для этого пришлось узнать о множествах).

Итак, сделаю предикат который получает решение одного уровня, далее собираем это другим предикатом и углубляемся, вот полное решение:

atom_to_list(Str,[Ch|T]) :-
    atom_concat(Ch,Rest,Str),atom_length(Ch,1),
    atom_to_list(Rest,T).

%варианты переходов
pattrn(X:X,true). %- все хорошо когда оба одинаковые
pattrn([Ch|UnpTail]:[Ch|PatTail],UnpTail:PatTail).
pattrn([_|UnpTail]:['?'|PatTail],UnpTail:PatTail).
pattrn([_|UnpTail]:['*'|PatTail],UnpTail:['*'|PatTail]).
pattrn(Str:['*'|PatTail],Str:PatTail).

%если попался true, значит более искать не надо, иначе проверка уровня ниже
next_level(Lev):-member(true,Lev),!.
next_level(Lev):-setof(One,SP^(member(SP,Lev),pattrn(SP,One)),Next),!,
                         next_level(Next).

test_pattrn(Str,Pat):-next_level([Str:Pat]).

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):-get_time(St),not(Goal),!,get_time(Fin),Per is Fin-St,
          writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal,     !,get_time(Fin),Per is Fin-St,
          writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).

%all test
:-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).
:-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true).
:-assert_are_equal(isMatch(abbbbbbbaabbabaabaa,'*****a*ab'),false).
:-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true).
:-assert_are_equal(isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab,'***bba**a*bbba**aab**b'),false).

Тут видно, что правило, которое ранее выполняло поиск по шаблону, как бы делало переход по грани в графе, теперь превратилось в набор фактов pattrn, которые содержат возможные переходы (связи между состояниями) — это описание графа, а не код его реализующий.

И результаты выполнения с временем в сек.:

isMatch(aa, a)->ok:0.00010013580322265625/sec
isMatch(aa, *)->ok:4.00543212890625e-5/sec
isMatch(cb, ?a)->ok:3.981590270996094e-5/sec
isMatch(adceb, *a*b)->ok:0.0001399517059326172/sec
isMatch(acdcb, a*c?b)->ok:9.989738464355469e-5/sec
isMatch(aab, c*a*b)->ok:4.00543212890625e-5/sec
isMatch(mississippi, m??*ss*?i*pi)->ok:0.0003399848937988281/sec
isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok:0.0003600120544433594/sec
isMatch(zacabz, *a?b*)->ok:9.989738464355469e-5/sec
isMatch(leetcode, *e*t?d*)->ok:0.00020003318786621094/sec
isMatch(aaaa, ***a)->ok:9.989738464355469e-5/sec
isMatch(b, *?*?*)->ok:6.008148193359375e-5/sec
isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab, *ab***ba**b*b*aaab*b)->ok:0.0040400028228759766/sec
isMatch(abbbbbbbaabbabaabaa, *****a*ab)->ok:0.0006201267242431641/sec
isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab, *ab***ba**b*b*aaab*b)->ok:0.003679990768432617/sec
isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab, ***bba**a*bbba**aab**b)->ok:0.002460002899169922/sec

И это уже успешное решение не только логически но и по времени.

Выводы

В предыдущей статье, я хотел увидеть интерес к теме декларативного подхода. Тема "ниасилил такой подход" сразу открылась, все же интерес проявить можно. Тут я показал, что есть проблема производительности, то что написано ясно не работает быстро. Попытки создать параллельный пролог успешностью не завершились. Может тут вопрос будущего, квантовый компьютер сможет??
Итого используем задачки, на вышеуказанном сайте, для приятного времяпровождения с умом.

Ну и в следующий раз, будет попытка сразу решить эффективно еще одну из хард-задач.