Salut les résidents , il est temps de parler de programmation déclarative. C'est à ce moment-là qu'on vous a frotté à l'institut que les programmes ne peuvent pas être codés, mais formulés. C'est l'opposé de l'impératif, qui est désormais présent dans tous les langages de programmation. Rendons hommage à l'approche fonctionnelle, elle est fraternelle ici, et elle fait son travail de plus en plus profondément dans la modernité, ici vous avez des lambdas en C ++ et des javascripts, peut-être un Haskell?
Mais le plus triste, c'est la programmation logique et productive, qui ne peut être représentée que sur Prolog .
Ici, je vais lancer une pensée intéressante pour l'effet habr. Pourquoi ne pas écrire un article sur la résolution d'un problème de programmation. Donc, je pense que beaucoup de messages se sont révélés. Je rejoins la sélection des sujets. Voici une nouvelle direction originale de développement et de concurrence entre les participants, nous montrons exactement comment nous pouvons résoudre les problèmes, afin que tous les lecteurs soient intéressés à exprimer leurs opinions et à signaler vos erreurs, car vous avez suffisamment de spécialistes en javascript et C ++, peut-être que les pythognoses se rencontrent encore ...
Au total, le but de l'article : résoudre au moment de la rédaction de l'article un problème qui n'était pas encore connu au début de la publication et montrer votre code de pensée, le confirmant avec le cours et la solution de travail reçue. Mais pour cette vérification vous avez besoin d'un arbitre, vous ne vous révisez pas vous-même. Je choisirai leetcode.com dans ce rôle.
1. Donc
Ici, nous sélectionnons la tâche la plus proche des plus difficiles et essayons de la résoudre sur Prolog, il est nécessaire de démontrer à quel point elle est divertissante.
2. Tâche 44. Correspondance générique
Étant donné une ou plusieurs chaînes d'entrée et un modèle (p), implémentez une correspondance de modèle générique avec la prise en charge de '?' et '*'.
'?' Correspond à n'importe quel caractère unique.
'*' Correspond à n'importe quelle séquence de caractères (y compris la séquence vide).
La correspondance doit couvrir toute la chaîne d'entrée (non partielle).
Remarque:
s peut être vide et ne contient que des lettres minuscules az.
p pourrait être vide et ne contient que des lettres minuscules az et des caractères comme? ou *.
Exemple 1:
Entrée:
s = "aa"
p = "a"
Sortie: faux
Explication: "a" ne correspond pas à la chaîne entière "aa".
Exemple 2:
Entrée:
s = "aa"
p = '*'
Sortie: vrai
Explication: '*' correspond à n'importe quelle séquence.
Exemple 3:
Entrée:
s = "cb"
p = "? a"
Sortie: faux
Explication: '?' correspond à «c», mais la deuxième lettre est «a», ce qui ne correspond pas à «b».
Exemple 4:
Entrée:
s = "adceb"
p = "* a * b"
Sortie: vrai
Explication: La première "étoile" correspond à la séquence vide, tandis que la seconde * correspond à la sous-chaîne "dce".
Exemple 5:
Entrée:
s = "acdcb"
p = "a * c? b"
Sortie: faux
3. C'est le mouvement
Wow))) (les modérateurs m'excusent), il y avait une tâche dans laquelle il était nécessaire d'implémenter un prédicat. Miracles, vous n’avez même pas à faire d’E / S, ce qui peut être difficile dans un tel environnement. En entrée, types simples; en sortie, booléen. Élémentaire.
En mettant en place des icônes de citation, je me suis brièvement familiarisé avec la tâche, nous avons une machine à états finis, il y a une chaîne de caractères, c'est un modèle, nous devons le parcourir et faire une vérification, contourner le graphique d'état, donc si nous atteignons la fin du sommet, alors la réponse est vraie. C'est la tâche de la recherche inversée.
Ensuite, continuez, j'écris immédiatement un brouillon ici, puis je vais vous montrer une version de travail:
Une ligne ... dans le prologue, un type de données important est une liste, c'est un concept récursif, décrit de manière déclarative, vous devez donc travailler avec, vous devez transformer des chaînes en listes d'atomes. Soit dit en passant, un atome n'est pas seulement un symbole, bien qu'il le soit aussi, un atome est une chaîne avec une petite lettre sans espaces, pour Prolog ce sont des constantes de chaîne et vous ne pouvez pas mettre de guillemets.
atom_to_list('',[]). %- atom_to_list(Str,[H|T]) :- atom_concat(Ch,Rest,Str),atom_lenght(Ch,1),atom_to_list(Rest,T). %- ,
Désolé pour mon anglais, nous allons le vérifier dans le meilleur environnement actuellement, swi-prolog.org , il y a un éditeur en ligne, ici:
Oups. C'est ce que signifie ne tromper personne, c'est un seuil d'entrée élevé, les appels aux prédicats de bibliothèque ne sont pas corrects. Nous recherchons les bons prédicats intégrés pour travailler avec des atomes.
Et dans l'image il y a un message que la variable H n'était pas réclamée, une faille dans la logique, la tête de la liste est le premier caractère, et à sa place devrait être Ch .
Voici une documentation:
atom_concat (? Atom1 ,? Atom2 ,? Atom3)
Atom3 forme la concaténation d'Atom1 et Atom2. Au moins deux des arguments doivent être instanciés en atomes. Ce prédicat permet également le mode (-, -, +), divisant de façon non déterministe> le 3e argument en deux parties (comme le fait append / 3 pour les listes). SWI-Prolog permet des arguments atomiques. Le code portable doit utiliser atomic_concat / 3 si des arguments non atomiques sont impliqués.
atom_length (+ Atom, -Length)
Vrai si Atom est un atome de caractères Longueur. La version SWI-Prolog accepte tous les types atomiques, ainsi que les listes de codes et les listes de caractères. Le nouveau code devrait éviter cette fonctionnalité et utiliser write_length / 3 pour> obtenir le nombre de caractères qui seraient écrits si l'argument était remis à write_term / 3.
3.1 Atome dans la liste des atomes
Comme ça
3.2 La machine d'état elle-même
Imaginez un graphique qui lit les caractères d'un modèle et vérifie la conformité avec les caractères de la ligne d'entrée. Projets de solutions:
%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).
Faisons l'interface finale:
isMatch (S, P): - atom_to_list (S, SL), atom_to_list (P, PL),!, test_pattrn (SL, PL),!.
Voici tous les exemples de l'énoncé du problème:
4. Arbitre
Il semble que la décision soit prête, maintenant nous allumons l'arbitre. Sur le site leetcode.com (oui, oui, on résout le problème numéro 44), on va recevoir des tests, on va essayer de les exécuter séquentiellement avec notre implémentation. Malheureusement, ils n'acceptent pas les programmes sur Prolog .
Rien, nous aurons toutes les tâches une par une:
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
Voici une liste de tests, quelqu'un a fait de son mieux en introduisant une telle liste de contrôle à ce problème.
Et ce ne sont pas tous les tests, jusqu'à ce que nous nous arrêtions:
Voici le programme terminé, plus quelques tests:
%- 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).
Voici les résultats des tests:
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. Conclusion
Prolog est comme une séance d'entraînement pour l'esprit. Il est amusant de résoudre des problèmes dessus, bien que cette solution n'ait pas été optimisée. Se rendre manuellement à des tests plus complexes s'est avéré très laborieux, jusqu'à présent, il n'a pas été possible de prouver l'exhaustivité de la solution. Et il me semble que j'ai déjà atteint la taille d'un article habr.
Sur quel exemple cette décision échoue-t-elle?
Comment aimez-vous mon appel, les habitants de Habr?
Vous pouvez rivaliser en faisant en sorte que votre cerveau résout des problèmes et montre des solutions intéressantes, car la programmation est un processus créatif.