Olá, comunidade de desenvolvedores , preciso terminar o trabalho.

Na minha obra anterior , houve um telefonema para mostrar como a linguagem Prolog pode ser usada e para mostrar que seria engraçado. Transforme-o em um exercício.

Vou tentar continuar mostrar para demonstrar.

Lembro-me brevemente da tarefa:

Não foi possível provar a integridade da solução. No site que fornece a tarefa, existem 1808 testes que não podem ser vistos imediatamente, você precisa escrever um programa e fazer outro teste como erro.

Hardcore, consegui 66 dele e verifiquei minha decisão - enquanto tudo funcionava. Mas não pode ser assim tão simples.

Por que tantos testes, quero verificar mais ...

Vou tentar reescrever esta solução no idioma compreensível disponível neste sistema (eles refletem a popularidade das linguagens de programação modernas).

Então, escolha Python.

O poder do Prolog está no procedimento de busca, cujas raízes estão nos métodos de provar teoremas . Simplificando, ele possui um mecanismo de unificação e pesquisa embutido com um retorno. É ainda mais simples dizer correspondência e pesquisa de profundidade através da árvore de decisão.

E o Python é o Pascal moderno (já existem três idiomas com a letra "P"), e os alunos podem escrever programas nele.

Agora, reescreverei a solução estabelecida na implementação anterior e implementarei rapidamente uma pesquisa de prólogo semelhante com um retorno.

Em seguida, iniciá-lo-ei no sistema de teste e verei se a movimentação (código) estava correta.

Inscreva-se agora.

Na entrada, a sequência e o padrão testados:

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 

Parece ser muito semelhante à implementação do Prolog:

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

Cinco soluções, caso contrário, uma mentira.

Mas como fazer uma pesquisa com retorno ?, para isso eu uso yield, como é chamado lá, cálculos inacabados (preguiçosos), fechamento, um elemento da abordagem funcional, diga-me ... Ele retornará algo do qual será possível buscar a solução a seguir, mas se Se isso não levar à resposta correta, iremos para a ramificação do programa com o próximo rendimento, essa é a diferença do retorno.

Essa função aceitará o resultado do primeiro teste () se for verdade, tudo está bem; caso contrário, ele tentará iterar novamente e haverá uma pesquisa profunda semelhante ao comportamento da saída do prólogo.

Aqui, o retorno é especificamente necessário aqui:

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

Verificação 1

Uau, este é o resultado, "939/1808 casos de teste foram aprovados". e "Status: limite de tempo excedido".
Isso é exatamente o que eu esperava, uma solução declarativa nem sempre leva a uma implementação com tempo eficiente. As palavras transparentes não são rápidas.

Mas, aqui está o resultado do python, testaremos o teste aberto na implementação desde o primeiro artigo e mediremos o tempo:

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

O tempo de execução do Python é 11,10963249206543 seg., Mas um pouco demais.

Mecanismo de teste avançado para Prolog:

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

E aqui está o resultado do Prolog (começando não no editor on-line, localmente, no mesmo hardware que o anterior):

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

Parece que não estou usando bem o python ((, preciso aprimorá-lo, não é mais tão óbvio:

 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) 

Aqui está o resultado: 3.921879768371582 seg. (isso é mais próximo do original). Voltamos ao árbitro:

E mais uma vez.

Concluo que a passagem total dos testes ultrapassa o prazo, porque as duas últimas opções são resolvidas muito rapidamente.

Precisamos de uma ordem de otimização de magnitude.

Verificação 2. Precisamos de otimização.

O que implora com certeza é a busca pela primeira vez.

Não continue a decisão de cada ramo até que possamos mentir e retornar a outro ramo, mas observe as decisões por níveis, descendo ao mesmo tempo para cada opção e gradualmente indo além.

Vou tentar transformá-lo em python e depois demonstrarei o prólogo.

 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 

Já existe o resultado para o teste 939, apenas 0,01585698127746582 seg.
e ... URA esta decisão é tomada

Prólogo

Vou tentar mostrar como implementar uma pesquisa abrangente, em uma implementação declarativa. Para fazer isso, existem predicados especiais de segunda ordem que podem coletar soluções em uma lista, por exemplo, bagof, setof, findall.

bagof (+ Modelo ,: Objetivo, -Bag)
Unifique o Bag com as alternativas do Template. Se o Objetivo tiver variáveis ​​livres além da compartilhada com o Modelo, o bagof / 3 retornará às alternativas dessas variáveis ​​livres, unificando o Saco às alternativas correspondentes do Modelo. A construção + Var ^ Objetivo diz ao bagof / 3 para não vincular Var no Objetivo. bagof / 3 falhará se a meta não tiver soluções.
setof (+ Modelo, + Objetivo, -Set)
Equivalente a bagof / 3, mas classifica o resultado usando sort / 2 para obter uma lista classificada de alternativas sem duplicatas.

O predicado Setof funciona bem desde ele já sabe como remover duplicatas (em python, eu tive que aprender sobre conjuntos).

Então, criarei um predicado que obtém uma solução de um nível, coleciono-o com outro predicado e vou mais fundo, eis a solução completa:

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

Aqui você pode ver que a regra que anteriormente executou a pesquisa pelo modelo, como se estivesse fazendo uma transição ao longo da face no gráfico, agora se transformou em um conjunto de fatos que contêm possíveis transições (relações entre estados) - essa é uma descrição do gráfico e não um código que o implementa.

E a execução resulta com tempo em segundos:

 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 

E essa já é uma solução bem-sucedida, não apenas logicamente, mas também com o tempo.

Conclusões

Em um artigo anterior, eu queria ver interesse no tópico de uma abordagem declarativa. O tópico "niasilil tal abordagem" foi aberto imediatamente, mas o interesse ainda pode ser demonstrado. Aqui eu mostrei que há um problema de desempenho, o que está escrito claramente não funciona rapidamente. Tentativas de criar um prólogo paralelo não tiveram êxito. Talvez aqui esteja a questão do futuro, pode um computador quântico?
Total usamos quebra-cabeças no site acima para um passatempo agradável com sabedoria.

Bem, da próxima vez, haverá uma tentativa de resolver imediatamente mais uma tarefa difícil de maneira eficaz.