Hola residentes , es hora de hablar sobre programación declarativa. Esto es cuando te rozaron en el instituto que los programas no pueden codificarse, sino formularse. Esto es lo opuesto a imperativo, que ahora está en todos los lenguajes de programación. Vamos a rendir homenaje al enfoque funcional, aquí es fraternal, y está haciendo su trabajo cada vez más en la modernidad, aquí tienes lambdas en C ++ y javascripts, ¿tal vez un Haskell?

Pero lo triste es con una programación lógica y productiva, que solo se puede representar en Prolog .

Aquí voy a arrojar un pensamiento interesante para el efecto habr. ¿Por qué no escribir un artículo sobre cómo resolver un problema de programación? Entonces, creo que muchas publicaciones resultaron. Me uno a la selección de temas. Aquí hay una nueva y original dirección de desarrollo y competencia entre los participantes, mostramos cómo exactamente podemos resolver los problemas, de modo que todos los lectores estén interesados ​​en expresar sus opiniones y señalar sus errores, porque tiene suficientes especialistas en JavaScript y C ++, tal vez las pitognosas todavía se encuentran ...

En total, el propósito del artículo : resolver al momento de escribir el artículo un problema que aún no se conocía al principio de la publicación y mostrar su código de pensamiento, confirmando esto con el curso y la solución de trabajo recibida. Pero para esta verificación necesita un árbitro, usted mismo no se revisa. Elegiré leetcode.com en este rol.

1. Entonces

Aquí seleccionamos la tarea más cercana a las más difíciles e intentamos resolverla en Prolog, es necesario demostrar cuán entretenida es.

2. Tarea 44. Coincidencia de comodines

Dadas una (s) cadena (s) de entrada y un patrón (p), implemente la coincidencia de patrones comodín con soporte para '?' y '*'.

'?' Coincide con cualquier personaje individual.
'*' Coincide con cualquier secuencia de caracteres (incluida la secuencia vacía).
La coincidencia debe cubrir toda la cadena de entrada (no parcial).

Nota:

s podría estar vacío y contiene solo letras minúsculas az.
p podría estar vacío y contiene solo letras minúsculas az y caracteres como? o *.
Ejemplo 1:
Entrada:
s = "aa"
p = "a"
Salida: falso
Explicación: "a" no coincide con la cadena completa "aa".

Ejemplo 2
Entrada:
s = "aa"
p = '*'
Salida: verdadero

Explicación: '*' coincide con cualquier secuencia.

Ejemplo 3
Entrada:
s = "cb"
p = "? a"
Salida: falso
Explicación: '?' coincide con 'c', pero la segunda letra es 'a', que no coincide con 'b'.

Ejemplo 4
Entrada:
s = "adceb"
p = "* a * b"

Salida: verdadero
Explicación: La primera "estrella" coincide con la secuencia vacía, mientras que la segunda * coincide con la subcadena "dce".

Ejemplo 5:
Entrada:
s = "acdcb"
p = "a * c? b"
Salida: falso

3. Este es el movimiento

Wow))) (los moderadores me disculpan), hubo una tarea en la que es necesario implementar un predicado. Milagros, ni siquiera tiene que hacer ninguna E / S, lo que puede ser difícil en ese entorno. En la entrada, tipos simples; en la salida, booleana. Elemental

Mientras ponía iconos de citas, me familiaricé brevemente con la tarea, tenemos una máquina de estados finitos, hay una cadena de caracteres, es una plantilla, debemos revisarla y hacer una verificación, omitir el gráfico de estado, de modo que si llegamos al final del vértice, la respuesta es verdadera. Esta es la tarea para la búsqueda inversa.

Luego proceda, escribo inmediatamente un borrador aquí, luego mostraré una versión funcional:
Una línea ... en el prólogo, un tipo de datos importante es una lista, es un concepto recursivo, descrito de forma declarativa, por lo que debe trabajar con él, debe convertir las cadenas en listas de átomos. Un átomo, por cierto, no es solo un símbolo, aunque también lo es, un átomo es una cadena con una letra pequeña sin espacios, para Prolog son constantes de cadena y no se pueden poner comillas.

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

Perdón por mi inglés, lo revisaremos en el mejor entorno actualmente, swi-prolog.org , hay un editor en línea, aquí:

Ups Esto es lo que significa no engañar a nadie, es un umbral de entrada alto, las llamadas a los predicados de la biblioteca no son correctas. Estamos buscando los predicados incorporados correctos para trabajar con átomos.
Y en la imagen hay un mensaje de que la variable H no fue reclamada, alguna falla en la lógica, el encabezado de la lista es el primer carácter, y en su lugar debería ser Ch .

Aquí hay alguna documentación:

atom_concat (? Atom1 ,? Atom2 ,? Atom3)
Atom3 forma la concatenación de Atom1 y Atom2. Al menos dos de los argumentos deben ser instanciados a átomos. Este predicado también permite el modo (-, -, +), dividiendo de forma no determinista> el tercer argumento en dos partes (como append / 3 para las listas). SWI-Prolog permite argumentos atómicos. El código portátil debe usar atomic_concat / 3 si hay argumentos que no sean átomos.

Atom_length (+ Atom, -Length)
Verdadero si Atom es un átomo de caracteres de longitud. La versión SWI-Prolog acepta todos los tipos atómicos, así como listas de códigos y listas de caracteres. El nuevo código debe evitar esta característica y usar write_length / 3 para> obtener el número de caracteres que se escribirían si el argumento se entregara a write_term / 3.

3.1 Atom en la lista de átomos

Como este

3.2 La máquina de estado en sí

Imagine un gráfico que lee caracteres de una plantilla y verifica el cumplimiento de los caracteres en la línea de entrada. Proyecto de soluciones:

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

Hagamos la interfaz final:
isMatch (S, P): - atom_to_list (S, SL), atom_to_list (P, PL),!, test_pattrn (SL, PL),!.

Aquí están todos los ejemplos del enunciado del problema:

4. Árbitro

Parece que la decisión está lista, ahora activamos al árbitro. En el sitio leetcode.com (sí, sí, resolvemos el problema número 44), recibiremos pruebas, intentaremos ejecutarlas secuencialmente con nuestra implementación. Una mala suerte, no aceptan programas en Prolog .

Nada, obtendremos todas las tareas una por una:

 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 

Aquí hay una lista de pruebas, alguien se esforzó al introducir dicha lista de verificación para este problema.

Y estas no son todas las pruebas, hasta que nos detenemos:

Aquí está el programa terminado, más algunas pruebas:

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

Aquí están los resultados de la prueba:

 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. Conclusión

Prolog es como un entrenamiento para la mente. Es divertido resolver problemas, aunque esta solución no tenía ninguna optimización. Llegar manualmente a pruebas más complejas resultó ser muy laborioso, hasta ahora no ha sido posible demostrar la integridad de la solución. Y me parece que ya llegué al tamaño de un artículo habr.

¿En qué ejemplo es esta decisión fallar?

¿Qué les parece mi llamado, los habitantes de Habr?

Puedes competir haciendo que tus cerebros resuelvan problemas y muestren soluciones interesantes, porque la programación es un proceso creativo.