Hola, comunidad de desarrolladores , necesito terminar el trabajo.

En mi obra anterior , había una llamada para mostrar cómo se puede usar el lenguaje Prolog y para mostrar que sería divertido. Conviértalo en un ejercicio.

Trataré de continuar presumir para demostrar

Recuerdo brevemente la tarea:

No fue posible demostrar la integridad de la solución. En el sitio que proporciona la tarea hay 1808 pruebas que no se pueden ver de inmediato, debe escribir un programa y obtener otra prueba como error.

Hardcore, obtuve 66 de él y verifiqué mi decisión, mientras todo funcionaba. Pero no puede ser tan simple.

¿Por qué tantas pruebas, quiero comprobar más ...

Intentaré reescribir esta solución en el idioma comprensible disponible en este sistema (reflejan la popularidad de los lenguajes de programación modernos).

Entonces, elige Python.

El poder de Prolog está en el procedimiento de búsqueda, cuyas raíces están en los métodos de probar teoremas . En pocas palabras, tiene un mecanismo de unificación y búsqueda incorporado con un retorno. Es aún más simple decir que coinciden más la búsqueda en profundidad a través del árbol de decisiones.

Y Python es Pascal moderno (ya hay tres idiomas con la letra "P"), y los estudiantes pueden escribir programas en él.

Ahora volveré a escribir la solución que se estableció en la implementación anterior e implementaré rápidamente una búsqueda de prólogo similar con un retorno.

A continuación, lo iniciaré en el sistema de prueba y veré si el movimiento (código) fue correcto.

Únete ahora

En la entrada, la cadena y el patrón probados:

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 muy similar a la implementación de 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 soluciones, de lo contrario una mentira.

Pero, ¿cómo hacer una búsqueda con retorno? Para esto utilizo el rendimiento, como se le llama allí, cálculos inacabados (perezosos), cierre, un elemento del enfoque funcional, dígame ... Devolverá algo de lo que será posible obtener la siguiente solución, pero si Si no conduce a la respuesta correcta, entonces iremos a la rama del programa con el próximo rendimiento, esta es la diferencia con respecto al rendimiento.

Esta función aceptará el resultado de la primera prueba () si es verdadera, entonces todo está bien; de lo contrario, intentará iterar más y habrá una búsqueda en profundidad similar al comportamiento de la salida del prólogo.

Aquí, el retorno es específicamente necesario aquí:

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

Cheque 1

Wow, este es el resultado, "se aprobaron 939/1808 casos de prueba". y "Estado: límite de tiempo excedido".
Esto es exactamente lo que esperaba, una solución declarativa no siempre conduce a una implementación eficiente en el tiempo. La redacción transparente no es una redacción rápida.

Pero, aquí está el resultado de la pitón, probaremos la prueba abierta en la implementación del primer artículo y mediremos el tiempo:

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

El tiempo de ejecución de Python es 11.10963249206543 segundos, pero un poco demasiado.

Motor de prueba avanzado 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). 

Y aquí está el resultado del Prolog (comenzando no en el editor en línea, localmente, en el mismo hardware que el anterior):

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

Parece que no estoy usando Python bien ((, necesito mejorarlo, ya no es tan obvio:

 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) 

Aquí está el resultado: 3.921879768371582 seg. (Esto está más cerca del original). Regresamos al árbitro:

Y una vez mas.

Llego a la conclusión de que el paso total de las pruebas va más allá del plazo, porque las dos últimas opciones se resuelven muy rápidamente.

Necesitamos un orden de optimización de magnitud.

Comprobación 2. Necesitamos optimización.

Lo que suplica con seguridad es la búsqueda de amplitud.

No continúe con la decisión de cada rama hasta que obtengamos una mentira y regresemos a otra rama, pero mire las decisiones por niveles, bajando al mismo tiempo para cada opción y gradualmente vaya más allá.

Intentaré convertirlo en una pitón, y luego demostraré el 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 

Ya existe el resultado para la prueba 939, solo 0.01585698127746582 seg.
y ... URA se toma esta decisión

Prologo

Intentaré mostrar cómo implementar una búsqueda de amplitud, en una implementación declarativa. Para hacer esto, existen predicados especiales de segundo orden que pueden recopilar soluciones en una lista, por ejemplo bagof, setof, findall.

bolsa (+ Plantilla,: Meta, -Bolsa)
Unify Bag con las alternativas de Template. Si Goal tiene variables libres además de la que comparte con Template, bagof / 3 retrocederá sobre las alternativas de estas variables gratuitas, unificando Bag con las alternativas correspondientes de Template. La construcción + Var ^ Goal le dice a bagof / 3 que no enlace a Var en Goal. bagof / 3 falla si Goal no tiene soluciones.
setof (+ Plantilla, + Objetivo, -Set)
Equivale a bagof / 3, pero ordena el resultado usando sort / 2 para obtener una lista ordenada de alternativas sin duplicados.

El conjunto de predicados funciona bien desde él ya sabe cómo eliminar duplicados (en Python, tuve que aprender sobre conjuntos).

Entonces, haré un predicado que obtenga una solución de un nivel, luego lo recopilaré con otro predicado y profundizaré, aquí está la solución 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). 

Aquí puede ver que la regla que previamente realizó la búsqueda por la plantilla, como si hiciera una transición a lo largo de la cara en el gráfico, ahora se ha convertido en un conjunto de patrones que contienen posibles transiciones (relaciones entre estados): esta es una descripción del gráfico y no un código que lo implementa.

Y la ejecución resulta con tiempo en 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 

Y esta ya es una solución exitosa, no solo lógicamente sino también a tiempo.

Conclusiones

En un artículo anterior, quería ver interés en el tema de un enfoque declarativo. El tema "niasilil tal enfoque" se abrió de inmediato, pero aún se puede mostrar interés. Aquí demostré que hay un problema de rendimiento, lo que está escrito claramente no funciona rápidamente. Los intentos de crear un prólogo paralelo no tuvieron éxito. Quizás aquí está la pregunta del futuro, ¿puede una computadora cuántica?
Total utilizamos acertijos en el sitio anterior para un pasatiempo agradable sabiamente.

Bueno, la próxima vez, habrá un intento de resolver de inmediato una tarea difícil más de manera efectiva.